C++で回転ソート済み配列の回転回数を求める方法

ここでは、回転ソート済み配列（Rotated Sorted Array）が与えられたときに、その配列を元のソートされた状態に戻すために必要な回転回数を求める問題を扱います。なお、回転は「右から左へ」要素を移動させる操作として考えます。

例えば、次のような配列を考えてみましょう。

{15, 17, 1, 2, 6, 11}

この配列をソートするには、2回の回転が必要です。回転を繰り返すと、最終的に次の順序になります。

{1, 2, 6, 11, 15, 17}

この場合の出力（回転回数）は 2 となります。

解法のポイント

この問題のロジックは非常にシンプルです。配列を注意深く観察すると、必要な回転回数は「最小要素のインデックス」と一致することがわかります。

つまり、配列内の最小要素を見つけられれば、そのインデックスがそのまま答えになります。これは、回転ソート済み配列では最小要素が「回転の境界位置」に必ず存在するためです。

アルゴリズムの手順

1. 配列の先頭要素を仮の最小値としてインデックス0を記録します。
2. 配列を先頭から順に走査し、より小さい要素が見つかるたびにそのインデックスを更新します。
3. 走査が終わった時点で記録されているインデックスが、回転回数（＝最小要素の位置）となります。

C++での実装例

#include <iostream>
using namespace std;

// 最小要素のインデックスを返す関数
int getMinIndex(int arr[], int n){
    int index = 0;
    for(int i = 1; i < n; i++){
        if(arr[i] < arr[index]){
            index = i;
        }
    }
    return index;
}

// 必要な回転回数を求める関数
int countNumberOfRotations(int arr[], int n){
    return getMinIndex(arr, n);
}

int main() {
    int arr[] = {15, 17, 1, 2, 6, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of required rotations: " << countNumberOfRotations(arr, n);
}

実行結果

Number of required rotations: 2

計算量について

上記の線形探索によるアプローチの計算量は O(n) です。配列のすべての要素を一度確認するため、シンプルで確実な方法と言えます。

なお、配列が「ソート済み配列を回転させたもの」であるという性質を利用すると、二分探索（Binary Search）を使って O(log n) の計算量で最小要素の位置を見つけることも可能です。大規模な配列を扱う場合は、こちらの手法を検討するとより効率的です。