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