ソートのアルゴリズムを実装する（１）

数値のリストをソートするアルゴリズムを実装する

バブルソート

概要

最初から順に、隣り合う２つの数値を比べて大きい方を右、小さい方を左になるように入れ替える。次に大きい方の数値と次の数値を比べて順になるように入れ替える。これを繰り返して最後まで行ったら、一番最後に最大の数値がくる。これを一巡とし、次のサイクルでは、一番最後の値が確定しているのでその前までの数値を入れ替えていく。このサイクルを要素数-1回繰り返すという方法。 アルゴリズムが単純なため実装が容易

実装

def buble array
  (array.length - 1).times do |i|　　//要素数ー１回繰り返す
    (1 ... (array.length - i)).each do |j|       //二個目の数値から確定していない最後の数値まで
      array[j], array[j - 1] = array[j - 1], array[j] if array[j] < array[j - 1]　　//現在の値が左の値よりも小さければ入れ替える
    end
  end
end

たったの七行で実装できました。 ループの回数がちょっとややこしいですね。 ..や...で表されるrangeオブジェクトで引っかかったので別記事にまとめます。

選択ソート

概要

リストの中から最小値を探し出し、その値と最初の値を入れ替える。次に残った値の中で最小の値を２番めの値と入れ替える。これを最後まで繰り返すという方法。 この方法もアルゴリズムが単純で実装が容易

実装

def selection array
  length = array.length
  (length - 1).times do |i|　　//最後から二番目の値が確定するまでループ
    min = i
    ((i + 1) ... length).each do |j|　　// 並びが確定していない数値から最小値を探す
      min = j if array[min] > array[j]
    end
    array[i], array[min] = array[min], array[i] if min != i　　//最小値を前に詰める
  end
end

こちらも１０行で実装できました

挿入ソート

概要

ソートされた範囲を一つずつ増やす方法。 最初に、二番目までの数値を順に整列する。三番目の数値が二番目の数値よりも小さい場合、正しい順になるように挿入する。これを繰り返して、ソートされた範囲を増やしていく。

実装

実装にあたって問題となるのは挿入という動作だ。 rubyにはsliceとdeleteいうメソッドがあり、挿入という動作を再現するのは簡単だが、アルゴリズムの学習なので今回は使用しない。 そのため、後ろから数値を一つずつずらしていくという方法を取る。 また、正しい位置を判断する事が必要なため、最後の数値から順に、挿入したい数値と比べて大きければ一つ後ろの位置に数値をコピーし、小さければ一つ後ろの位置に挿入したい数値をコピーするという方法を取る。

例： 以下のリストで次に２を正しい位置に挿入したい。 [1,3,4,2] まず４のほうが大きいので４を一つ後ろの位置にコピーする。 [1,3,4,4] 次に３のほうが大きいので３を一つ後ろの位置にコピーする。 [1,3,3,4] 次に１のほうが小さいので２を一つ後ろの位置にコピーする。 [1,2,3,4] この動作を繰り返してソートされた範囲を増やす。

def insert array
  (1 ... array.length).each do |i|　　//リストの二番目の数値から最後までループ
    tmp = array[i]
    if array[i - 1] > tmp　　//現在の値の位置を動かす必要があるか
      j = i
      while (tmp < array[j - 1]) && (j > 0)　　//後ろから順に比較・値をコピーする
        array[j] = array[j -1]
        j -= 1
      end
      array[j] = tmp　　//正しい位置に値を挿入
    end
  end
end

今回は少し長めの１３行 コードにすると挿入って感じしないですね。