クイックソート

質問

クイックソートのアルゴリズムの問題で
9 1 8 5 3 4 2 6 7
と上記のようなデータ列を昇順に整列するときに
9 1 8 5 3 4 2 6 7
6 1 8 5 3 4 2 9 7
6 1 2 5 3 4 8 9 7
とここで詰まってしまうんですけどどうしたら昇順に導けますか？

回答No.2

sakusaker7

あー、すみません。
ちょっと読み違えてました。

> 9 1 8 5 3 4 2 6 7
まずここから、右端の7をpivotに選択しました。

9 1 8 5 3 4 2 6
6 1 8 5 3 4 2 9 >=7 の 9 と <7 の6を交換
6 1 2 5 3 4 8 9 >=7 の 8 と <7 の2を交換

とここまではいいのですよね?
ここまでで、7以上と7未満との分割は終わったので、
次は分割されたそれぞれの部分に対して同じ手順を繰り返します。
つまり、

6 1 2 5 3 4
と
8 9 7
とを別々のものとして処理します。

[7未満の配列][7以上の配列]

と分かれているので、それぞれが昇順になれば
全体としても昇順に並んでいる。

ということなんですけどこういう説明でわかりますか?

クイックソート
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

で紹介されているやり方でいうと、
質問者さんは

int k=partition(a,i,j,a[p]);

この partition の呼び出しから返ってきたところまではできたので、続いて
quickSort(a,i,k-1);
quickSort(a,k,j);
という二つの手順をすればよいのです。

お礼

お返事のほう遅れて申し訳ないですm(__)m
大変よく理解できました。ありがとうございます。

回答No.1

sakusaker7

>どうしたら昇順に導けますか？
それ以前にどういう手順で処理したらこういう結果になるのか見当がつきません。
pivot をどう選択して、どのように分割したのか説明してもらえませんか?

補足

まずpivotを7にします。そしてleftPtrが7よりでかいとき、そしてrightPtrが7より小さいときに入れ替えしてやるという方法でやりました。