C++で学ぶカクテルソート（双方向バブルソート）の仕組みと実装方法

カクテルソート（Cocktail Sort）は、バブルソートの変種の一つです。通常のバブルソートでは常に左から右へ走査を行い、各パスで最大の要素を配列の末尾へ移動させ、次のパスで2番目に大きい要素を後ろから2番目の位置へ配置していきます。

一方、カクテルソートは両方向を交互に走査する点が特徴です。まず左から右へ走査して大きな要素を右端へ送り、次に右から左へ走査して小さな要素を左端へ送ります。この往復動作が「カクテルシェイカー」のように見えることから、この名前が付いています。双方向に走査することで、「ウサギ（端に近い小さな値）」や「カメ（末尾近くにある小さな値）」と呼ばれる要素の移動が速くなり、バブルソートより効率が改善される場合があります。

それでは、アルゴリズムを見ながらその考え方を理解しましょう。

アルゴリズム

cocktail(array, n)

Begin
    flag := true
    start := 0, end := n-1
    while flag が true の間、繰り返す
        flag := false
        // 左から右へ走査（バブルソートと同様）
        for i in range start to end-1, do
            if arr[i] > arr[i+1], then
                arr[i] と arr[i+1] を交換
                flag := true
            end if
        done
        // 交換が一度も発生しなければソート完了
        if flag が false ならば
            break
        end if
        flag := false
        end := end - 1
        // 右から左へ走査
        for i in range end-1 down to start, do
            if arr[i] > arr[i+1], then
                arr[i] と arr[i+1] を交換
                flag := true
            end if
        done
        start := start + 1
    done
End

C++による実装例

#include<iostream>
using namespace std;

void cocktailSort(int arr[], int n){
    bool flag = true;
    int start = 0, end = n-1;
    while(flag){
        flag = false;
        // バブルソートと同様に左から右へ走査
        for(int i = start; i<end; i++){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        // 変更がなければループを抜ける
        if(!flag){
            break;
        }
        flag = false;
        end--; // 終端ポインタを1つ減らす
        // 右から左へ走査
        for(int i = end - 1; i >= start; i--){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        start++; // 始端ポインタを1つ進める
    }
}

main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    cocktailSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

出力結果

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

処理のポイント

• フラグ flag を使うことで、交換が発生しなくなった時点（＝ソート完了）で早期にループを抜けられます。
• 左→右の走査で最大値が右端に確定したら、end を減らして探索範囲を狭めます。
• 右→左の走査で最小値が左端に確定したら、start を増やして同様に範囲を狭めます。
• 計算量は平均・最悪ケースで O(n²)、すでに整列済みのデータに対しては O(n) となります。