クイックソートとスタックオーバーフローの例外

Question

クイックソートは、特定の条件でスタックオーバーフロー例外が発生する可能性があると思います。

ソート処理中にピボット要素を選択するには、基本的に2つの方法があります。ピボット値は、ソートされた範囲の中央の要素またはランダムに選択された要素（ソートされた範囲内）です。 2つ目の方法（ランダム）は、最初の方法よりもスタックオーバーフローが起こりにくいのですか？私に助言してもらえますか？

procedure QuickSort(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 

    procedure Sort(lLowIndex, lHighIndex: integer); 
    var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    begin 
    repeat 
     lLeft := lLowIndex; 
     lRight := lHighIndex; 
     lPivot := (lLowIndex + lHighIndex) div 2; //the pivot as the element in the middle 
     //lPivot := lLowIndex + Random(lHighIndex - lLowIndex + 1); //the pivot chosen randomly 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lLowIndex < lRight) then 
     Sort(lLowIndex, lRight); 

     lLowIndex := lLeft; 
    until lLeft >= lHighIndex; 
    end; 

begin 
    if lHighBound > lLowBound then 
    Sort(lLowBound, lHighBound); 
end; 

事前にあなたのアドバイスをありがとう：ここ

は、クイックソート（デルファイ）の私のバージョンです！

マリウス。

Answer 1

ピボット要素として特定のインデックス（最初、最後、または中間）にある要素を使用すると、特定のデータセットで縮退の危険が常に発生します。最初と最後の要素は、あまりにも一般的な事前ソート済みの（またはほとんど事前にソートされた）データで縮退するため、特に悪いことです。中間要素は実際には問題は少ないが、依然として悪意を持って構築されたデータセットの影響を受けやすい。

ランダム要素を使用すると、純粋な不運でしか縮退が起こらないことを意味します（仮想攻撃者がRNGを予測できないと仮定した場合）ので、良い戦術です。その悪い幸運に襲われる可能性を大幅に減らすさらなる改善は、ランダムに選択された3（または5以上）のメジアンを使用することですが、追加の複雑さと実行時間に対して重み付けする必要があります。

Answer 2

効率を向上させる確率的方法は、3つのランダム要素を選択し、中間値（最大値でも最小値でもない値）を使用することです。

レコードのスタックを使用して、境界をプッシュしてポップし、再帰呼び出しを行う代わりにループを書き込むこともできます（また、配列へのポインタはすべてのコール）。

編集：私は、内部プロシージャがパラメータとしてポインタを取っていないことに気づいたので、その部分を忘れて^ _ ^とにかく、スタックフレームは関数のパラメータよりも多くの情報を持っています。さらに多くのメモリを効率的に使用できます（主なポイントは、データスタックが割り当てられているヒープは通常、プロセススタックよりも大きくなります）。

Answer 3

ご回答ありがとうございます。

Fortran、非再帰的メソッドの作成に関するご意見ありがとうございます。それらに基づいて、私はiterational迅速な並べ替えを行うことができたし、それは正常に動作しているようだ:)。ここで

はコードです：

procedure QuickSortI(lLowBound, lHighBound: integer; lCompare: TListSortCompare; 
    lSwap: TListSortSwap); 
var 
    lLeft: Integer; 
    lRight: Integer; 
    lPivot: Integer; 
    lLeftCompare: Integer; 
    lRightCompare: Integer; 
    lStack: array of integer; 
    lStackLen: integer; 
begin 
    if lHighBound > lLowBound then 
    begin 
    lStackLen := 2; 
    SetLength(lStack, lStackLen); 
    lStack[lStackLen - 1] := lLowBound; 
    lStack[lStackLen - 2] := lHighBound; 

    repeat 
     lLowBound := lStack[lStackLen - 1]; 
     lHighBound := lStack[lStackLen - 2]; 
     SetLength(lStack, lStackLen - 2); 
     Dec(lStackLen, 2); 

     lLeft := lLowBound; 
     lRight := lHighBound; 
     lPivot := (lLowBound + lHighBound) div 2; 
     repeat 
     lLeftCompare := lCompare(lLeft, lPivot); 
     while lLeftCompare < 0 do 
     begin 
      Inc(lLeft); 
      lLeftCompare := lCompare(lLeft, lPivot); 
     end; 
     lRightCompare := lCompare(lRight, lPivot); 
     while lRightCompare > 0 do 
     begin 
      Dec(lRight); 
      lRightCompare := lCompare(lRight, lPivot); 
     end; 

     if lLeft <= lRight then 
     begin 
      if not ((lLeftCompare = 0) and (lRightCompare = 0)) then 
      begin 
      lSwap(lRight, lLeft); 

      if lPivot = lLeft then 
       lPivot := lRight 
      else if lPivot = lRight then 
       lPivot := lLeft; 
      end; 
      Inc(lLeft); 
      Dec(lRight); 
     end; 
     until lLeft > lRight; 

     if (lHighBound > lLeft) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLeft; 
     lStack[lStackLen - 2] := lHighBound; 
     end; 

     if (lLowBound < lRight) then 
     begin 
     Inc(lStackLen, 2); 
     SetLength(lStack, lStackLen); 
     lStack[lStackLen - 1] := lLowBound; 
     lStack[lStackLen - 2] := lRight; 
     end; 

    until lStackLen = 0; 
    end; 
end; 

私は私が最適な方法でそれを実現したいと考えています。私はソートの境界を格納するために動的配列を使いました（アイテムの各ペアは低および高の境界です）。

この反復方法は再帰的な方法よりもわずかに遅いようですが、それほど問題にはならないと思います。

あなたが間違いに気づいた場合、または方法を最適化する方法がわかっている場合は、私にお知らせいただければ幸いです。

ありがとうございます！

マリウス。

Answer 4

まともなクイックソートの実装では、O（ログn）スタックスペースが使用されます。最小のサブアレイを最初にソートすることで実現します。最悪の場合は、ピボットが最大の要素で、毎回1つ小さいサブアレイをソートしようとする場合です。これは、すでにソートされたデータを入力として使用し、正しい要素をピボットとして使用する場合に発生します。

明示的なスタックの実装が遅く、同じ問題が発生します（スタックの代わりにヒープになります）。

サブアレイが小さい（5-25要素）場合、挿入ソートへの切り替えがあります。また、このサイトのデュアルピボットquicksortの質問を見てください。