クイックソート :C#でLet’sデルゴリ(データ構造とアルゴリズム)

クイックソートです。

名前にクイックつける勇気。見習いたい。

そして名前の通りたいていの場合一番早い。

概要

昇順の場合

基準となる値(ピボット)を決める。

基準値より小さいものを基準値の前方に、大きいものを後方へ移動

基準値の前方、後方それぞれで同じことを繰り返す。

分割統治方の一種(重要)。

そのうち動的計画法と合わせて解説する日が来るかも。。。

新たに配列を生成しないタイプの内部ソート。

安定ではない。

計算時間

O(nlogn)

自分的イメージ;マージソートと同じく徐々に範囲を狭めながら再帰的に繰り返すので階層はlogn段階。各段階において合計だいたいn回くらいの比較を行うのでnlogn。

自分的にはすごく納得いく考え方なんだけど大体だし図とかないとわかりづらいので参考程度で。そのうち図とかつけたいですね。

最悪時はO(n^2)

式的にはマージソートと同じ平均計算量だが基本的にマージソートより早い。

しかし最悪時がものすごく遅い。(ソート済みの配列で常に左端をピボットとして指定した時など)

ただ、ピボットの選び方を工夫することでたいてい避けられる。

実装

実装してみた。

言語はC#。再帰的。

実際に前回のマージソートやシェルソートと比較してみましたがちゃんと早かったです。

再帰を使った実装は簡潔ですが、Nが大きくなるとスタック領域が足りなくなることがあるので注意が必要です。

複雑になったとしても再帰を使わないほうがメモリには優しいんですって。

今まで自分でコード書いててWhileループってそんなに使わなかったんですがアルゴリズム系のコードを調べると結構使っててへ〜って思いました。ちゃんと使うと便利ですね。というかfor文でやろうとしたら全然できなかったです。

使い分けていこうと思いました。

終わりです。

ではまた。

にほんブログ村 IT技術ブログへ
スポンサーリンク

コメントをどうぞ

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