バブルソートとマージソートをRubyで実装してみました。

未経験エンジニアとして転職活動中に技術課題としてソートを2種類実装する課題がありました。
実際のそれぞれの処理速度の比較もあわせて、備忘録として残しておきます。

課題

wikipediaの「ソート」に記載されたソートから好きなソートを2種類実装し、好きな理由と合わせて回答してください。

ソートとは？

データを一定の規則に従って並べることです。
rubyではsortメソッドで数値を昇順に並べ替えることができますが、これを自分で実装してください。という課題です。
wikiを開いてもらえばわかりますが、ソートの種類はたくさんあります。
それぞれのソートに特徴があり、並べ替える数値の状態によっても処理速度が変わるものやどんな状態でも安定した処理速度のものなど色々あります。

バブルソート

本題のソートの実装に移ります。
バブルソートは隣り合った数字を比較し入れ替えることで値を大きい順、小さい順に整列させる方法です。
数値の入れ替えによって泡（バブル）がふわふわしているように見えることからこの名前がついたようです。

特徴

基本となるアルゴリズムが単純で実装が容易
処理速度は遅い
これをもとに比較交換順序を調整したより効率化されたアルゴリズムが作られている

実装

 def bubble_sort(array)
   element_size = array.length
   (0..element_size-1).each do |n|
     (0..element_size - n).each do |x|
       y = x+1
       if array[x].to_i > array[y].to_i
         array[x],array[y] = array[y], array[x]
       end
     end
   end
   p array
 end

処理する数値は配列で扱うことが前提です。
これは繰り返し処理などを行う時に扱いやすいデータのためです。
（配列以外で行う方法はわかりません。）
①配列に入れた入れ替える数値の要素数を求める
②要素数の数の分だけ比較処理を行う
といった流れです。

ポイント

配列の中のすべての要素に対して処理を行うための繰り返し処理です。

(0..element_size-1).each do |n|

隣接した数値を比較するためにxとyを定義しています。

(0..element_size - n).each do |x|

左右の数値を比較し、左側が大きければ入れ替える処理です。

if array[x].to_i > array[y].to_i
  array[x],array[y] = array[y], array[x]
end

マージソート

マージソートはソートする数値を半分ずつにきりわけ、最小単位になった時に大小比較を行い結合（マージ）し、これを繰り返す方法です。

特徴

処理速度が早く、ソートする数値の状態によらず安定した速度が実現できる
バブルソートと比べると処理が少し複雑になる

実装

def calc_half_point(array)
  return ((array.length / 2) +0.5).floor
end

  # 分解された配列を数値の低い順に結合する処理
def merge(array1, array2)
  array = []
  while (array1.length > 0) || (array2.length > 0) do
    if array1.length == 0
      array.push(array2.shift)
    elsif array2.length == 0
      array.push(array1.shift)
    elsif array1[0] > array2[0]
      array.push(array2.shift)
    else
      array.push(array1.shift)
    end
  end
  return array
end

  # 配列を最小になるまで分割し、定義したmergeメソッドで大小入れ替え後結合する処理
def merge_sort(array)
  if array.length == 0
    array = []
  elsif array.length == 1
    array = array 
  elsif array.length == 2
    array = [array.min, array.max]
  else
    half = calc_half_point(array)
    left = array.slice(0..half)
    right = array.slice(half + 1..array.length)
    left = merge_sort(left)
    right = merge_sort(right)
    array = merge(left, right)
  end
  return array
end

イメージできるとどう処理をすればいいかわかりやすかったので、wikiの数値の動きを一度確認してみてください。
https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

ポイント

配列の半分の要素数を計算する処理

半分に分けていくため、配列の要素数の真ん中の値を求める必要があります。
処理の中にまとめても良かったのですが、1つのメソッド内に1つの処理のほうがわかりやすいかと思いメソッドを作りました。

def calc_half_point(array)
  return ((array.length / 2) +0.5).floor
end

結合処理

