Javaで実装するカクテルソート（双方向バブルソート）のプログラム

カクテルソート（Cocktail Sort）は、バブルソートを改良した整列アルゴリズムの一つで、「双方向バブルソート」や「シェーカーソート」とも呼ばれます。通常のバブルソートが配列を一方向にのみ走査するのに対し、カクテルソートは前方向と後方向を交互に走査する点が最大の特徴です。

まず前方向のパスでは、隣り合う要素を比較しながら大きい値を配列の末尾側へ移動させます。続く後方向のパスでは、逆に小さい値を配列の先頭側へ移動させます。この往復操作を、交換が一度も発生しなくなるまで繰り返すことで、配列全体が昇順に整列されます。

この手法により、配列の終盤に位置する小さな要素でも、1回の後方向パスで先頭付近まで一気に移動できるため、通常のバブルソートよりも少ないパス回数でソートが完了するケースがあります。

カクテルソートの処理の流れ

1. 未ソート範囲の先頭から末尾へ向かって隣接要素を比較し、順序が逆なら交換する（最大値が末尾へ移動）。
2. 未ソート範囲の末尾を1つ縮める。
3. 未ソート範囲の末尾から先頭へ向かって同様に比較・交換する（最小値が先頭へ移動）。
4. 未ソート範囲の先頭を1つ広げ、交換が発生しなくなるまで1〜3を繰り返す。

Javaによる実装例

public class Demo{
    void Cocktail_Sort(int my_arr[]){
        boolean swapped = true;
        int start = 0;
        int end = my_arr.length;
        while (swapped == true) {
            swapped = false;
            for (int i = start; i < end - 1; ++i) {
                if (my_arr[i] > my_arr[i + 1]) {
                    int temp = my_arr[i];
                    my_arr[i] = my_arr[i + 1];
                    my_arr[i + 1] = temp;
                    swapped = true;
                }
            }
            if (swapped == false)
                break;
            swapped = false;
            end = end - 1;
            for (int i = end - 1; i >= start; i--) {
                if (my_arr[i] > my_arr[i + 1]) {
                    int temp = my_arr[i];
                    my_arr[i] = my_arr[i + 1];
                    my_arr[i + 1] = temp;
                    swapped = true;
                }
            }
            start = start + 1;
        }
    }
    void print_values(int my_arr[]){
        for (int i = 0; i < my_arr.length; i++)
            System.out.print(my_arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args){
        Demo my_object = new Demo();
        int my_arr[] = { 6, 8, 34, 21, 0, 1, 98, 64, 6};
        System.out.println("ソート前の配列: ");
        for (int i = 0; i < my_arr.length; i++)
            System.out.print(my_arr[i] + " ");
        System.out.println();
        my_object.Cocktail_Sort(my_arr);
        System.out.println("カクテルソート適用後の配列: ");
        my_object.print_values(my_arr);
    }
}

実行結果

ソート前の配列: 
6 8 34 21 0 1 98 64 6
カクテルソート適用後の配列: 
0 1 6 6 8 21 34 64 98

計算量と特徴

カクテルソートの平均計算量および最悪計算量はO(n²)で、バブルソートと同じオーダーです。一方、すでに整列済みの配列に対しては交換が発生せずに1周で処理が終了するため、最良ケースではO(n)となります。また、等しい値の相対的な順序が保たれる「安定なソート」である点もバブルソートと共通しています。