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

名前

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

本文

非再帰型クイックソート
出典「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;

←解決時は質問者本人がここをチェックしてください。

戻る