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

本記事は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は、定数として暗記しておきましょう。

コムソートの計算量

平均計算時間	最悪計算時間	最良計算時間
Ｏ（n*log(n)）	Ｏ（ｎ²）	Ｏ（n*log(n)）

コムソートの計算量は「Ｏ（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を用いて作成したコムソートの関数です。
５行目のwhile文では、「gapが1で、かつ入れ替えが行われなくなるまでループを行う」という条件のもとループ処理を行っています。
７から９行目は、gapが１より小さくなった場合に１の整数に戻す処理を行っています。

特に重要となる、コムソートの中核とも言えるコードは１１〜１４行目にあたります。
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, 54, 94, 5, 35, 61, 49, 44]のリストを昇順に上手くソートできていることがわかります。

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

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

【あなたにオススメの記事】
・プログラミングで挫折しなくなる方法
・Pythonで画像サイズを一括変更！

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

超オススメのPC用品

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

リンク

外部モニターで２倍以上の効率化が見込めます！
安いものだと、たったの１万円前後なのでおすすめですよー！＼(^o^)／

リンク