Quicksort没有做任何事情，现在陷入永久循环

我试图实施就地版本的quicksort。这是我的代码：Quicksort没有做任何事情，现在陷入永久循环

#include <vector> 
#include <algorithm> 

using namespace std; 

size_t partition(vector<int>& v, size_t l, size_t r, size_t p) 
{ 
    size_t pivot = v[p]; 
    swap(v[p], v[r]); 
    size_t store = l; 

    for (size_t i = l; l < (r-1); i++) { 
     if (v[i] <= pivot) { 
      swap(v[i], v[store]); 
      store++; 
     } 
    } 
    swap(v[store], v[r]); 

    return store; 
} 

void quickSort(vector<int>& v, size_t l, size_t r) 
{ 
    //If two or more elements 
    if(l<r) 
    { 
     size_t pI = l; 
     size_t nP = partition(v, l, r, pI); 

     quickSort(v, (nP+1), r); 
     quickSort(v, l, (nP-1)); 
    } 
}

仅供参考，我使用的是伪代码in-place version on wikipedia。

我遇到的问题是，我第一次accredntily调用列表中间的函数作为最左arguemtn。该程序运行无错误，并输出新的列表，完全不变和未排序（根本没有错误）。我发现我的错误，现在我这样调用该函数：

quickSort(v, 0, (v.size()-1));

而且Xcode的警告我说，我被陷在一个永远的循环在

if (v[i] <= pivot)

这是在确切的路线，如如果比较触发某事。如果你能帮助我，我会很高兴！

来源

2014-02-16 pimmen

嗨。要求人们发现代码中的错误并不是特别有效。您应该使用调试器（或者添加打印语句）来分析问题，追踪程序的进度，并将其与预期发生的情况进行比较。只要两者发生分歧，那么你就发现了你的问题。（如果有必要，你应该构造一个[最小测试用例]（http://sscce.org）。） –

您的问题是，您正在比较l < r - 1，但在for循环的每次迭代中增加了i。因此，无限循环。将for (size_t i = l; l < (r-1); i++) {更改为for (size_t i = l; i < (r-1); i++) {。

来源

2014-02-16 11:17:02

是的，它也应该是' Predelnik

Quicksort没有做任何事情，现在陷入永久循环

回答

相关问题