Rubyで学ぶソートアルゴリズム

はじめに

本記事は「Rubyで学ぶアルゴリズムとデータ構造」勉強会用の資料として書かれたものです。

ソートとは、データの集合を一定の規則に従って並べ替えるものです。
Rubyには Array#sort が存在し、これで配列の要素を楽々ソートできます。

ary = [ "d", "a", "e", "c", "b" ]
ary.sort  #=> ["a", "b", "c", "d", "e"]

このように言語側でアルゴリズムを用意してくれているとはいえ、中身を知っておいて損はないです。基本的なソートアルゴリズムを押さえることで、より高度なアルゴリズムとデータ構造への理解がしやすくなります。

そこで本記事では下記ソートアルゴリズムをRubyで実装することで理解を深めていきます。

• 選択ソート
• バブルソート
• マージソート
• クイックソート

ソートとなると順序性担保や計算量の話題がどうしても出てきますが、本記事では詳しく扱いません。ソートを学ぶ理由や計算量などについてはソートを極める！ 〜 なぜソートを学ぶのか 〜が詳しいのでこちらを参考ください。

テストデータと想定解

arr = [5, 6, 7, 4, 1, 3, 4, 9, 14, 41, 341, 15, 55, 51, 554, 9, 154]
p arr.sort  #=> [1, 3, 4, 4, 5, 6, 7, 9, 9, 14, 15, 41, 51, 55, 154, 341, 554]

選択ソート

Wikipediaから引用です。

1. 1番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する（1番目の要素までソート済みとなる）
2. 以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する
3. すべての要素がソート済みになったら処理を終了する

一番大きな要素を掴んで、それを整頓されていない部分の最後尾へ持っていくことでソートされるんですね！
何から何までWikipedia頼りですが、要素の並べ替えのイメージはwikipediaを見てください。(もしくは別サイトを見てください)

arr = [5, 6, 7, 4, 1, 3, 4, 9, 14, 41, 341, 15, 55, 51, 554, 9, 154]

def get_min_value_with_index(arr, n, current_idx)
  min_value, min_index = arr[current_idx], current_idx
  (current_idx...n).each do |i|
    min_value, min_index = arr[i], i if min_value > arr[i]
  end
  return [min_value, min_index]
end

def main(param)
  arr = param.dup
  n = arr.size
  n.times do |i|
    min_value, min_index = get_min_value_with_index(arr, n, i)
    arr[min_index], arr[i] = arr[i], min_value
  end
  return arr
end

result = main(arr)

p result.join(' ') == arr.sort.join(' ')  #=> true

バブルソート

Wikipediaより

要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

2連番を比較し順番を入れ替える処理を整頓されていない部分で何度も行うことで最終的にはソートされるんですね！
これもWikipediaのアニメーションが参考になります。

arr = [5, 6, 7, 4, 1, 3, 4, 9, 14, 41, 341, 15, 55, 51, 554, 9, 154]

def main(param)
  arr = param.dup
  n = arr.size
  n.times do |i|
    (n-(i+1)).times do |j|
      arr[j], arr[j+1] = arr[j+1], arr[j] if arr[j] > arr[j+1]
    end
  end
  return arr
end

result = main(arr)

p result.join(' ') == arr.sort.join(' ')  #=> true

マージソート

Wikipediaより

1. データ列を分割する（通常、二等分する）
2. 分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする
3. 二つのソートされたデータ列（1個であればそれ自身）をマージする

分割して、その中でソート(このソートは再帰的に行う)。ソートされた配列の先頭を比較し、小さい方から配列に詰め直していくんですね！
これもWikipediaのアニメーションが(以下略)

arr = [5, 6, 7, 4, 1, 3, 4, 9, 14, 41, 341, 15, 55, 51, 554, 9, 154]

def merge(arr_first, arr_second)
  res = []
  until arr_first.empty? || arr_second.empty? do
    res << (arr_first[0] < arr_second[0] ? arr_first.shift : arr_second.shift)
  end
  if arr_first.empty? then
    res.concat(arr_second)
  elsif arr_second.empty? then
    res.concat(arr_first)
  end
  return res
end

def main(arr)
  return arr.dup if arr.empty? || arr.size == 1
  left = 0
  right = arr.size
  mid = (left + right) / 2
  res_first = main(arr[left...mid])
  res_second = main(arr[mid...right])
  return merge(res_first, res_second)
end

result = main(arr)

p result.join(' ') == arr.sort.join(' ')  #=> true

クイックソート

Wikipediaより

1. ピボットの選択：適当な値（ピボットという）を境界値として選択する
2. 配列の分割：ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
3. 再帰：分割された区間に対し、再びピボットの選択と分割を行う
4. ソート終了：分割区間が整列済みなら再帰を打ち切る

マージソートは一度配列を別に定義する必要がありましたが、クイックソートは途中で配列を保持する必要がありません。
これも(以下略)

ここでのピポットは先頭の値にしています。

arr = [5, 6, 7, 4, 1, 3, 4, 9, 14, 41, 341, 15, 55, 51, 554, 9, 154]

def quick_sort(arr, first, last)
  left = first + 1
  right = last
  while left < right do
    left += 1 while arr[left] < arr[first] && left < last
    right -= 1 while arr[right] >= arr[first] && right > first
    arr[left], arr[right] = arr[right], arr[left] if left < right
  end

  arr[first], arr[right] = arr[right], arr[first] if arr[first] > arr[right]

  quick_sort(arr, first, right-1) if first < right - 1
  quick_sort(arr, right+1, last) if right + 1 < last
end

def main(param)
  arr = param.dup
  quick_sort(arr, 0, arr.size - 1)
  return arr
end

result = main(arr)

p result.join(' ') == arr.sort.join(' ')  #=> true

おわりに

WikipediaのGIFアニメーション最強👆

参考

• アルゴリズムを、はじめよう
• 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本