コムソートとは?【アルゴリズム紹介・Pythonによる実行】

本記事はPythonのコムソートについて、学生エンジニアが初心者の方へ向けて優しく解説しています。ソートとは数値や文字列を昇順や降順に並べ替えることで、プログラミングを学ぶ上で非常に重要な道具です。ソートの中でも極めて重要なコムソートを一緒に学習しましょう!

コムソートとは?

コムソートは、バブルソートの改良版です。
バブルソートについて、理解が曖昧な方は下の記事紹介していますので、御覧ください。

バブルソートとは?コードやアルゴリズムを初心者向けに解説

コムソートは、英語で書くと「combsort」と書き、「comb」とは「髪をとくクシ」という意味があります。
クシという言葉の通り、コムソートはクシのように並べ替えていくアルゴリズムです。

詳しくは下の動画で理解してください。
英語で語られていますが、どのようにソートをしているかを理解してみてください。


いかがでしたでしょうか。
コムソートはバブルソートとは違い、初期段階で離れた要素を比較します。
しかし、最終的にはバブルソートと同様に隣接した値同士で比較をするアルゴリズムです。

少し複雑なので、手順を整理します。

1. リストの総数を1.3で割り、gapを求める
2. 先頭からの要素とgap分離れた要素の大小関係を比較して入れ替える
3. 2の比較を最後まで繰り返す
4. gapを更に1.3で割り、新しいgapを求める。
5. 2〜3を繰り返す
6. gapが1になれば、入れ替えがなくなるまで比較を行う

ここで用意されている1.3は、定数として暗記しておきましょう。

コムソートの計算量

平均計算時間最悪計算時間最良計算時間
O(n*log(n))O(n2O(n*log(n))

コムソートの計算量は「O(n*log(n))」です。よって、コムソートは安定性のない整列アルゴリズムと言えます。

コムソートの欠点

コムソートはメモリの使用率も低く、非常に優れた整列アルゴリズムです。
しかし、安定性のない点が唯一の欠点と言えます。

Pythonコード

def comb_sort(nums):
    gap = len(nums)
    swap = True

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

        for i in range(0, len(nums) - gap):
            if nums[i] > nums[i + gap]:
                nums[i], nums[i + gap] = nums[i + gap], nums[i]
                swap = True
    return nums

上記がPythonを用いて作成したコムソートの関数です。
5行目のwhile文では、「gapが1で、かつ入れ替えが行われなくなるまでループを行う」という条件のもとループ処理を行っています。
7から9行目は、gapが1より小さくなった場合に1の整数に戻す処理を行っています。

特に重要となる、コムソートの中核とも言えるコードは11〜14行目にあたります。
gapを上手く利用して、Pythonでコムソートを実現しています。

コムソートの実行例

def comb_sort(nums):
    gap = len(nums)
    swap = True

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

        for i in range(0, len(nums) - gap):
            if nums[i] > nums[i + gap]:
                nums[i], nums[i + gap] = nums[i + gap], nums[i]
                swap = True
    return nums


if __name__ == '__main__':
    nums = [20, 54, 94, 5, 35, 61, 49, 44]
    print(comb_sort(nums))
【実行結果】
[5, 20, 35, 44, 49, 54, 61, 94]

実行結果から、
20行目で宣言した[20, 54, 94, 5, 35, 61, 49, 44]のリストを昇順に上手くソートできていることがわかります。

コムソートの理解が曖昧な方へ

下の動画もコムソートについて、非常にわかりやすい動画です。
繰り返し見てみてくださいね。


ということで、本記事はコムソートについて、Pythonのコードを使用しながらまとめました。
最後まで読んでいただき、ありがとうございました\(^o^)/

超オススメのPC用品

PCを操作する上で、トラックボールマウスが非常におすすめです!
僕も感動したこのマウスを、騙されたと思って使ってみてください!(^^)

外部モニターで2倍以上の効率化が見込めます!
安いものだと、たったの1万円前後なのでおすすめですよー!\(^o^)/

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です