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

Ruby アルゴリズム

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

シェルソートとは

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した[3][4] 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。

シェルソート - Wikipedia

Rubyで実装

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

def shell_sort(arr, number_of_elements)
  h = 1
  # 効率を上げるため、121, 40, 13, 4, 1となるような間隔を作る
  while h < (number_of_elements / 9)
    h = h * 3 + 1
  end
  while h > 0
    for i in h..(number_of_elements - 1)
      j = i - h
      target = arr[i]
      while j >= 0 && arr[j] > target
        arr[j + h] = arr[j]
        j += -h
      end
      arr[j + h] = target
    end
    h = h / 3
  end
  return arr
end

sorted_arr = shell_sort(arr, number_of_elements)
p sorted_arr
# => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]

参考文献、参考リンク