sortアルゴリズムにおけるstack操作

質問

あるサイトさんを参考にしてstackを用いたソートアルゴリズムを作っていたのですが、先ほど偶然完成してしまいました。
スタックの動きがよく分からないまま出来てしまったので何だか腑に落ちません・・・
（参考にしたサイトさんも解説がありませんでした）
よろしければ(1)～(3)の部分の解釈を教えていただけないでしょうか？
よろしくお願いしますm(_ _)m

void sort(int A[], int a, int b)
/* 昇順整列 */
{
int i, j;
int pvt; /* 枢軸 */
int sp = 0; /* スタックポインタ */
int left_stc[64], right_stc[64];

while(FOREVER){
pvt = a[b], i = a, j = b-1;
while(i < j){
while(A[i] < pvt) i++;
while(A[j] > pvt) j--;
if(i < j){
swap(&A[i], &A[j]); i++; j--;
}
}
if(A[i] > pvt) swap(&A[i], &A[b]);

(1)if(a < i-1){
left_stc[sp] = i;
right_stc[sp++] = b;
b = i-1;
continue;
}

(2)if(i+1 < b){
a = i+1;
continue;
}

(3)else{
if((sp--) <= 0)
break;
a = left_stc[sp];
b = right_stc[sp];
continue;
}

}
}

回答No.3

rabbit_cat · ベストアンサー

つまり、このプログラムは普通の再帰で書けば、
void qsort(int A[], int a, int b)
{
　pvt = A[b] より小さい要素、大きい要素に分割する処理。この結果、
　A[0]～A[i-1]は、pvt以下の要素、
　A[i]～A[b]は、pvt以上の要素 になる

　qsort(A[], a, i-1);　… (1)の部分
　qsort(A[], i, b);　… (2)の部分と(3)の部分
}
てなっているわけです。

(1)の部分でが、
left_stc[sp] = i;
right_stc[sp++] = b;
で、次に呼び出す予定の
qsort(A[], i, b);
に相当する引数をスタックに記憶しておいて、
b = i-1;
continue;
で、
qsort(A[], a, i-1);
を呼び出します。

で、(3)の部分で、
(1)でスタックに記憶していた引数を
if((sp--) <= 0) break;
a = left_stc[sp];
b = right_stc[sp];
で思い出して、
continue;
で
qsort(A[], i, b);
を呼び出しています。

具体的に短い配列A[]について、スタックの動きを紙に書き出してみるといいと思います。

ちなみに、最初の再帰呼び出し
qsort(A[], a, i-1);
のところでは、現在の状態を記憶しておかなければなりませんが（質問のプログラムでは、実際には、現在の状態そのももではなくて、次に行わなければいけないことを覚えています）、
２番目の再帰呼び出し
qsort(A[], i, b);
は、末尾再帰になっているので、現在の状態をスタックに記憶する必要はありません。

お礼

実は紙、#ifdef等で動きを調べることもやってみたのですが挫折してしまいました（汗）
rabbit_catさんの回答が無ければ自分の中でこの問題は迷宮入りになってました....；；

自分の中でもう一度、整理してみます。
ありがとうございましたm(_ _)m

回答No.2

rabbit_cat

あんまり良く見てないけど、
ぱっと見た感じ、クイックソートですかね。

(1) pvtより小さい要素だけをソート（再帰呼び出し）
(2) pvtより大きい要素だけをソート（再帰呼び出し）
(3) 再帰呼び出しの後始末をして呼び出し元に戻る。
　（普通の明示的な再帰呼び出しを使ったプログラムで言えば、returnに相当する処理）

お礼

回答ありがとうございます。参考になります。

right_stc[sp++] = b;

a = left_stc[sp];

この2つの処理の意味がまだよくわかりませんが・・・。

回答No.1

phoenix343

えーと
これってコンパイルしてみましたか。

ざっと見た感じ、コンパイルエラーになる箇所があるみたいだけど。
変数で、A[]、aとあるみたいですが普通、こんな変数名はつけないですよ、、

お礼

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

この質問を書き込んだパソコンにはコンパイラがなくて
別のパソコンから目で見て写したソースなので間違ってるところ
（pvt = a[b]は　正しくはpvt = A[b]ですね。）
があるかもしれませんが、
コンパイラがあるパソコンではちゃんとコンパイルでき、
実行もきちんとできました。

変数名はあとから変えます。読みづらくてすいません…