C++でシェーカーソートを実装する方法｜アルゴリズムとサンプルコード解説

シェーカーソートとは

シェーカーソート（Shaker Sort）は、与えられたデータを昇順に並べ替えるためのソートアルゴリズムの一つです。バブルソートとよく似ていますが、決定的に異なるのは配列を双方向（往復）に走査して整列を進める点です。「カクテルソート」「双方向バブルソート」と呼ばれることもあります。このアルゴリズムの最悪計算量は O(n²) です。

アルゴリズムの手順

開始
　　ShakerSort() 関数は、引数としてデータ配列 arr と要素数 n を受け取る。
　　// ネストした for ループを使ってソートを実装する。
　　外側のループは i を 0 から n-1 まで回し、内部に2つのループを持つ。
　　1つ目のループは j を i+1 から n-1 まで回し、a[j] < a[j-1] なら swap() で隣接要素を交換する。
　　n をデクリメントする。
　　2つ目のループは k を m-1 から i+1 まで回し、a[k] < a[k-1] なら swap() で隣接要素を交換する。
　　i をインクリメントする。
終了

具体的には、まず左から右へ走査して大きな値を末尾側へ移動させ、続いて右から左へ走査して小さな値を先頭側へ移動させます。未整列の範囲を両端から狭めながらこれを繰り返すことで、配列全体が整列されます。

C++によるサンプルコード

#include<iostream>
using namespace std;

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void ShakerSort(int a[], int m) {
    int i, j, k;
    for(i = 0; i < m;) {
        // 前方向のパス：大きい値を後ろへ移動
        for(j = i+1; j < m; j++) {
            if(a[j] < a[j-1])
                swap(&a[j], &a[j-1]);
        }
        m--;
        // 後方向のパス：小さい値を前へ移動
        for(k = m-1; k > i; k--) {
            if(a[k] < a[k-1])
                swap(&a[k], &a[k-1]);
        }
        i++;
    }
}

int main() {
    int n, i;
    cout<<"\nソートするデータ要素の個数を入力してください: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"要素 "<<i+1<<" を入力: ";
        cin>>a[i];
    }
    ShakerSort(a, n);
    cout<<"\nソート後のデータ ";
    for (i = 0; i < n; i++)
        cout<<"->"<<a[i];
    return 0;
}

補足： 上記のコードで使われている可変長配列（int a[n];）はGCCなど独自拡張の機能であり、標準C++の規格では保証されていません。移植性を重視する場合は、std::vector<int> の利用を推奨します。

実行結果

ソートするデータ要素の個数を入力してください: 4
要素 1 を入力: 3
要素 2 を入力: 1
要素 3 を入力: 7
要素 4 を入力: 6
ソート後のデータ ->1->3->6->7

まとめ

シェーカーソートは、バブルソートを双方向化することで、配列の後方にある小さな要素を素早く先頭側へ移動できるようにした改良版ソートです。計算量は平均・最悪ともに O(n²) と大規模データには不向きですが、仕組みがシンプルで直感的に理解しやすいため、ソートアルゴリズムの学習用として最適な題材といえます。