バブルソート、選択ソートをRubyで作る

目的

ソートアルゴリズムについて、実際にコードを書いてまとめてみる。
言語はRubyでやってみます。

ソートについて

ソートは、入力として与えられた数字を小さい順に並び替えること。

バブルソート

バブルソートは、「数列の右から左に向かって、隣り合う2つの数字を比較して入れ替える」操作を繰り返し行う。数列に対して、処理を1周行えば、一番小さい数字が配列の１番目に入る。要素の数だけ周回することで並び替えることができる。

bubble.rb

def bubble_sort(array)
  length = array.length
  (length - 1).times do |round|
    (length - 1 - round).times do |n|
      if array[length - n - 1] < array[length - n - 2]
        smaller = array[length - n - 1]
        array[length - n - 1] = array[length - n - 2]
        array[length - n - 2] = smaller
      end
    end
  end
  array
end

array = [2, 3, 13, 7, 8, 9, 11, 1, 5]
bubble_sort(array)　#=> [1, 2, 3, 5, 7, 8, 9, 11, 13]

バブルソート関数の中身
・配列arrayの長さをlengthで取得(1行目)
・(length - 1)ラウンドで入れ替えが終了する(2行目)
・n回目のラウンドでは、(length - n - 1)回比較して、入れ替える処理を行う(3行目)
・左の数値が右の数値よりも大きい場合は入れ替える(4~7行目)
大小比較の回数は、(length - 1) + (length - 2) + ・・・+ 1 = (length)^2 / 2　になる。

選択ソート

選択ソートは、「数列の中から最小値を検索し、左端の数字と入れ替える」という操作を繰り返す。

selection.rb

def selection_sort(array)
  length = array.length
  (length - 1).times do |round|
    min = round + 1
    round.upto(length - 1) do |n|
      if array[n] < array[min]
        min = n
      end
    end
    min_number = array[min]
    array[min] = array[round]
    array[round] = min_number
  end
  array
end

最小値のインデックス番号を取得して、検索した後に入れ替える。
バブルソートと同じで、大小比較する回数は (length)^2 / 2　になる。

後書き

次は、挿入ソート、ヒープソート、マージソート、クイックソート、バケットソートについてもまとめようと思います。