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は必要なさそう...。

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

Rubyを学びつつアルゴリズムも復習し直そうということで、1日1記事を目標にやっていけたらと思っている。記念すべき初回である今回はバブルソートを実装。

バブルソートって？？

Wikipediaにはこんな風に書いてある。

バブルソート(bubble sort)は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n^2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。

wikipedia:バブルソート

簡単に言うと、隣り合う要素を順々に比較して要素の順序を入れ替えるという操作を全ての要素に行うことで整列を行うといったとこだろうか。

実装

Arrayクラスのsortメソッドをオーバーライドしてみた。

class Array
    def sort
        unsorted_length = self.length-2
        begin
            unsorted = false
            (0..unsorted_length).each do |i|
                if(self[i] > self[i+1])
                    unsorted = true
                    self[i], self[i+1] = self[i+1], self[i]
                end
            end
            unsorted_length -= 1
        end while (unsorted)
    end
end

今回Rubyを書いていて、

self[i], self[i+1] = self[i+1], self[i]

Cだと、一時変数なんかを使って、

tmp = self[i]
self[i] = self[i+1]
self[i+1] = tmp

この辺が、Rubyが直感的に理解しやすいコードが書けると言われている所以なのかと想像。

バブルソートのまとめ

少し脇道に反れたが、最後にまとめ。

• アルゴリズムが簡単で、実装も楽
• 最悪時は計算時間がO(n^2)かかってしまう

何かの処理時間を測定したいときに便利。

Benchmarkモジュールを利用する。

require "benchmark"
puts Benchmark::CAPTION
puts Benchmark.measure{
    process()
}

require "benchmark"
N = 1000
array = Array.new( N )
(0..N).each do |i|
    array[i] = rand(10000)
end
puts Benchmark::CAPTION
puts Benchmark.measure{
    array.sort
}

ちなみに単位は秒。

user     system      total        real
0.000000   0.000000   0.000000 (  0.000158)

参考サイト

benchmark – Rubyリファレンスマニュアル