カクテルソートとは？C++での実装プログラムをわかりやすく解説

カクテルソート（Cocktail Sort）とは

カクテルソートは、バブルソートの改良版の一種で、安定なソートアルゴリズムかつ比較ソートに分類されます。「双方向バブルソート」「カクテルシェーカーソート」「シェーカーソート」「リップルソート」「シャッフルソート」「シャトルソート」など、複数の名前で呼ばれることもあります。

通常のバブルソートとの最大の違いは、リストを通過するたびに前方向と後ろ方向の両方でソートを行う点です。これにより、配列の末尾付近にある小さな要素も早く正しい位置へ移動でき、バブルソートよりも効率が改善される場合があります。

入出力例

入力：53421
出力：12345

アルゴリズムの仕組み

カクテルソートでは、ソートされていない要素で構成された配列を対象とし、各パスで配列を双方向に走査します。具体的には、バブルソートを前方向に1回、後ろ方向に1回適用するイメージです。

1. 前方向のパス：先頭から末尾に向かって隣接する2要素を比較し、順序が逆であれば交換します。これにより最大の要素が末尾へ移動します。
2. 後ろ方向のパス：次に末尾から先頭に向かって同じく比較・交換を行い、最小の要素が先頭へ移動します。
3. ソート済みの範囲を端から1つずつ狭めながら、交換が発生しなくなるまでこの処理を繰り返します。

C++による実装例

#include <iostream>
using namespace std;
int main() {
    int arr[] = { 5, 3, 4, 2, 1 };
    int m = 5;
    int n, c;
    n = m;
    do {
        // 前方向のパス（先頭 → 末尾）
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                arr[i] = arr[i] + arr[i + 1];
                arr[i + 1] = arr[i] - arr[i + 1];
                arr[i] = arr[i] - arr[i + 1];
            }
        }
        n = n - 1;
        // 後ろ方向のパス（末尾 → 先頭）
        for (int i = m - 1, c = 0; i >= c; i--) {
            if (arr[i] < arr[i - 1]) {
                arr[i] = arr[i] + arr[i - 1];
                arr[i - 1] = arr[i] - arr[i - 1];
                arr[i] = arr[i] - arr[i - 1];
            }
        }
        c = c + 1;
    }
    while (n != 0 && c != 0);
    // 結果の出力
    for (int i = 0; i < m; i++) {
        cout << arr[i] << "\t";
    }
}

このプログラムでは、配列 { 5, 3, 4, 2, 1 } をカクテルソートで昇順に並べ替え、実行結果として「1 2 3 4 5」が出力されます。なお、コード内では一時変数を使用せず、加減算によって隣接要素を入れ替える（スワップする）手法を採用しています。

計算量の目安

• 平均計算量・最悪計算量：O(n²)
• 最良計算量（すでにソート済みの配列）：O(n)
• 空間計算量：O(1)（インプレースソート）

カクテルソートはシンプルな実装で理解しやすい一方、大規模なデータには不向きです。学習用途や、ほぼ整列済みの小さなデータを扱う場面で活用するとよいでしょう。