クイックソートってなんだ 戻る
クイックソートってわかりにくい。
まずは実践。
こんな数字の羅列があります。
6 9 2 3 1 7 5 8 4
これをクイックソートで並び替える
まず基準を選ぶ
一番左を選ぶ(今回は)。
6
9 2 3 1 7 5 8 4
基準の右側にある数の羅列に対して右側と左側から基準の数字よりも小さい、大きいを探していく。
左側からは基準より大きい数字を、右側からは基準より小さい数字を。
探していく仮定で「ここまでは調べましたよ~」っていう基準として『|』を使います。基準値の色はオレンジで交換する値は赤。こんな感じ
6
|9 2 3 1 7 5 8 4|
基準より大きい数字と小さい数字を探します。
この数字の羅列でこの操作を行うと9と4がヒットします。
6
|
9
2 3 1 7 5 8
4
|
こいつらを交換。
6
|
4
2 3 1 7 5 8
9
|
交換した内側の数字の羅列に対して同じことを行います。(|が内側に移動)。
次は7と5がヒット。
6
4 2 3 1 |
7
5
| 8 9
交換
6
4 2 3 1 |
5
7
| 8 9
ここで、もう|が重なってしまいました。
6
4 2 3 1 5 | 7 8 9
ここで最後に交換した数字の左側と基準を交換します。(5と7を交換。結果は5が左側)
5 4 2 3 1
6
| 7 8 9
ここで一巡目終了。
さて数列を見てみると
5 4 2 3 1 6 7 8 9
となっているのがわかる。基準となった6の右側に6より大きい数字、左側に6より小さい数字が集まっている。
3つのグループになってるのがわかる。どんなグループかというとおおげさに書くと
5 4 2 3 1 6 7 8 9
こんな感じ。
二巡目に突入。
一巡目と同じように基準を選び、同じ処理を繰り返す。ただし、この処理をすべてのグループに対して行う(ここでは3つのグループに行えってことです)
5
4 2 3 1
6
7
8 9
真ん中のグループは数字が一つしかないので終了。
さて問題発生です。左側グループの5 4 2 3 1に処理ができません。基準となる5より大きい数字がないため、小さい数字と交換ができないのです。こんなとき(基準となる数字がそのグループ内で一番大きい数字)は一番右に移動させます。そしてこのグループからは抜け出し、新しいグループとなります。
4 2 3 1
5
6
7
8 9
↓
4 2 3 1
5
6
7
8 9
さて、処理を再開しましょう。
4
2 3 1
5
6
7
8 9
はい。また上のような状況になりました。同じように4をグループの一番右に移動させ、グループから外しましょう。
2 3 1
4
5
6
7
8 9
↓
2 3 1
4
5
6
7
8 9
さて処理を再開しましょう。
……………………………………………ってかもうわかりましたね。以上のような処理を続けていれば最終的にはソートされた9つのグループができあがります。
この方法は基準値を一番左で設定して行っていますが、この基準値を選ぶ方法はいろいろあります。(基準値を選ぶ方法で交換方法も変わりますが…)
ここで言いたいのは、クイックソートは基準値を選んで、左側と右側から順に小さい値、大きい値を探し交換、更に交換後は基準値と交換、グループを増やしていく、ということです。(最後はグループをすべて合体)。それだけ覚えてればいけます。ちなみに基準値はピボットって呼ばれます。最後は丸投げですが、以上です。
参考：クイックソート