並べ替えの行われた数値同士を比較し、結合する処理です。
並べ替えの行われた数値は昇順にならんでいるため、一番左の値同士を比較し、小さい方から新しい配列に格納を繰り返せば数値が昇順に並んだ新しい配列ができます。
例えば、[1,5,9]と[4,6,7]の場合
まず各配列の一番左の値を比較します。
1のほうが小さいので、1から取り出し別の配列に格納しておきます。
[5,9],[4,6,7]　　[1]
となり、また各配列の一番左の値を比較します。
5と4なので、4をとりだし、1を入れた配列に追加します。
[5,9],[6,7]　　[1,4]
これを配列が空になるまで繰り返すことをここでは結合と呼んでいます。
続けると、
[9],[6,7]　　　[1,4,5]
[9],[7]　　　　[1,4,5,6]
[9],[]　　　　　[1,4,5,6,7]
[],[]　　　　　[1,4,5,6,7,9]
ここまで来ると処理が終了です。
これをまた別の配列とあわせて同じ処理を行い、分割した配列が全て空になったときが処理の終了、つまり数値が並び替わった状態になります。

配列1,2を引数として与えます。
条件分岐として、片方の配列が空の場合は無条件でもう一方の配列から値を取り出します。（①、②）
配列1,2が空でない場合は比較を行います。（③、④）
小さい方の値をshiftメソッドで取り出し、新しい配列にpushメソッドで格納します。
これを両方の配列内の要素がなくなるまで処理を行います。(while部分の条件)

def merge(array1, array2)
  array = []
  while (array1.length > 0) || (array2.length > 0) do
    if array1.length == 0　　　　　　・・・①
      array.push(array2.shift)
    elsif array2.length == 0　　　　・・・②
      array.push(array1.shift)
    elsif array1[0] > array2[0]　　・・・③
      array.push(array2.shift)
    else　　　　　　　　　　　　　　　　・・・④
      array.push(array1.shift)
    end
  end
  return array
end

配列を最小単位へ分解する処理

配列の要素数によって分割する処理を分けています。

配列に要素がない場合（①）
何も処理する必要はありません。
配列の要素が1つの場合（②）
何も処理せず、そのままの配列を返します。
配列の要素が2つの場合（③）
並べ替えのメソッドを適用するまでもないので、[小,大]となるようにmin,maxメソッドを使って並べ替えた配列を返します。
配列の要素が3つ以上の場合（④）
要素数の半分の数を求める
配列を2つに分解する
左右の値に対して、同じ処理(merge_sort)を行わせる
最小単位になった後、結合処理を行う(merge)
結合した配列を返す

def merge_sort(array)
  if array.length == 0　　　　　　　　　　・・・①
    array = []
  elsif array.length == 1　　　　　　　　・・・②
    array = array 
  elsif array.length == 2　　　　　　　　・・・③
    array = [array.min, array.max]
  else　　　　　　　　　　　　　　　　　　　・・・④
    half = calc_half_point(array)
    left = array.slice(0..half)
    right = array.slice(half + 1..array.length)
    left = merge_sort(left)
    right = merge_sort(right)
    array = merge(left, right)
  end
  return array
end

処理速度の比較

benchMarkというライブラリを使って処理速度の比較を行いました。
10000の数値に対して、ランダムな値を0~10000の間で与え処理させました。

require 'benchMark'

bubble_speed = Benchmark.realtime do
  array = Array.new(10000){rand(10000)}
  bubble_sort(array)
end
puts bubble_speed

結果

bubble_speed = 6.148252000100911
merge_speed = 0.02221799991093576

約280倍程度マージソートの方が早いという結果でした。
wikiの最悪計算時間を確認してみました。
バブルソート：n^2 → (10000)^2
マージソート：nlogn →10000log10000 = 40000
これをもとにすると2500倍の差となるので、これから比べるとそこまで大きな差にならなかったです。
処理の書き方が適切でなく、思ったより時間がかかっているのか、
１００００個の並び替えだとそもそも差がこの程度しかでないのか。
ただnで書いてあるので、並べ替える個数はあまり関係してないように思えました。

まとめ

実装自体はできているのではないかと思います。
実装、解釈の間違いや、ご意見有りましたら是非コメントをお願いします。