import random
def comb_sort(lst):
# ギャップの計算に使うための初期値
gap = len(lst)
# 入れ替えが発生したかどうかのフラグ。ギャップが1の場合に参照する
swap_occurred = False
# 手順全体を繰り返すためのループ
# まずはギャップが1になるまで繰り返す(ギャップを縮めながらループする)
# ギャップが1になっても、入れ替えが発生しなくなるまでは繰り返す必要があるため、
# ギャップが1の場合はswap_occurred(入れ替えが発生したかどうか)も見ている
# ギャップが1で、かつ入れ替えが一度も発生しなくなったらループを抜ける(= ソート完了)
while gap > 1 or swap_occurred:
swap_occurred = False
# ギャップを求める。1.3で割るのが理想的とされているみたい
gap = int(gap / 1.3)
# 計算結果が0になったらギャップを1にする
# これにより、ギャップが1になってからもループが継続する(swap_occurredがFalseになるまでは)
if gap < 1:
gap = 1
# リストを走査するためのループ
# 比較、入れ替え対象の要素がリストの範囲外になったらループを抜ける
i = 0
size = len(lst)
while i+gap < size:
if lst[i] > lst[i+gap]:
# 大小関係が違うため入れ替え
lst[i], lst[i+gap] = lst[i+gap], lst[i]
# swap_occurredにTrueを設定するのはここだけなので、swap_occurredは
# 「ギャップが特定の値の間、入れ替えが一度でも発生したかどうか」という意味の値になる
# ギャップが2以上の場合は無視されるが、ギャップが1の時にループを継続するかどうかがここで決まる
swap_occurred = True
i += 1
lst = list(range(10))
random.shuffle(lst)
print("ソート前: " + str(lst))
comb_sort(lst)
print("ソート後: " + str(lst))