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沒有做任何事情，現在陷入永久循環

回答

相關問題