0

Delphi のサンプルの 1 つに、次の QuickSort の実装があります。

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi); // just for visual
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;
  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

動作しますが、パーティショニングは奇妙に思えます。それとも、これは一般的な最適化ですか?

ランダムな値でテストを行ったところ、Mid が Hi、Lo、またはその中間にない場合がありました。その場合、「ピボット」は 2 つの値の間を取得します。これは、どちらかが Mid 値であっても、反転後に Lo と Hi の両方がインクリメントされるためです。ピボット値を保持し、その左側と右側で別の QuickSort を実行する手がかりではありませんか。これは等しいキー値の最適化ですか?

また、この実装には等しい値の問題がありますか? 3 方向パーティショニングはより良いものになるでしょうか?

4

3 に答える 3

1

また、中央値が 3 などのさまざまなバリアントもテストしました。スピードアップをもたらした唯一のことは、クイックソートと挿入ソートのハイブリッドにし、再帰の 1 つをアンロールすることでした。何も与えなかったので、キー部分を削除しました。私のテストからの最終的な変種は次のとおりです。

procedure QuickSort3(var A: array of integer; iLo, iHi: integer);
var
  Hi, Lo, T, Mid: integer;
begin
  repeat
    if (iHi-iLo) > 16 then
    begin
      Mid := A[(iHi + iLo) shr 1];
      Lo := iLo;
      Hi := iHi;
      repeat
        while A[Lo] < Mid do inc(Lo);
        while A[Hi] > Mid do dec(Hi);
        if Lo <= Hi then
        begin
          if Lo <> Hi then
          begin
            T := A[Lo];
            A[Lo] := A[Hi];
            A[Hi] := T;
          end;
          inc(Lo);
          dec(Hi);
        end;
      until Hi < Lo;
      if Hi > iLo then
        QuickSort3(A,iLo,Hi);
      iLo := Lo;
    end
    else
    begin
      for Lo := iLo + 1 to iHi do
      begin
        T := Arr[Lo];
        Hi := Lo;
        while (Hi > iLo) and (Arr[Hi-1] > T) do
        begin
          Arr[Hi] := Arr[Hi-1];
          dec(Hi);
        end;
        Arr[Hi] := T;
      end;
      exit;
    end;
  until iHi <= Lo;
end;

ゲインは、1 億のランダム値で約 1.4 秒でした。

とにかく、これまでに学んだこと：

パーティショニングは正しいです。キーを処理する必要はありません。多くの QuickSort チュートリアルでは、これが「間違っている」と説明されています。必要ないという点で間違っています。

キーを処理するメリットはほとんどありませんでした。コールは少し少なくなりますが、追加の処理でペナルティも発生し、それらはほぼ同じです. 全体として、1 億の値をソートする際のキー処理で 50 ～ 100 ミリ秒速くなりました (合計 13.9 秒)。しかし、それは Delphi コンパイラにあります。

挿入ソートは、要素が 16 未満の場合にクイックソート内に含めるのに十分な機能を提供します。

于 2013-03-09T15:11:01.927 に答える
0

これがより良い方法かどうかわからないので、これについてコメントしてください。

私はQuickSortの本質を理解しようとしています。この修正により、この実装がより適切に機能すると思います（VisualSwapは無視してください。これは、デモの視覚効果専用です）。

procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
var
  Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo;
  Hi := iHi;
  T := (Lo + Hi) div 2;
  VisualSwap(A[Lo], A[T], Lo, T);
  Mid := A[T];
  A[T] := A[Lo];
  A[Lo] := Mid;

  inc(Lo);
  //Mid := A[(Lo + Hi) div 2];
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then
    begin
      VisualSwap(A[Lo], A[Hi], Lo, Hi);
      T := A[Lo];
      A[Lo] := A[Hi];
      A[Hi] := T;
      Inc(Lo);
      Dec(Hi);
    end;
  until Lo > Hi;

  if Hi > iLo then
  begin
    VisualSwap(A[iLo],A[Hi],iLo,Hi);
    A[iLo] := A[Hi];
    A[Hi] := Mid;
    dec(Hi);
  end;

  if Hi > iLo then QuickSort(A, iLo, Hi);
  if Lo < iHi then QuickSort(A, Lo, iHi);
  if Terminated then Exit;
end;

私がしたことは、ピボットを見つけながらキーを移動し、次にキーをピボットに配置し、そのキーポイントの外側でのみクイックソートすることでした。

于 2013-03-09T12:45:05.843 に答える
0

コードの1つのバグ：

mid =（low + high）div 2は、最大整数に近い配列を使用するとオーバーフローする可能性があります。

で解く：mid = low div 2 + high div 2

詳細については、アルゴリズムを参照してください。

そのリンクを読んだ後、あなたはそれを知っているべきです：

これは等しいキー値の最適化ですか？

いいえ、同じ値でも問題はありません。（クイックソートは安定したソートではありません）

また、この実装には同等の価値の問題がありますか？3ウェイパーティショニングの方が優れていますか？

問題はありません。いいえ、なぜそれが良いはずですか？最適化は、ランダムなピボット要素の選択を使用して実行できます。

于 2013-03-09T12:59:54.880 に答える