アルゴリズムとデータ構造の要点メモ in ruby（Rubyで各種ソート）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f
キュー https://qiita.com/tsnb/items/588afe675ad830ff1fc6
二分木 https://qiita.com/tsnb/items/8aa4e1ebb24d87919c40
二分探索木 https://qiita.com/tsnb/items/8553f8c2effb4d704d9a
ヒープ https://qiita.com/tsnb/items/0fb42e62118d647b20d6

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

ソート（アルゴリズム）

要点

• 単純ソート O(n^2) 安定
• 選択ソート O(n^2) 安定でない
• バブルソート O(n^2) 安定
• 挿入ソート 探索の仕方次第：安定、選択・バブルより早いことが多い
  • 線形探索 O(n^2)
  • 二分探索 O(log n)
• クイックソート 平均計算量 O(n log n)、最悪ケース O(n^2)
• マージソート O(n log n)
• ヒープソート O(n log n) 安定でない

Arrayクラスを再オープン

単純ソート 実装

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

  def simple_sort!
    0.upto(self.size-1) do |i|
      i.upto(self.size-1) do |j|
        swap!(i, j) if self[i] > self[j]
      end
    end
  end
end

irb(main):356:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):357:0> a.simple_sort!
=> 0
irb(main):358:0> a
=> [1, 1, 3, 4, 5, 7, 8]

# ベンチマーク
require 'benchmark'
random = Random.new(10000)
list=10000.times.inject([]) { |res| res << random.rand(10000) }
# 以降、同じシードのlistを生成して使うので略する

irb(main):396:0> result = Benchmark.realtime do
irb(main):397:1* list.simple_sort!
irb(main):398:1> end
=> 4.6476910000201315

選択ソート 実装

単純ソートより気持ちだけ早い

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

  def selection_sort!
    setloop
    0.upto(@loop) do |i|
      min = i
      i.upto(@loop) do |j|
        min = j if self[min] > self[j]
        swap!(i, min) if j == @loop
      end
    end
    self
  end

private
  def setloop
    @loop = self.size - 1
  end
end

irb(main):545:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):546:0> a.selection_sort!
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):548:0> result = Benchmark.realtime do
irb(main):549:1* list.selection_sort!
irb(main):550:1> end
=> 4.492196999955922

バブルソート 実装

単純ソートより遅いンゴ、一回計測しただけだがまあ遅い

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

  def bubble_sort!
    setloop
    0.upto(@loop) do |i|
      1.upto(@loop-i) do |j|
        swap!(j-1, j) if self[j-1] > self[j]
      end
    end
    self
  end

private
  def setloop
    @loop = self.size - 1
  end
end

irb(main):133:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):134:0> a.bubble_sort!
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):138:0> result = Benchmark.realtime do
irb(main):139:1* list.bubble_sort!
irb(main):140:1> end
=> 5.747221999976318

挿入ソート 実装1

• 線形探索
• 非破壊

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

  def insertion_sort
    setloop
    @tmp = []
    self.each do |i|
      insertion_index = linear_search(i)
      @tmp.insert(insertion_index, i)
    end
    @tmp
  end

private
  def setloop
    @loop = self.size - 1
  end

  def linear_search(val)
    return 0 if @tmp.empty?
    @tmp.each_with_index do |v, i|
      return i if v > val
    end
    @tmp.size
  end
end

irb(main):308:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):309:0> a.insertion_sort
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):033:0> result = Benchmark.realtime do
irb(main):034:1* list.insertion_sort
irb(main):035:1> end
=> 1.3734219999751076

挿入ソート 実装2

二分探索を取り入れる

二分探索

前提：対象のデータの集まりがソート済み => 上のコードの@tmpはソート済み

探索したい値 = val

1. 探索したいデータの集まりの中央にあたる場所を求める array[0..99] => array[49]
2. val > array[49] => array[50..99]を探索対象に更新して1へ

と言う感じで探索する

class Array
  def insertion_sort
    @tmp = []
    self.each do |i|
      insertion_index = binary_search(i)
      @tmp.insert(insertion_index, i)
    end
    @tmp
  end

private
  def binary_search(val)
    return 0 if @tmp.empty?
    lower = 0
    upper = @tmp.size - 1
    while lower <= upper do
      middle = (upper + lower)/2
      if @tmp[middle] == val
        return middle
      elsif @tmp[middle] < val
        lower = middle + 1
      else
        upper = middle - 1
      end
    end
    lower
  end
