[アルゴリズム] クイックソートの実装（解説編）

ソートアルゴリズムで最も高速といわれているクイックソートにチャレンジしてみます。 でも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 クイックソートの考え方は？ ※このサイトの説明が分かりやすかった。

関連記事

アルゴリズム学習

• 解説
• Javascript
• PHP
• Python
• Shell
• AWK
• C言語
• Go言語
• Ruby