Quicksortでスタックオーバーフローを起こさないようにするには？ (ID:10283)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 CMAGAZINEの「アルゴリズムとデータ構造」から 「コームソート」を移植。 オーダは N LOG N だそうですがクイックソートより遅い気がします。 スタックの消費は少ないです（たぶん） >一番遅い場合は、O(2*N) O(N^2)ですよね＾＾ ※const で Nを定義してください procedure CombSort(var a: array of Integer); var i, temp, flag, gap: Integer; begin gap := N; repeat gap := (gap * 10) div 13; (* 収縮率は1.3（gapが毎回1/1.3になる） *) if (gap = 0) then gap := 1; flag := 1; (* 先頭から順に見ていって *) i := 0; (*前に移動*) while (i < N - gap) do begin (* 距離がgapだけ離れた要素を比較し， 並びがおかしければ *) if (a[i] > a[i + gap]) then begin (* 入れ替える *) flag := 0; temp := a[i]; a[i] := a[i + gap]; a[i + gap] := temp; end; Inc(i); end; (* 1度も並べ替えをせずに，gap=1で見終わったら終了 *) until ((gap <= 1) and (flag = 1)); //trueで終了 end;