クイックソートプログラムが動作を停止しました

Question

私はハッカーにとって簡単なソート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いうよりintの生の配列のvectorを使用していますので、私はあなたのプログラムを変更している、とあなたがこのプログラムを実行するときには、範囲の例外のうちのインデックスを取得します。

問題を引き起こすシーケンス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

まず、あなたが作成したのは、クイックソートではなく、divide-ans-conquerパーティショニングと挿入ソートの組み合わせです。

canonicalクイックソートは、それぞれ要素arr [p] mをスキップして、配列の下限（p）と上限（q）から移動します。次にarr [p]をarr [q]と入れ替え、p≧qの場合はインクリメント/デクリメントします。 p> = qになるまですすぎ、繰り返す。その後、サブパーティションでコールを行います。このようにpまたはqはピボット位置を保持し、サブコールは明白です。

しかし、あなたは別のやり方で、サブアレイの右側から左側に要素を挿入します。このようなことは、1回の反復でO（N^2）時間の複雑さを生成する可能性があります。たとえば、1,0,1,0,1,0,1,0,1,0,1,0、... sequenceを考えてみましょう。これは、O（N^2）よりも最悪の複雑さを増やすことができる。時間計算量のうち

は...あなたの機能に問題はjがsubcallsでのピボット位置を保持していることを前提にある：

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

実は、jはループのためのあなたの主に私に何度も何度も同じ設定されています。最後の要素がピボット以上であれば、n = 1となり、qsort（arr、n、n）を呼び出し、nn！= 1であるため、最初のチェックが渡されます（sic！）。

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つのことを行う必要があり、この問題を解決するには

更新新しい変数の代わりに、J

2を使用するには、再帰呼び出しは）あなたの関数の先頭でより多くの防弾チェックを行います。

if (n - m <= 1) 

後者は、いくつかの結果を取得するのに十分だろうが、それは非常に少なくなりますあなたの現在のアイデアよりも効果的で、最悪の場合はおそらくO（N^3）に落ちます。