データ構造とアルゴリズム：comb（コムソート）

重要度低い

combというのはクシという意味なので、クシを溶かしていくように、くしの幅を小さくしていくようにソートを行う手法。 Gap 7/1.3 = 5というのは櫛の幅だと考え、１番目と５番目の数値を入れ替えて入れ替える必要がなければ戻し、Gapを狭くして同じ作業を行なっていく。Gapの7というのは配列の個数。　

前回の幅である５を分子として使用して、次の櫛の幅で同じ入れ替え確認作業を行う。

最終的に幅が１で入れ替え確認作業を行い、SwapフラグがFalseになったまま周回が終わるまで入れ替え作業を行なっていく。

from typing import List
import random

def comb_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    gap = len_numbers
    swapped = True

    while gap != 1 or swapped:
        gap = int(gap / 1.3)
        if gap < 1:
            gap = 1

        swapped = False

        for i in range(0, len_numbers - gap):
            if numbers[i] > numbers[i + gap]:
                numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
                swapped = True

    return numbers

# nums = [2, 9, 1, 8, 7 ,3, 5]
nums = [random.randint(0, 1000) for i in range(10)]

print(comb_sort(nums))


[169, 197, 217, 245, 328, 383, 555, 692, 824, 983]