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

2017年2月7日

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

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 クイックソートの考え方は? ※このサイトの説明が分かりやすかった。

関連記事

アルゴリズム学習

このブログを検索

プロフィール

自分の写真
町田市, 東京都, Japan
プログラミングとサーバーを心の底から楽しむクリエーターです。 経営者であり、開発者でもありますが、得意としているのは、アイデア創出。

ブログ アーカイブ

QooQ