クイックソート

Posted on Sunday, September 7th, 2014 20:38:34

クイックソートとは

今回は”言うは易し、書くは難し”なアルゴリズムです。クイックソートは、ある要素を軸に分割を繰り返しながら整列を行うアルゴリズムで、分割統治法と一種です。

データの要素数を n とすると、平均計算量が O(n log n) で、ランダムなデータに対して最も高速なソートアルゴリズムであるとされています。開発者のアントニー・ホーアは、あまりの早さに”quick”のワードを付けることにしたそうです。本当かどうか知りませんが。

そんな高速なアルゴリズムを C で組もうとすると、なかなかに複雑になります。そらで書けなかったし。。再起的アルゴリズムなので、フィボナッチ数列ぐらいを理解して組めるようになったら、クイックソートを書いてみると良いかもしれません。

サンプル

ソースプログラム

実行結果

ソート関数の解説

やっていることは割りと単純で、ピボットとなる要素を取得して、それを軸に再帰的にこのアルゴリズムを実行するだけです。ピボットの取得が複雑なのは雑なオーバーフロー対策で、 ((left + right) / 2) と思って良いでしょう。

while ブロックの中ではピボットの値以上の集まりと、ピボットの値以下の集まりに分割しています。訳が分からなくなったら、ソートの過程を出力してみると良いでしょう。プログラムの見た目ほど複雑な動きはしていません。

冒頭で平均計算量は O(n log n) と述べましたが、対して最悪計算量は O(n²) となります。このパターンは、分割を行った結果、1:(n – 1) になってしまったパターンです。要するにピボットを偏って選びまくってしまった場合ですね。

また、再帰処理であるため、log2(N) に比例するメモリを使用します。ソートアルゴリズムの選び方は “時間と空間のトレードオフ” なんて言いますが、はえーからクイックソート使っとけ、って話にもならないってわけですね。ではでは。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

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