Pythonでソートアルゴリズムの再発明をしてみる: コムソート

概要

• Pythonでソートアルゴリズムを再発明してみるだけ
• 今回はコムソートについて
• 参考サイトのサンプルコードをできるだけ見ずに実装する
• とりあえず昇順ソートのみの対応とする

コムソートの概要

• バブルソートでは要素が1ずつしか移動しないので遅い…せや！離れた要素同士で入れ替えしたろ！ -> コムソート
• バブルソートを改良したシンプルなアルゴリズムだが、条件が良ければバブルソートとは比較にならないくらい速い
• 離れた要素同士で入れ替えを行うことで「だいたいソートされた状態」にし、その後バブルソートと同等の処理を行って「完全にソートされた状態」にするみたいな感じ
• 不安定ソート

基本的な手順

1. ソート対象のリストのサイズをもとにギャップ（比較する要素同士の距離）を決める（2回目以降は前回のギャップをもとにする）
2. 先頭要素とギャップ分離れた要素を比較し、大小関係が逆なら入れ替える
3. 比較する要素両方を1つ右にずらしながら手順2を繰り返す。ギャップ分離れた要素の位置がリストの末尾を超えたら繰り返しを止める
4. 手順1〜3を繰り返す。繰り返すたびにギャップは小さくなっていく
5. ギャップが1になったら、隣り合う要素同士で比較、入れ替えを行う。入れ替えが発生しなくなるまで繰り返す
6. 手順5で入れ替えが発生しなくなったらソート完了

ソース

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))

参考サイト

• https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88
• https://en.wikipedia.org/wiki/Comb_sort