Bubble sort algorithm not working

Question

I am in the process of creating a C++/SFML game engine. Every "entity" in the game has a pointer to it stored in a static vector in the Entity class, called entityRenderList. This vector is sorted by the Bubble Sort algorithm on each iteration of the game loop so that the sprites are drawn in the correct order.

Whenever an entity is deleted, it replaces its pointer in the vector with a NULL pointer. My algorithm should, by default, cause any NULL pointers it finds to be sorted to the back of the vector, where they are subsequently removed.

Here is the code for the sorting algorithm:

bool Entity::depthSortFunction(Entity* a, Entity* b)
{
    if (b==NULL) return false; //any NULL values are moved to the back
    if (a==NULL) return true;

    else return (a->depth_) < (b->depth_);
}

void Entity::sortEntityRenderList()
{
    if (entityRenderList.size()>1) {
        //Any NULL values are brought to the top to be stripped off.

        bool passMade=false;
        Entity* temp;
        int n=entityRenderList.size()-1;
        for(int i=0; i<n; i++)
        {
            passMade=false;
            for(int j=0; j<n-1; j++)
            {
                if(depthSortFunction(entityRenderList[j],entityRenderList[j+1])) 
                {
                    //then swap them
                    temp = entityRenderList[j+1];
                    entityRenderList[j+1] = entityRenderList[j];
                    entityRenderList[j] = temp;
                    //and then notify the entities of the change
                    if (entityRenderList[j]!=NULL)   {entityRenderList[j]->renderListID=j;}
                    if (entityRenderList[j+1]!=NULL) {entityRenderList[j+1]->renderListID=j+1;}

                    passMade=true;
                    //std::cout<<"Swapping entries "<<j<<" and "<<j+1<<"...\n";
                }
            }
            if (!passMade) {
                break; //then it is sorted, as we have not needed to modify the array.
            }
        }
    }
    //Now, we strip off any NULL values from the top.
    while (!entityRenderList.empty() && entityRenderList.back()==NULL) {
        entityRenderList.pop_back(); //strip off last one
    }
}

What should be happening is that any NULL pointers are removed from the vector on each run of the algorithm. However, this is not the case, and any NULL pointers stay right where they are, and appear to not be sorted at all.

NB: The passMade boolean is there so that if a pass of the array is made and no swaps were made, the algorithm stops.

Any help would be appreciated. Thanks in advance.

EDIT: The sorting algorithm code is slightly modified from here.

Answer 1

There is a bug in the j loop limit. For example, if the list has 10 elements, n is 9, n-1 is 8, and the largest value of j is 7. The loop can exchange elements 7 and 8 of a 10 element list. It cannot exchange the last pair, elements 8 and 9.

As suggested by a comment, it would be better and simpler to use a library sort that is already tested and working. Rather than adjust the renderListID fields as you go along, you could do them all in a single pass through the list at the end. If you do it after popping the NULL elements, you would not need to test for NULL in that loop.

    for(int i=0; i<entityRenderList.size(); i++)
    {
        entityRenderList[i]->renderListID=i;
    }