冒泡排序算法不起作用

我正在创建一个C++/SFML游戏引擎。游戏中的每个“实体”都有一个指向它的指针，存储在Entity类的静态向量中，名为entityRenderList。该向量在游戏循环的每次迭代中按照Bubble Sort算法进行排序，以便以正确的顺序绘制小精灵。冒泡排序算法不起作用

每当一个实体被删除时，它用一个NULL指针替换它在vector中的指针。我的算法默认情况下应该使它找到的任何NULL指针排序到向量的后面，并在那里随后被删除。

下面是排序算法的代码：

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 
    } 
}

什么应来发生的是，任何NULL指针从对算法的每次运行的载体中删除。但是，情况并非如此，任何NULL指针都保持在原来的位置，并且看起来根本没有进行排序。

注意：passMade布尔值存在，所以如果数组通过并且没有进行交换，算法将停止。

任何帮助，将不胜感激。提前致谢。

编辑：排序算法代码从here稍微修改。

来源

2014-11-03 Dumbgenius

为什么使用自己的冒泡排序而不是'std :: sort'或其他库排序方法？您可以避免使用预先测试过的库和数据结构（例如'std :: list'和'std :: sort'）在StackOverflow上发布问题。 – 2014-11-03 19:46:58

@ThomasMatthews如果您只是在交换代码之后，您会看到被交换的两个实体的“renderListID”已更改。这样他们可以在被删除时将它们的位置设置为NULL。这对于'std :: sort'来说是不可能的，因为那样我就不得不执行一次搜索来确定每个指针的移动位置。 – Dumbgenius 2014-11-03 19:55:02

j循环限制中存在一个错误。例如，如果列表中有10个元素，则n为9,n-1为8，最大值为j为7.该循环可交换10元素列表的元素7和8。它不能交换最后一对，即元素8和9.

正如评论所建议的那样，使用已经过测试和工作的库排序会更好更简单。随着时间的推移，您不必调整renderListID字段，您可以在最后一次通过列表中完成所有操作。如果在弹出NULL元素后执行该操作，则不需要在该循环中测试NULL。

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

来源

2014-11-04 05:14:21

冒泡排序算法不起作用

回答

相关问题