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

deldel 2004-08-08 01:07:36 No: 10279

Quicksortを利用して配列のソートを行っているのですが、
配列の数が多くなるとスタックオーバーフローを起こしてしまいます。
おそらく、再帰処理が原因だと思うのですが、
再帰させないようなQuicksortのアルゴリズム、
またquicksort並みの速度を持つソート法を教えていただけないでしょうか。

にしの 2004-08-08 06:38:22 No: 10280

クイックソートと同等のソート方法は、ヒープソート、マージソートだそうです。
ヒープソートの場合、スタックを必要としません。

ウォレス 2004-08-10 04:41:49 No: 10281

状況や環境に依存するでしょうが、
物理メモリ512Mの私のPCでは
N=50000000のIntegerでは無事ソートできました。
その２倍はしばらく待ったけど帰ってきませんでした＾＾；

あまり詳しくは無いのですが、クイックソートは逆整列に近いデータだと恐らく莫大なメモリを消費するのではないでしょうか。

にしの 2004-08-10 19:13:45 No: 10282

逆整列よりも、規則的に折り混ざった状態でしょう。
クイックソートの速度は、O(n*log(n))になりますが、一番遅い場合は、O(2*N)になったと思います。
再帰処理でなく、スタックを自前で用意してやるというのも手です。

ウォレス 2004-08-10 20:44:35 No: 10283

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;

deldel 2004-08-11 09:55:44 No: 10284

にしのさん、ウォレスさん
コメントありがとうございます。
しばらくネットにつなげない状況で、返信が遅れてしまいすみません。

ウォレスさんのコームソートを早速試させていただきました。
コードまで書いていただいて、ありがとうございます。
試してみたところ、クイックソートではエラーを起こしていた
配列の数でも無事にソートすることができました。
ただ、ウォレスさんもおっしゃっているように、
やはり速度がかなり遅くなってしまいます。

また、にしのさんの「スタックを自前で用意する」というのは
どういうことなのでしょうか？

クイックソートの速度のまま、
なんとかソートを行いたいと思っています。
何か方法があれば教えていただきたいと思います。

jok 2004-08-11 10:20:13 No: 10285

よく知りませんが、プロジェクト/オプション/リンカの最大スタックサイズを
大きくしたら駄目ですか？

ウォレス 2004-08-11 18:57:12 No: 10286

コームソート（コムソートの方が正しい表記？）はコード・理屈が極めて平易であるのにオーダが N LOG N である事から紹介しました。

ヒープソートは速度的にはコムソートと変わらないのではないでしょうか。
（試していません）

非再帰的なクイックソートが「C言語による最新アルゴリズム事典」に載っていますね。

スタックの代わりを自前で用意するので結局速度は遅くなる気がしますが・・・
（試していませんよ）

ウォレス 2004-08-12 22:04:10 No: 10287

非再帰型クイックソート
出典「C言語による最新アルゴリズム事典」

区間がTHRESHOLD未満で挿入ソートに切り替えるみたい＾＾；
速度は再帰型とかわらないみたい。
※挿入ソートを持ってくればさらに高速に。

const で以下を定義。
THRESHOLD =0;
STACKSIZE =32; (* たかだか Integer のビット数程度 *)

//----------------------

procedure nonrecursiveqsort( var a : array of Integer );
var
   i, j, left, right, p :Integer;
   leftstack  : array[0..STACKSIZE-1] of integer;
   rightstack : array[0..STACKSIZE-1] of integer;
   x, t :Integer;

begin

left := 0; right := N - 1; p := 0;

  while( true ) do  begin
    if (right - left <= THRESHOLD)then  begin
      if (p = 0)then  break;
      dec(p);
      left := leftstack[p];
      right := rightstack[p];
    end;
    x := a[(left + right) div 2];
    i := left;  j := right;

    while( true ) do  begin
      while (a[i] < x)do  inc(i);
      while (x < a[j])do  dec(j);
      if (i >= j)then  break;
      t := a[i];  a[i] := a[j];  a[j] := t;
      inc(i);  dec(j);
    end;

    if (i - left > right - j)then  begin
      if (i - left > THRESHOLD)then  begin
        leftstack[p] := left;
        rightstack[p] := i - 1;
        inc(p);
      end;
      left := j + 1;
    end else begin
      if (right - j > THRESHOLD)then  begin
        leftstack[p] := j + 1;
        rightstack[p] := right;
        inc(p);
      end;
      right := i - 1;
    end;
  end;

//inssort(N, a);

end;