快速排序程序停止工作

Question

我正試圖解決hackerrank上的快速排序 - 2挑戰。它說，我們必須重複調用分區，直到整個數組被排序。我的程序適用於某些測試用例，但對於某些程序崩潰，「Quick Sort - 2.exe已停止工作」。我找不到爲什麼會發生這種情況。 數組/子數組的第一個元素每次都被當作主元素。

#include <iostream> 
#include <conio.h> 

using namespace std; 

void swap(int arr[], int a, int b) 
{ 
    int c = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = c; 
} 

void qsort(int arr[], int m, int n) //m - lower limit, n - upper limit 
{ 
    if (n - m == 1) 
    { 
     return; 
    } 

    int p = arr[m], i, j, t;   //p - pivot element, t - temporary 
    //partition 
    for (int i = m+1; i < n; i++) 
    { 
     j = i; 
     if (arr[j] < p) 
     { 
      t = arr[j]; 
      while (arr[j] != p) 
      { 
       arr[j] = arr[j-1]; 
       j--; 
      } 
      arr[j] = t;    //pivot is at j and j+1 
     } 
    } 
    //check if sorted 
    int f = 1; 
    while (arr[f] > arr[f-1]) 
    { 
     if (f == n-1) 
     { 
      f = -1; 
      break; 
     } 
     f++; 
    } 
    if (f == -1) 
    { 
     cout << "Sub Array Sorted\n"; 
    } 
    else 
    { 
     if (p == arr[m])    //pivot is the smallest in sub array 
     { 
      qsort(arr, m+1, n);  //sort right sub array 
     } 
     else 
     { 
      qsort(arr, m, j+1);  //sort left sub array 
      qsort(arr, j+1, n);  //sort right sub array 
     } 
    } 
} 

int main() 
{ 
    int n; 
    cin >> n; 

    int arr[n]; 
    for (int i = 0; i < n; i++) 
    { 
     cin >> arr[i]; 
    } 

    qsort(arr, 0, n); 

    for (int i = 0; i < n; i++) 
    { 
     cout << arr[i] << " "; 
    } 

    return 0; 
} 

Answer 1

你有一個索引超出範圍的問題。

這不會給你解決方案，但它可以幫助你找到你的程序失敗的原因。

所以它使用int的vector而不是int原始陣列，而當你運行這個程序，你得到一個索引超出範圍例外的我已經修改你的程序。

觸發問題的序列4 3 7 1 6 4是硬編碼的，因此您無需每次都輸入它。

#include <iostream> 
#include <vector> 

using namespace std; 

void swap(vector<int> & arr, int a, int b) 
{ 
    int c = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = c; 
} 

void qsort(vector<int> & arr, int m, int n) //m - lower limit, n - upper limit 
{ 
    if (n - m == 1) 
    { 
    return; 
    } 

    int p = arr[m], j, t;   //p - pivot element, t - temporary 
            //partition 
    for (int i = m + 1; i < n; i++) 
    { 
    j = i; 
    if (arr[j] < p) 
    { 
     t = arr[j]; 
     while (arr[j] != p) 
     { 
     arr[j] = arr[j - 1]; 
     j--; 
     } 
     arr[j] = t;    //pivot is at j and j+1 
    } 
    } 
    //check if sorted 
    int f = 1; 
    while (arr[f] > arr[f - 1]) 
    { 
    if (f == n - 1) 
    { 
     f = -1; 
     break; 
    } 
    f++; 
    } 
    if (f == -1) 
    { 
    cout << "Sub Array Sorted\n"; 
    } 
    else 
    { 
    if (p == arr[m])    //pivot is the smallest in sub array 
    { 
     qsort(arr, m + 1, n);  //sort right sub array 
    } 
    else 
    { 
     qsort(arr, m, j + 1);  //sort left sub array 
     qsort(arr, j + 1, n);  //sort right sub array 
    } 
    } 
} 

int main() 
{ 
    vector<int> arr = { 4,3,7,1,6,4 }; 

    qsort(arr, 0, arr.size()); 

    for (unsigned int i = 0; i < arr.size(); i++) 
    { 
    cout << arr[i] << " "; 
    } 

    return 0; 
} 

Answer 2

首先，你所做的不是快速排序，而是分而治之分割和插入排序的組合。

典型快速排序從數組的下限（p）和上限（q）開始，分別跳過元素arr [p] m。然後它用arr [q]交換arr [p]，增加/減少並檢查p> = q。沖洗並重復，直到p> = q。然後在子分區上調用。這樣，p或q保持樞軸位置，並且亞呼叫是顯而易見的。

但是你正在以不同的方式做：你從子陣列右側向左側插入元素。這樣的事情會在一次迭代中產生O（N^2）時間複雜度。例如，考慮1,0,1,0,1,0,1,0,1,0,1,0，...序列。這會使O（N^2）上的最壞情況複雜度增加。

出的時間複雜度......在你的函數問題在於假定，殲持有子調用樞軸位置：

qsort(arr, m, j+1);  //sort left sub array 
qsort(arr, j+1, n);  //sort right sub array 

其實，j被一次又一次等於設置爲我在主for循環。如果最後一個元素等於或大於數據透視表，則以j = n-1結束，您調用qsort（arr，n，n），並且第一行校驗通過（原文！），因爲nn！= 1。

爲了解決這個問題，你應該做兩兩件事：

1）重新整理後直接找到支點位置：

for (int i = m; i < n; i++) 
    if (p == arr[i]) 
    { 
     j = i; 
     break; 
    } 

或該行後在不同的變量初始化，更新：

arr[j] = t;    //pivot is at j and j+1 

並更新遞歸調用使用新的變量，而不是Ĵ

2）做出更防彈檢查你函數的開頭：

if (n - m <= 1) 

後者將足以得到一些結果，但它會少得多比你目前的想法更有效，在最壞的情況下可能會下降到O（N^3）。