クイックソートスタックオーバーフローC++ビッグナンバー

Question

良い日 クイックソートを10000番台で使用しようとしていますが、スタックオーバーフローエラーが発生しています。それは乱数で動作しますが、降順と昇順の数字ではありません。

「 はあなたにソートされた要素については

void quickSort(long* array, long start, long last) 
{ 
    if (start < last) 
    { 
     int p = partition(array, start, last); 
     quickSort(array, start, p-1); 
     quickSort(array, p + 1, last); 
    } 
} 
int partition(long* array, long start, long last)//first partition 
{ 
    int j = start + 1; 
    for (long i = start + 1;i <= last;i++) 
    { 
     if (array[i] < array[start]) 
     { 
      swap(array[i], array[j]); 
      j++; 
     }   

    } 
    swap(array[start], array[j - 1]); 
    return j - 1; 
} 
' 

Answer 1

コードは大丈夫ですが、コンパイラはスタックを非常に効果的に使用します。予約されたスタック量を増やすだけです。コンパイラはプロシージャの実行中にスタックが壊れていないかどうかを確認するために大規模なスタックチャンクを保存するだけなので、リリースするよりもデバッグプロファイルでずっと頻繁に発生します。

Answer 2

に感謝し、あなたのピボット値として三つの要素array[start]、array[last]とarray[(start + last + 1)/2]の中央値を選択することによってこの問題を回避することができます。

int median_of_3(long* array, long start, long last) 
{ 
    long a = (start + last + 1)/2, b = start, c = last; 
    if (array[c] < array[a]) swap(array[c], array[a]); 
    if (array[b] < array[a]) swap(array[b], array[a]); 
    if (array[c] < array[b]) swap(array[c], array[b]); 
    return partition(array, start, last); 
} 

大きなスタック深度を避けるための追加の戦略は、どのパーティションが小さいかを再計算し、小さなパーティションを再帰的に呼び出すことです。その後、他のパーティションをループに最適化することができます（末尾再帰最適化）。

void quickSort(long* array, long start, long last) 
{ 
    if (start >= last) return; 

    int p = median_of_3(array, start, last); 
    int next_start[2] = { start, p + 1 }; 
    int next_last[2] = { p - 1, last }; 
    bool i = p > (start + last)/2; 
    quickSort(array, next_start[i], next_last[i]); 
    /* 
    * If the compiler does not optimize the tail call below into 
    * a loop, it is easy to do the optimization manually. 
    */ 
    quickSort(array, next_start[!i], next_last[!i]); 
} 

イントロスペクションは、大きなスタックの深さを避けるためにも使用できます。再帰呼び出し深度を追跡し、「深すぎる」​​場合は、マージソートやヒープソートなどの異なるソート戦略に安全に失敗します。これは現在、std::sortによって使用されている動作です。

void introSortImpl(long* array, long start, long last, int depth) 
{ 
    if (--depth == 0) { 
     heapSort(array, start, last); 
     return; 
    } 

    if (start >= last) return; 

    int p = median_of_3(array, start, last); 
    int next_start[2] = { start, p + 1 }; 
    int next_last[2] = { p - 1, last }; 
    bool i = p > (start + last)/2; 
    introSortImpl(array, next_start[i], next_last[i], depth); 
    introSortImpl(array, next_start[!i], next_last[!i], depth); 
} 

void introspectionSort(long* array, long start, long last) 
{ 
    introSortImpl(array, start, last, log2(start - last) * 3); 
} 

Answer 3

小さなパーティションで再帰を使用するquicksortのようなLomutoパーティションスキームの例では、lまたはrを更新してから、ループバックして大きなパーティションを2つのパーティションに分割し、プロセスを繰り返します。最悪のスタック空間はO（log2（n））であり、スタックのオーバーフローを避ける必要があります。最悪の時間の複雑さは依然としてO（n^2）です（パーティションの実装方法によって異なります）。

この例は半再帰と呼ばれます。テイル再帰の例ではありません。テール再帰とは、再帰関数がそれ自身を呼び出した後に戻ることを意味するからです。最初の質問例の2番目の呼び出しは、テールコールです。だから、

void quicksort(int * tab, int l, int r) 
{ 
    int q; 
    while(l < r) 
    { 
     q = partition(tab, l, r); 
     if(q - l < r - q) {  // recurse into the smaller partition 
     quicksort(tab, l, q - 1); 
     l = q + 1; 
     } else { 
     quicksort(tab, q + 1, r); 
     r = q - 1; 
     } 
    }       // loop on the larger partition 
}