クイックソートについて質問です。

質問

クイックソートについて勉強中なのですが、どうしても
理解できない箇所があるのですが

http://rararahp.cool.ne.jp/vc/algorithm/quickSort.txt
のクイックソートなんですが

後半の
quick(ll,r);
quick(l,rr);
は何を表してるのかどうも理解ができません、教えていただければ幸いです

回答No.1

sakusaker7 · ベストアンサー

while(l<=r){
while(A[l]<m) l++; // 左からm以下をさがす
while(A[r]>m) r--; // 右からm以上をさがす
if(l<=r){
w=A[l]; A[l]=A[r],A[r]=w; // 交換
l++;r--;
}
}
↑このループを抜けたところで、
ll ... r l ... rr
のように分割されます(m以下のグループとmを超えるグループ)。
で、ll ... r の部分と、l ... rr の部分は、きちんと整列は
されていません(ざっとpivot の値を基準にして選り分けただけ)。

そこで全体をきちんと整列するために、
今ざっくりと分けた二つの部分をそれぞれ整列してやります。
そのとき再帰的に呼び出しているので

quick(ll,r);
quick(l,rr);

のようになっているわけです。
適当な数の配列を紙にでも書きながら動きを追いかけてみるといいですよ。