アルゴリズム？プログラミング。 - シェルソート
シェルソート(shell sort)です。挿入ソートの進化版ということです。間隔をあけて比較して挿入していきます。
挿入操作とは挿入部分を一時的に同じ数字にしておき最後に順番通りになるように入れ替え(挿入)してやる操作をします。
上記参考サイトのコードにprint()を入れて各箇所についてどのように出力しているかがわかるようなコードにしています。
nums = [54, 32, 2, 76, 39, 47, 99, 15]
gap = len(nums) // 2
print(f"最初 gapは{gap}")
while gap > 0:
for i in range(gap, len(nums)):
tmp = nums[i]
j = i
print(f"tmpは {tmp}")
while j >= gap and nums[j - gap] > tmp:
nums[j] = nums[j - gap]
print(f"挿入場所を作る {nums}")
print(f"jは {j}")
j -= gap
print(f"jは {j}")
nums[j] = tmp
gap //= 2
print(f"工程終了 gapは {gap}")
print("最後")
print(nums)これを出力すると、
最初 gapは4
tmpは 39
挿入場所を作る [54, 32, 2, 76, 54, 47, 99, 15]
jは 4
jは 0 ・・・ この後whileを抜け数字の入れ替えをしています。
tmpは 47
tmpは 99
tmpは 15
挿入場所を作る [39, 32, 2, 76, 54, 47, 99, 76]
jは 7
jは 3 ・・・ この後whileを抜け数字の入れ替えをしています。
工程終了 gapは 2
tmpは 2
挿入場所を作る [39, 32, 39, 15, 54, 47, 99, 76]
jは 2
jは 0 ・・・ この後whileを抜け数字の入れ替えをしています。
tmpは 15
挿入場所を作る [2, 32, 39, 32, 54, 47, 99, 76]
jは 3
jは 1 ・・・ この後whileを抜け数字の入れ替えをしています。
tmpは 54
tmpは 47
tmpは 99
tmpは 76
工程終了 gapは 1
tmpは 15
tmpは 39
tmpは 32
挿入場所を作る [2, 15, 39, 39, 54, 47, 99, 76]
jは 3
jは 2 ・・・ この後whileを抜け数字の入れ替えをしています。
tmpは 54
tmpは 47
挿入場所を作る [2, 15, 32, 39, 54, 54, 99, 76]
jは 5
jは 4 ・・・ この後whileを抜け数字の入れ替えをしています。
tmpは 99
tmpは 76
挿入場所を作る [2, 15, 32, 39, 47, 54, 99, 99]
jは 7
jは 6 ・・・ この後whileを抜け数字の入れ替えをしています。
工程終了 gapは 0
最後
[2, 15, 32, 39, 47, 54, 76, 99]
となります。
少しシェルソートが分かりにくいのが間隔をあけて比較していくのですが、
for i in range(gap, len(nums)):
gapから、リストの長さ分について順番にやっていくのですが、イメージ的に先頭から間隔をあけて調べていくイメージがあります。
実際はgapは例えば"4"から始まれば、リストの4 番目以降の数字を調べていくので、イメージとは少し違うところがあります。"4"から始まって順番に5、6 ・・・と順次数字が変わっていき、その数からgapを引いた数と比較して、数字のずらす操作、まず同じ数字にしておいて保存しておいた数字を適切な場所に挿入してやるということになります。
少し違った形、whileの条件ではなく、"if"で条件分岐させます。
nums = [54, 32, 2, 76, 39, 47, 99, 15]
gap = len(nums) // 2
while gap > 0:
for i in range(gap, len(nums)):
tmp = nums[i]
j = i
while j >= gap:
if nums[j - gap] > tmp:
nums[j] = nums[j - gap]
else:
break
j -= gap
nums[j] = tmp
gap //= 2
print(nums)