Rubyでソートアルゴリズム

0.概要

ソートについて色々と調べた上で、クイックソートとヒープソートを実装した。

1.クイックソート

ピボットを基準として、値の大小で2つに分割していく方法。
O(n log n)で計算でき、他のソートと比べると高速なソート法。
ただし、データの並びやデータの数によって計算量が変化する。最悪計算量はO(n**2)となる。

実装は以下の通り。

quick_sort.rb

class Array
  def quick_sort
    return self if size <= 1
    pivot = choice_pivot
    smallers, biggers = partition { |item| item < pivot }
    push(pivot)
    smallers.quick_sort.concat([pivot]).concat(biggers.quick_sort)
  end

  def choice_pivot
    self[0] >= self[1] ? delete_at(0) : delete_at(1)
  end
end

ピボットの選択によって計算量が変わるらしく、今回は2つの数値からより大きいものをピボットにした。

2.ヒープソート

ヒープという木構造を構築すると、必ず根が最大の値になる。
これを利用してソートしていくのがヒープソート。
あまり実装例を見かけないので、チャレンジという意味も込めて試してみた。

実装は以下の通り。

heap_sort.rb

class Array
  def build_heap(arr)
    parent = (arr.length - 1) / 2
    node_cnt = parent

    until node_cnt < 0
      l_child = 2 * parent + 1
      r_child = l_child + 1

      if arr[r_child] && arr[r_child] >= arr[l_child] && arr[r_child] > arr[parent]
          arr.swap!(r_child, parent)
          parent = r_child
      elsif arr[l_child] && arr[l_child] > arr[parent]
          arr.swap!(l_child, parent)
          parent = l_child
      else
        node_cnt -= 1
        parent = node_cnt
      end
    end
    arr
  end

  def swap!(a, b)
    self[a], self[b] = self[b], self[a]
  end

  def heap_sort
    arr = self.dup
    res = []
    until arr.empty?
      heap = build_heap(arr)
      heap.swap!(-1, 0)
      res.unshift(heap.delete_at(-1))
    end
    res
  end
end

3.実行速度について

実行速度を測りたいという意図もあり、以下のテストコードを書いた。

quick_sort_test.rb

class QuickSortTest < Minitest::Test
  def setup
    num = 10000
    @arr = []
    num.times { @arr << rand(num)  }
  end

  def test_quick_sort
    assert_equal @arr.quick_sort, @arr.sort
    run_time = Benchmark.realtime { @arr.quick_sort }
    p run_time
  end
end

heap_sort_test.rb

class HeapSortTest < Minitest::Test
  def setup
    num = 10000
    @arr = []
    num.times { @arr << rand(num)  }
  end

  def test_quick_sort
    assert_equal @arr.heap_sort, @arr.sort
    run_time = Benchmark.realtime { @arr.heap_sort }
    p run_time
  end
end

結果は以下の通り。

クイックソート　0.029008000157773495
ヒープソート　4.9474329999648035

圧倒的にクイックソートのほうが速い...
ヒープソートも書き方を変えたらもっと速くなるのだろうか。

4.終わりに

アルゴリズムはほぼ未学習の状態だったので、よい勉強になった。