カクテルソートとは？Javaでの実装方法と動作原理をわかりやすく解説

カクテルソート（Cocktail Sort）は、バブルソートを改良した整列アルゴリズムの一つで、「双方向バブルソート」や「シェーカーソート」とも呼ばれます。

通常のバブルソートでは、要素を左から右への一方向にのみ走査し、大きい値から順に配列の末尾へ確定させていきます。一方、カクテルソートでは左から右、右から左へと交互に双方向の走査を行う点が大きな特徴です。これにより、配列の末尾側だけでなく先頭側にも素早く整列済みの領域が形成され、バブルソートよりも効率が向上する場合があります。

カクテルソートのJavaプログラム例

以下は、カクテルソートをJavaで実装したサンプルプログラムです。

public class Demo{
    static int temp;
    static void Cocktail(int a[], int n){
        boolean swap = true;
        int begin = 0,i;
        int end = n - 1;
        while (swap) {
            swap = false;
            for (i = begin; i < end; ++i){
                if (a[i] > a[i + 1]){
                    temp = a[i];
                    a[i]=a[i+1];
                    a[i+1]=temp;
                    swap = true;
                }
            }
            if (!swap)
            break;
            swap = false;
            for (i = end - 1; i >= begin; --i){
                if (a[i] > a[i + 1]){
                    temp = a[i];
                    a[i]=a[i+1];
                    a[i+1]=temp;
                    swap = true;
                }
            }
            ++begin;
        }
    }
    public static void main(String[] args) {
        int my_arr[] = {34, 78, 90, 32, 67, 12, 1, 0, 95};
        Cocktail(my_arr, my_arr.length);
        System.out.println("The sorted array is ");
        for (int i = 0; i < my_arr.length; i++)
        System.out.print(my_arr[i]+" ");
        System.out.println();
    }
}

実行結果

The sorted array is
0 1 12 32 34 67 78 90 95

プログラムの動作の流れ

このアルゴリズムの処理は、以下の2つのフェーズを交互に繰り返すことで進みます。

1. 前方への走査（左から右）

まず、バブルソートと同様にループを左から右へ実行し、隣接する要素同士を比較します。左側の値が右側の値より大きければ、両者を交換します。この1回目の走査が完了すると、配列内の最大の要素が末尾に配置されます。

2. 後方への走査（右から左）

次に、直前の走査で整列済みとなった末尾の要素を除外し、今度は右から左へループを実行します。ここでも隣接する要素同士を比較・交換を行い、最小の要素が配列の先頭に配置されていきます。

この往復の走査を、交換が一切発生しなくなるまで繰り返すことで、配列全体が昇順に整列されます。プログラム中の begin と end は、それぞれ整列済みとなった領域を除外するための境界インデックスとして機能しています。

計算量について

• 平均計算量・最悪計算量： O(n²)
• 最良計算量： O(n)（すでに整列済みの場合）
• 安定性： 安定なソート（等しい値の相対的な順序が保たれる）

カクテルソートはシンプルで理解しやすいアルゴリズムですが、大規模なデータには不向きであり、実務ではクイックソートやマージソートなどが使われることが一般的です。ただし、ソートアルゴリズムの学習や、ほぼ整列されたデータの処理においては有用な手法といえます。