Pythonでカクテルソート（双方向バブルソート）を実装する方法

この記事では、カクテルソート（Cocktail Sort）をPythonで実装する方法について解説します。サンプルコードと実行結果を通じて、アルゴリズムの仕組みをわかりやすく説明していきます。

カクテルソートとは

カクテルソートは「双方向バブルソート」とも呼ばれるソートアルゴリズムです。通常のバブルソートが一方向のみの走査を行うのに対し、カクテルソートはリストを左右両方向に交互に走査しながら要素を並べ替えていく点が特徴です。

アルゴリズムの手順

1. 左から右への走査

まず配列を左から右へ走査します。走査中は隣接する要素同士を比較し、条件を満たしていれば値を入れ替えます。この処理により、配列内で最も大きい値が末尾に移動します。

2. 右から左への走査

次に、配列を逆方向（右から左）へ走査し、同じく隣接要素の比較と入れ替えを行います。これにより、最も小さい値が先頭に移動します。

この2つの走査を、入れ替えが発生しなくなるまで繰り返すことで、配列全体が昇順にソートされます。

Pythonでの実装例

# カクテルソート関数
def cocktailSort(a):
    n = len(a)
    flag = True
    start = 0
    end = n - 1

    while flag:
        # 前回の反復結果をリセット
        flag = False

        # 左から右へ走査
        for i in range(start, end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                flag = True

        # 交換が一度も発生しなければソート完了
        if not flag:
            break

        # フラグをリセット
        flag = False

        # 末尾の要素は確定済みなので範囲を狭める
        end = end - 1

        # 右から左へ走査
        for i in range(end - 1, start - 1, -1):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                flag = True

        # 先頭の要素は確定済みなので範囲を狭める
        start = start + 1


# メイン処理
a = [2, 5, 4, 3, 8, 3, 4, 6]
cocktailSort(a)
print("Sorted array is:")
for i in range(len(a)):
    print(a[i], end=" ")

実行結果

Sorted array is:
2 3 3 4 4 5 6 8

コードのポイント

• flag変数： 各パスで交換が行われたかどうかを記録します。交換がなければ配列はすでにソート済みのため、ループを抜けて処理を終了します。
• start / end変数： 各パスが完了するごとに、先頭または末尾の要素が確定するため、走査範囲を狭めて無駄な比較を減らしています。
• 双方向の走査： 往路で最大値を末尾へ、復路で最小値を先頭へ移動させることで、通常のバブルソートよりも効率的にソートできます。特に「端に近い小さな要素（タートル）」の移動が速くなるのが利点です。

すべての変数はローカルスコープで宣言されており、各反復での参照関係は上記のコードから確認できます。

まとめ

この記事では、Pythonを使ってカクテルソートを実装する方法を学びました。カクテルソートはバブルソートを改良したシンプルなアルゴリズムであり、双方向の走査によって効率を向上させられる点が魅力です。計算量は平均・最悪ケースでO(n²)となるため大規模データには不向きですが、ソートアルゴリズムの基礎理解には最適な題材といえます。