ソートアルゴリズムで最も高速といわれているクイックソートにチャレンジしてみます。
でもwikipediaの解説を見てみると、最も高速と言われながらも、データの並びや数によっては、必ずしも早いわけではないそうだ。
少し冷めてしまいそうなアルゴリズムだが、今までと何が違うかを考えながら仕様を確率してみたいと思う。
ソートのしかた
サンプル乱数（配列）
[10,2,12,7,16,8,13,1]
手順
１、ピポットを抽出
※厳密でなくてもいいが、大体、配列の要素数の中間を取得すると良い
10,2,12,[7],16,8,13,1
→7を選択
２、ピポットの左側を端から比較していき、ピポット値よりも大きいものを選択
(10),2,12,7,16,8,13,1
10 > 7
３、ピポットの右側を端から比較していき、ピポット値よりも小さいものを選択
(10),2,12,7,16,8,13,(1)
7 < 1
４、２番と３番の数値（10と1）を入れ返る
(1),2,12,7,16,8,13,(10)
５、左右それぞれ、次の数字を比較する。
1,2,(12),7,16,8,13,10
※左側が12が７より大きく、右側は7よりも小さい数が無いので、12と7を入れ替える
1,2,(12),(7),16,8,13,10
※左側が12が７より大きく、右側は7よりも小さい数が無いので、12と7を入れ替える
1,2,(7),(12),16,8,13,10
6.左辺と右辺が交差する位置に来たら、左右を分けて、それぞれの配列に対して同じ処理を繰り返す
交差した位置を元に、配列を分ける。（今回は下の位置）
1,2,7 | 12,16,8,13,10
分割された配列を1番にもどってそれぞれ処理する
[1,2,7]
[12,16,8,13,10]
上記の手順で全ての分割された配列が１つの要素になるまで処理を行い、全て完了したらソートされている状態になる。
完了
1,2,7,8,10,12,13,16
処理する配列がいくつも分割されるため、while文の構造で排他的処理をする必要がある。
個人的には少しややこしいアルゴリズムだと感じた。
参考リンク
wikipedia|クイックソート
http://algorithmbeginner.blogspot.jp/2012/12/blog-post_25.html
クイックソートの考え方は？
※このサイトの説明が分かりやすかった。
関連記事
アルゴリズム学習
