快速排序爲常數提供stackoverflow但不是隨機數

當我將數組值賦值爲rand()或任何常數值時，我感到非常困惑，爲什麼此C++代碼段的行爲不同。快速排序爲常數提供stackoverflow但不是隨機數

const int MIN_SIZE = 10000; 
const int MAX_SIZE = 100000; 

int main() 
{ 
    for(j = MIN_SIZE; j <= MAX_SIZE; j += MIN_SIZE) { 
    int *arrPtr = new int[j]; 
    for(int i = 0; i < j; i++) 
     arrPtr[i] = 1; //When I put rand() here, it works fine but in any constant it gives stack overflow 
    quickSort(arr, 0, j - 1); 
    delete []arrPtr; 
    } 
}

上述基本的代碼創建與j在每匝一個動態分配的陣列大小，這得到由MIN_SIZE（10,000）遞增，並且分配一些特定整數每個索引。賦值後，它將與我將在下面提供的快速排序算法分類，然後在完成時釋放此數組。這整件事重複到MAX_SIZE（100,000）。

這裏是我的快速排序代碼：

void quickSort(int *arr, int front, int rear) 
{ 
    if (front < rear) 
    { 
     int part = partition(arr, front, rear); 
     quickSort(arr, front, part - 1); 
     quickSort(arr, part + 1, rear); 
    } 
} 

int partition(int *arr, int front, int rear) 
{ 
    int element = arr[rear]; 
    int i = front - 1; 
    for (int j = front; j<rear; ++j) 
    { 
     if (arr[j] <= element) 
     { 
      ++i; 
      long temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
     } 
    } 
    long temp = arr[i + 1]; 
    arr[i + 1] = arr[rear]; 
    arr[rear] = temp; 
    return i + 1; 
}

我試圖實現其嚴格使用最後一個項目爲支點快速排序算法。在這種情況下，我面臨着一個奇怪的問題：當我使用rand()函數將數組的每個值賦給一個隨機數時，一切正常，但是，當我輸入一個常數值時，數組的大小會上升到4039（當你操縱MAX_SIZE和MIN_SIZE時）則給出堆棧溢出錯誤。我真的很困惑，爲什麼地球上會引起問題，此外，爲什麼4039？

來源

2016-02-29 Burak.

檢查分區的返回值。我想你有一個運行的方式遞歸，由於分區返回一個錯誤的值，導致快速排列整個數組一遍又一遍。 –

這功課嗎？如果是這樣的話，那麼在網絡和SO上的快速排序會有很多幫助。否則...使用'vector'和內置的'sort'算法。 10次中有9次會比你寫的速度快。 –

當數組中的所有元素都相同時，數組已經被排序，並且如果數組已經排序，那麼使用quicksort會導致最壞的情況。 [請參閱此解釋]（https://en.wikipedia.org/wiki/Quicksort#Choice_of_pivot）。 –

以直接方式實現時，使用最後一個元素作爲主元素的快速排序預計會溢出相同元素的堆棧。這是quicksort的工作原理。這是算法中的一個「缺陷」。

看看爲什麼看看如何創建遞歸函數調用。

quicksort(arr, 0, 100) - will produce the recursive calls 
    quicksort(arr, 0, 99); and 
    quicksort(arr, 100, 100);

問題是quicksort(arr, 0, 99);將爲數組中的每個元素遞歸。

在你的情況下，你的堆棧滿了4039個元素。您的每個通話似乎都有大約8個整數值，這會給您一個關於您的堆棧最大大小的提示。我猜測大約1 MB。

隨機整數的情況並非如此，因爲遞歸調用的深度將均勻分佈在遞歸的左邊部分和右邊部分之間。這種期望的行爲使得遞歸深度方法記錄爲N.對於MAX_SIZE，這是大約17的深度，而不是100000.這就是快速排序被描述爲N log N算法的原因。第一個N來自分區。

來源

2016-02-29 09:55:20

所以我們不應該使用最後一個元素作爲支點，它最終會導致堆棧溢出，然後..在某些情況下......但是當我們使用rand（）或一個簡單的常量時會有所不同。當我使用rand（）賦值時，我的程序完美無缺地運行，但是，乍一看，我手動分配的這些常量值在我看來是造成問題的原因。然而，我要告訴你關於你是對的最後一個樞軸缺陷。 –

不要爲最大間隔遞歸，只適用於較小間隔（尾遞歸優化） – mksteve

@Burak。如果數組包含隨機值，則數據透視將不是最後一個元素。 –

一個常量數組，帶有一個end-pivot並將數組分成兩個結果，遞歸深度爲「數組中的元素數」和O（n^2）時間。

有很多方法可以解決這個問題。

首先，將數組分成3個部分。大於，小於，並且等於來分區。平等之間。這可以修復您遇到的拐角案例。它增加了常數因子，但快速排序成本變爲O（n lg m），其中m是作爲獎勵的不同元素的數量。

排序陣列仍然死亡可怕。做一個更好的部分選擇器。隨機分區使得接近0的可怕行爲的概率。採用3（或2k + 1）個元素（可能是隨機的）並使用它們的中值是另一種方法。對於確定性良好行爲，在O（n）時間內找到30％到70％標記的元素的算法被稱爲「中值5」（其不僅取5元素的中值）。

另一個技巧是陣列分區，遞歸上較小分區，並且在大環。這解決了遞歸深度問題，但不是運行時問題。

接下來，考慮小陣列長度的逃生策略。快速排序（說）8個元素可能會嚴重不理想與選擇排序相比。一旦你有一個逃生策略，你可以優化使用一個快速和骯髒的快速排序（爲樞軸選擇3個隨機元素等）並跟蹤遞歸深度。如果你通過2 * lg（n）的深度，逃脫到可證實的快速排序（5的中位數找到樞軸）。而當你跌落到8以下（調整這個）elememts，切換到選擇排序。

最後，當你只是std::sort時，以上所有和更多可能已經完成。所以用它代替。

來源

2016-02-29 10:27:05 Yakk

關於分區步驟的註釋。霍爾在'62年的原始快速排序描述了一個更小和更大的分區的分區步驟。分割元素是分割元素。所以三分區劃分不是一個「純」快速排序。 OP所遇到的問題在論文中被評論爲「如果綁定的價值很容易出現尷尬的情況......」。 –

如果您總是先遞歸到較小的一半並且編譯器爲第二次調用生成尾遞歸，那麼您可以保證堆棧深度爲O(log(N))。

void quickSort(int *arr, int front, int rear) 
{ 
    if (front < rear) 
    { 
     int part = partition(arr, front, rear); 
     int a, b, c, d; 
     if (part - front <= rear - part) 
     { 
      a = front; 
      b = part - 1; 
      c = part + 1; 
      d = rear; 
     } 
     else 
     { 
      a = part + 1; 
      b = rear; 
      c = front; 
      d = part - 1; 
     } 
     quickSort(arr, a, b); 
     quickSort(arr, c, d); 
    } 
}

來源

2016-02-29 10:32:03 piotrekg2

快速排序爲常數提供stackoverflow但不是隨機數

回答

相關問題