シェルソートを実装してみます。
概要
シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell’s method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[ 2 ]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した[ 3 ][ 4 ] 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。
シェルソート – Wikipedia
サンプルコード
import random
data_len = 10
data = random.sample(range(1, 42), data_len)
print(data)
def shell_sort(collection):
# Marcin Ciura's gap sequence
# https://stackoverflow.com/questions/2539545/fastest-gap-sequence-for-shell-sort
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
for gap in gaps:
for i in range(gap, len(collection)):
j = i
while j >= gap and collection[j] < collection[j - gap]:
collection[j], collection[j -
gap] = collection[j - gap], collection[j]
j -= gap
print(collection)
return collection
shell_sort(data)実行結果（例）
[8, 27, 1, 2, 39, 36, 14, 19, 4, 30]
[8, 27, 1, 2, 4, 36, 14, 19, 39, 30]
[4, 27, 1, 2, 8, 36, 14, 19, 39, 30]
[4, 27, 1, 2, 8, 30, 14, 19, 39, 36]
[4, 1, 27, 2, 8, 30, 14, 19, 39, 36]
[1, 4, 27, 2, 8, 30, 14, 19, 39, 36]
[1, 4, 2, 27, 8, 30, 14, 19, 39, 36]
[1, 2, 4, 27, 8, 30, 14, 19, 39, 36]
[1, 2, 4, 8, 27, 30, 14, 19, 39, 36]
[1, 2, 4, 8, 27, 14, 30, 19, 39, 36]
[1, 2, 4, 8, 14, 27, 30, 19, 39, 36]
[1, 2, 4, 8, 14, 27, 19, 30, 39, 36]
[1, 2, 4, 8, 14, 19, 27, 30, 39, 36]
[1, 2, 4, 8, 14, 19, 27, 30, 36, 39]
