Edited at

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

More than 3 years have passed since last update.


きっかけ

なにやらRuby信者はアルゴリズムわからんバカばっかみたいなアレがあったので

バブルソートについて復習したら選択ソートと間違えて覚えてた事が発覚した


自分のポジ

Railsなんて使わんけど速度を気にしない用途ではRubyばっか書くので多分Ruby信者

MatzとDHHについてはノーコメント


バブルソート


bubblesort.rb

def bubble_sort(array)

ary = array.dup
pos_max = ary.length - 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 = 10.times.map{ 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 = 10.times.map{ 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{|num, ix| num}
end

require 'pp'

array = 10.times.map{ 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.reduce(&:+) / ary.length
end

def average_sample(ary, count)
average(count.times.map{ary.sample})
end

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

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

pivot = select_pivot ary, ary.length
left = []
right = []
ary.each{|num|
if num < pivot
left << num
else
right << num
end
}
qsort(left) + qsort(right)
end

require 'pp'

array = 10.times.map{ 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.length.times.map{
if lv < rv
lv.tap{ lv = left.shift || right[-1] || rv}
else
rv.tap{ rv = right.shift || left[-1] || left}
end
}
end

require 'pp'

array = 10.times.map{ 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 もしくは クイックソートっぽい

https://github.com/ruby/ruby/blob/trunk/util.c