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

2017/02/07

テクノロジー プログラミング 特集

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

関連記事

アルゴリズム学習

人気の投稿

このブログを検索

ごあいさつ

このWebサイトは、独自思考で我が道を行くユゲタの少し尖った思考のTechブログです。 毎日興味がどんどん切り替わるので、テーマはマルチになっています。 もしかしたらアイデアに困っている人の助けになるかもしれません。

ブログ アーカイブ