C++で実装するパンケーキソート：アルゴリズムの仕組みとサンプルコード

パンケーキソート(Pancake Sort)は、配列Aを並べ替えるユニークなソートアルゴリズムです。このアルゴリズム最大の特徴は、使用できる操作が「rev(arr, i)」、すなわち配列arrの先頭(0番目)からi番目までの要素を反転させるという1種類のみであるという点です。

基本的な発想は選択ソートに似ています。最大の要素を繰り返し配列の末尾に移動させ、そのたびに扱う範囲(配列のサイズ)を1つずつ縮めていきます。例えば、入力が [54, 85, 52, 25, 98, 75, 25, 11, 68] であれば、出力は [11, 25, 25, 52, 54, 68, 75, 85, 98] になります。

アルゴリズムの手順

• size := n(初期サイズを設定)

• size > 1 の間、以下を繰り返します。

  • index := 先頭から size – 1 番目までの範囲における最大要素のインデックスを求める

  • rev(arr, index) を実行し、最大要素を先頭に移動する

  • rev(arr, size - 1) を実行し、最大要素を未整列部分の末尾へ移動する

  • size := size - 1 として、整列済みの部分を除外する

まず最大値を先頭に反転で持ってきてから、範囲全体を反転することで末尾に配置する、という2段階の反転がポイントです。それでは、実際のC++による実装を見ていきましょう。

C++での実装例

#include<iostream>
using namespace std;

// 先頭から i 番目までの要素を反転する関数
void rev(int arr[], int i) {
    int temp, st = 0;
    while (st < i) {
        temp = arr[st];
        arr[st] = arr[i];
        arr[i] = temp;
        st++;
        i--;
    }
}

// 先頭から n 個の範囲における最大要素のインデックスを返す関数
int maxIndex(int arr[], int n) {
    int index, i;
    for (index = 0, i = 0; i < n; ++i){
        if (arr[i] > arr[index]) {
            index = i;
        }
    }
    return index;
}

// パンケーキソート本体
int pancakeSort(int arr[], int n) {
    for (int size = n; size > 1; size--) {
        int index = maxIndex(arr, size);
        // 最大要素がすでに末尾にある場合は反転不要
        if (index != size-1) {
            rev(arr, index);   // 最大要素を先頭へ
            rev(arr, size-1);  // 最大要素を未整列部分の末尾へ
        }
    }
}

int main() {
    int arr[] = {54, 85, 52, 25, 98, 75, 25, 11, 68};
    int n = sizeof(arr)/sizeof(arr[0]);
    pancakeSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
}

入力

[54, 85, 52, 25, 98, 75, 25, 11, 68]

出力

Sorted array: [11, 25, 25, 52, 54, 68, 75, 85, 98]

計算量について

パンケーキソートでは、各ループで最大要素の探索にO(n)、反転処理にも最大O(n)かかるため、全体の時間計算量はO(n²)となります。一方、必要な補助メモリはO(1)と非常に少なく、また「先頭からの反転」という特殊な操作だけで並べ替えが完結するため、制約付き環境での応用例や競技プログラミングの題材としても知られています。