end

線形探索より100倍くらい早くなった。

irb(main):031:0>  a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):032:0> a.insertion_sort
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):036:0> result = Benchmark.realtime do
irb(main):037:1* list.insertion_sort
irb(main):038:1> end
=> 0.019606999994721264

クイックソート

• 再帰で実装（スタックでもやりたいので後日追加する）
• pivotは左端を抜き出す

class Array
  def quick_sort
    tmp = self.dup
    quick_sort_rec(tmp)
  end

private
  def quick_sort_rec(array)
    return array if array.size < 2
    pivot = array.shift
    smallers, biggers = array.partition {|val| val < pivot }
    quick_sort_rec(smallers) + [pivot] + quick_sort_rec(biggers)
  end
end

お、挿入ソートの二分探索版より早いこれまで最速

irb(main):015:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):016:0> a.quick_sort
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):020:0> result = Benchmark.realtime do
irb(main):021:1* list.quick_sort
irb(main):022:1> end
=> 0.01457299996400252

マージソート

class Array
  def merge_sort
    merge_sort_rec(self.dup)
  end

private
  def merge_sort_rec(array)
    return array if array.size <= 1
    middle_index = array.size/2
    a = merge_sort_rec(array[0...middle_index])
    b = merge_sort_rec(array[middle_index..-1])
    merge(a, b)
  end

  def merge(a, b)
    res = []
    p "before: #{a} #{b} #{res}"
    loop_num = [a, b].map(&:size).inject(&:+)
    loop_num.times do #ここuntilにしないと無駄だ・・後で修正
      res <<
        case
        when a.empty? then b.shift
        when b.empty? then a.shift
        when a.first < b.first then a.shift
        else b.shift
        end
    end
    p "after: #{a} #{b} #{res}"
    res
  end
end

ランダムデータではクイックソートより遅い。

irb(main):200:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):201:0> a.merge_sort
"before: [3] [5] []"
"after: [] [] [3, 5]"
"before: [4] [3, 5] []"
"after: [] [] [3, 4, 5]"
"before: [8] [7] []"
"after: [] [] [7, 8]"
"before: [1] [1] []"
"after: [] [] [1, 1]"
"before: [7, 8] [1, 1] []"
"after: [] [] [1, 1, 7, 8]"
"before: [3, 4, 5] [1, 1, 7, 8] []"
"after: [] [] [1, 1, 3, 4, 5, 7, 8]"
=> [1, 1, 3, 4, 5, 7, 8]

# 計測時はpを除外
irb(main):234:0> result = Benchmark.realtime do
irb(main):235:1* list.merge_sort
irb(main):236:1> end
=> 0.027911000011954457

ヒープソート

ヒープにselfを全部突っ込んでから、先頭からdelしていくだけ

class Array
  attr_reader :list

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

  def heap_sort
    @list = [nil]
    add_all
    tmp = del_all
    tmp.compact
  end

  def add_all
    self.each do |val|
      add(val)
    end
  end

  def del_all
    @list.size.times.inject([]) do |res|
      res << del
    end
  end

  def add(val)
    @list.push(val)
    up_heap(@list.size - 1)
    @list
  end

  def del(index=1)
    return if index < 1
    @list.swap!(index, -1)
    tmp = @list.pop
    down_root(index)
    tmp
  end

private
  def up_heap(index)
    return if index <= 1
    parent_index = index/2
    if @list[parent_index] > @list[index]
      @list.swap!(parent_index, index)
      up_heap(parent_index)
    end
  end

  def down_root(index)
    child_index = small_child(index)
    return if child_index >= @list.size
    if @list[index] > @list[child_index]
      @list.swap!(index, child_index)
      down_root(child_index)
    end
  end

  def small_child(index)
    left = index*2
    right = index*2 + 1
    return left if @list[right].nil?
    return right if @list[left].nil?
    (@list[left] > @list[right])? right : left
  end
end

irb(main):069:0> a=[4,3,5,8,7,1,1]
=> [4, 3, 5, 8, 7, 1, 1]
irb(main):070:0> a.heap_sort
=> [1, 1, 3, 4, 5, 7, 8]

irb(main):074:0> result = Benchmark.realtime do
irb(main):075:1* list.heap_sort
irb(main):076:1> end
=> 0.06721399998059496

今回の実測