Rubyで各種ソートアルゴリズム

きっかけ

なにやらRuby信者はアルゴリズムわからんバカばっかみたいなアレがあったので
バブルソートについて復習したら選択ソートと間違えて覚えてた事が発覚した

自分のポジ

Railsなんて使わんけど速度を気にしない用途ではRubyばっか書くので多分Ruby信者
MatzとDHHについてはノーコメント

バブルソート

bubblesort.rb

def bubble_sort(array)
  ary = array.dup
  pos_max = ary.size- 1

  (0...(pos_max)).each{|n|
    (0...(pos_max - n)).each{|ix|
      # 隣と比較して前が大きかったら後ろと交換
      iy = ix + 1
      ary[ix], ary[iy] = ary[iy], ary[ix] if ary[ix] > ary[iy] # 交換
    }
  }

  ary
end

require 'pp'

array = Array.new(10){ rand(100) } # [0..100) の整数 10個の配列を生成
pp array
pp (sorted_array = bubble_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

安定ソートであること、メモリ使用量が少ないことが選択ソートより優れている
ただし、メモリ使用量についてはそこまで詰める必要があるのかちょっと疑問

選択ソート

バブルソートにおいて、交換していくのではなく一時変数に貯めておいた方が交換回数が減り少し高速化する

selectionsort.rb

# 選択ソート
def selection_sort array
  ary = array.dup
  (0...ary.length).each{|ix|
    # 最小値を検索
    min_num = ary[ix]
    min_pos = ix
    ((ix+1)...ary.length).each{|iy|
      if min_num > ary[iy]
        min_num = ary[iy]
        min_pos = iy
      end
    }

    # 最小値と ix を交換する
    ary[ix], ary[min_pos] = min_num, ary[ix]
  }
  ary
end

require 'pp'

array = Array.new(10){ rand(100) } # [0..100) の整数 10個の配列を生成
pp array
pp (sorted_array = selection_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

Enumerble#min_by / max_byを使うと

selectionsort_ruby.rb

# ruby的な選択ソート
# min/max_with_indexが欲しい
def selection_sort_ruby ary
  ary_with_index = ary.zip(0...ary.length)
  (0...ary.length).each{|ix|
    # 最小値を探す
    min = ary_with_index[ix..-1].min_by{|num, ix| num}

    # 最小値と ix を交換する
    ary_with_index[ix][0], ary_with_index[min[1]][0] = min[0], ary_with_index[ix][0]
  }
  ary_with_index.map(&:first)
end

require 'pp'

array = Array.new(10){ rand(100) } # [0..100) の整数 10個の配列を生成
pp array
pp (sorted_array = selection_sort_ruby(array))
puts "is_sorted: #{array.sort == sorted_array}"

クイックソート

ある値(ピボット)より大きいか小さいかで分割していく方法

# クイックソート

# ピボットの選択が大事
# いろいろやり方はあるが今回は平均値を選択

def average(ary)
  avg = ary.sum / ary.length
end

def average_sample(ary, count)
  average(ary.sample(count))
end

# 定数は適当
def select_pivot ary, size
  if size < 4096
    average(ary)
  else
    average_sample(ary, 16)
  end
end

# クイックソート本体
def qsort ary
  if ary.size == 1
    return ary
  elsif ary.size == 2
    return ary if ary[0] < ary[1]
    return [ary[1],ary[0]]
  end

  pivot = select_pivot ary, ary.length
  left, right = ary.partition{|num| num < pivot }
  qsort(left) + qsort(right)
end

require 'pp'

array = Array.new(10){ rand(100) } # [0..100) の整数 10個の配列を生成
pp array
pp (sorted_array = qsort(array))
puts "is_sorted: #{array.sort == sorted_array}"

マージソート

半分に分割していく方法

mergesort.rb

def merge_sort array
  return array if array.length == 1
  return [array.min, array.max] if array.length == 2

  half = array.length / 2

  left = merge_sort array[0..(half-1)]
  right = merge_sort array[half..-1]

  lv = left.shift
  rv = right.shift
  Array.new(array.size){
    if lv < rv
      lv.tap{ lv = left.shift || right[-1] || rv }
    else
      rv.tap{ rv = right.shift || left[-1] || lv }
    end
  }
end

require 'pp'

array = Array.new(10){ rand(100) } # [0..100) の整数 10個の配列を生成
pp array
pp (sorted_array = merge_sort(array))
puts "is_sorted: #{array.sort == sorted_array}"

ヒープソート

疲れたので特徴だけ

ヒープ木という木構造を構築してそこからデータを取り出すことでソートする不安定ソート

整列済みデータにいくつかの整列してないデータを追加する場合高速にできる特徴を持ってたはず(うろ覚え

ただし、ランダムアクセスになるので理論上の速度より遅くなる事もある

いいわけ

アルゴリズムの違いによる速度差なんてお金とマシンの力でどうにかすりゃいいんだよ
という富豪的な考えはRubyでプログラム書く時の根底にあると思う

ちなみに

Array#sortの実装はqsort_s もしくは qsort_r もしくは クイックソートっぽい