takulab

前回の Rubyでアルゴリズム 第01回 ~バブルソート編~ に続いて、今回はクイックソートに取り組んでいく。

クイックソートって？

例のごとくWikipediaを見てみると、

クイックソートは、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

最良計算量および平均計算量はO(n log(n))>である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。 安定ソートではない。

wikipedia:クイックソート

どういう風にソートを行うのかはこれだけでは分かりにくいが、安定ソートでないといった特徴を把握した上で活用すれば役立ちそうだと推測できる。

具体的なソートの方法は？

簡単に説明すると、

1. 要素の中から軸(ピポット)を1つ決める
2. その軸より小さい値と大きい値のグループに分ける
3. それぞれのグループで1.2を実行する
4. それ以上は分割できない状態になればソーティング終了

という方法によりソーティングが可能である。

ちなみに軸の選び方は
 (1)完全にランダムに選ぶ
 (2)適当な３つの値の中央値を選ぶ
といった様々な変形パターンが存在する。

実装

今回の実装は様々な戦略のうち、軸をランダムに選ぶ方法で実装を行った。

class Array
  def sort
    quickSort(self, 0, self.length-1)
  end
 
  def quickSort array, left, right
    if left > right then
      pi = partition(array, left, right)
      quickSort(array, left, pi-1)
      quickSort(array, pi+1, right)
    end
  end
 
  def partition array, left, right
    p = left + rand(right - left)
    self[p], self[right] = self[right], self[p]
    store = left
    (left..right-1).each do |i|
      if array[i] <= array[right] then
        self[i], self[store] = self[store], self[i]
        store += 1
      end
    end
    self[store], self[right] = self[right], self[store]
    return store
  end
end

まとめ

• 最良時、平均時には O(n log(n)) でソートが可能。
• 軸を選択するときに常に左端、または右端を選んでしまうと最悪時になり、O(n^2)の計算時間がかかる
• 軸の選択方法、要素が少なくなると挿入ソートに切り替える等の亜種が存在する

追記 2010/07/28

よく考えるとquicksortとpartitionの引数arrayは必要なさそう...。

そのうちもう一度考える。