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

Pocket
LINEで送る
GREE にシェア
LinkedIn にシェア

ソートアルゴリズムで最も高速といわれているクイックソートにチャレンジしてみます。
でもwikipediaの解説を見てみると、最も高速と言われながらも、データの並びや数によっては、必ずしも早いわけではないそうだ。
少し冷めてしまいそうなアルゴリズムだが、今までと何が違うかを考えながら仕様を確率してみたいと思う。

ソートのしかた

サンプル乱数(配列)

[10,2,12,7,16,8,13,1]

手順

1、ピポットを抽出
※厳密でなくてもいいが、大体、配列の要素数の中間を取得すると良い

10,2,12,[7],16,8,13,1

 →7を選択
 
2、ピポットの左側を端から比較していき、ピポット値よりも大きいものを選択

(10),2,12,7,16,8,13,1

10 > 7
 
3、ピポットの右側を端から比較していき、ピポット値よりも小さいものを選択

(10),2,12,7,16,8,13,(1)

7 < 1 4、2番と3番の数値(10と1)を入れ返る

(1),2,12,7,16,8,13,(10)

5、左右それぞれ、次の数字を比較する。

1,2,(12),7,16,8,13,10

 ※左側が12が7より大きく、右側は7よりも小さい数が無いので、12と7を入れ替える

1,2,(12),(7),16,8,13,10

 ※左側が12が7より大きく、右側は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つの要素になるまで処理を行い、全て完了したらソートされている状態になる。

完了

1,2,7,8,10,12,13,16

処理する配列がいくつも分割されるため、while文の構造で排他的処理をする必要がある。

個人的には少しややこしいアルゴリズムだと感じた。

参考リンク

wikipedia|クイックソート

http://algorithmbeginner.blogspot.jp/2012/12/blog-post_25.html


クイックソートの考え方は?

※このサイトの説明が分かりやすかった。

クイックソート

解説

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です