【アルゴリズムの勉強】Rubyで挿入ソートを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてRubyで挿入ソートを実装する。

挿入ソートとは

挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。

挿入ソート - Wikipedia


Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count
DESC, ASC = 1, 2

def insertion_sort(arr, number_of_elements, order)
  for i in 1..(number_of_elements - 1)
    target = arr[i]
    j = i
    if order == ASC
      while (j > 0) && (arr[j - 1] > target)
        arr[j] = arr[j - 1]
        j += -1
      end
    elsif order == DESC
      while (j > 0) && (arr[j - 1] < target)
        arr[j] = arr[j - 1]
        j += -1
      end
    end
    arr[j] = target
  end
  return arr
end

asc_sorted_arr = insertion_sort(arr, number_of_elements, ASC)
p asc_sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
desc_sorted_arr = insertion_sort(arr, number_of_elements, DESC)
p desc_sorted_arr
# => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]

参考文献