C++で配列をソートするための「先頭へ移動」操作の最小回数を求める方法

1からnまでの数字が重複なく格納された配列が与えられます。この記事の目的は、与えられた配列を昇順にソートするために必要な「先頭へ移動(move-to-front)」操作の最小回数を求めることです。「先頭へ移動」とは、配列内の任意の要素を取り出して、先頭(インデックス0)に配置する操作を指します。

この問題は、配列を末尾から先頭に向かって走査することで効率的に解けます。要素がすでに正しい位置にあれば移動は不要ですが、そうでなければ移動が必要です。1からnまでの要素で構成されるソート済み配列では、各要素arr[i]の正しい値はi+1である必要があります。つまり、arr[0]=1、arr[1]=2、……、arr[n-1]=nという対応関係になります。

入力例

Arr[]= { 4,3,2,1 }

出力

「先頭へ移動」操作の最小回数: 3

解説

3を先頭へ移動 → 3,4,2,1 (回数=1)
2を先頭へ移動 → 2,3,4,1 (回数=2)
1を先頭へ移動 → 1,2,3,4 (回数=3)

入力例

Arr[]= { 6,1,2,5,4,3 }

出力

「先頭へ移動」操作の最小回数: 5

解説

5を先頭へ移動 → 5,6,1,2,4,3 (回数=1)
4を先頭へ移動 → 4,5,6,1,2,3 (回数=2)
3を先頭へ移動 → 3,4,5,6,1,2 (回数=3)
2を先頭へ移動 → 2,3,4,5,6,1 (回数=4)
1を先頭へ移動 → 1,2,3,4,5,6 (回数=5)

プログラムのアプローチ

• 整数型配列Arr[]に、1からnまでの数字を格納します。

• 整数型変数sizeに、配列Arr[]の長さを保存します。

• 関数movetoFront(int arr[], int n)は、配列とその長さを引数として受け取り、その配列をソートするのに必要な「先頭へ移動」操作の最小回数を返します。

• カウント用変数countは、配列のサイズで初期化されます。これは、降順に並んだ配列の場合、すべての要素を移動する必要があるためです。

• 配列を末尾のインデックスから先頭に向かって走査し、要素の値が現在のcountと一致した場合(1からnまでのソート済み要素では、nが末尾、n-1がその手前に配置される)、その要素は正しい位置にあるためcountをデクリメントします。

• この処理により、ループ終了時のcountが求める最小移動回数となります。

コード例

#include <bits/stdc++.h>
using namespace std;
// 配列を昇順に並べるために必要な最小移動回数を計算する
int movetoFront(int arr[], int n){
    // すべての要素が正しく配置されているものとしてカウントを初期化
    int count = n;
    // 配列を末尾から走査
    for (int i=n-1; i >= 0; i--){
        // 現在の要素が正しい位置にある場合、カウントを減らす
        // 範囲は1からnなので、各arr[i]はi+1の値を持つべき
        // インデックス0には1、インデックス1には2......
        if (arr[i] == count)
            count--;
    }
    return count;
}
int main(){
    int Arr[] = {5, 3, 4, 7, 2, 6, 1};
    int size = 7;
    cout <<"配列をソートするための最小「先頭へ移動」回数:"<< movetoFront(Arr, size);
    return 0;
}

出力

配列をソートするための最小「先頭へ移動」回数:6

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量はO(n)です。また、追加の記憶領域を必要としないため、空間計算量はO(1)となります。要素が正しい位置にあるかどうかの判定を末尾から行うことで、すでに整列済みの後方要素を移動対象から除外できるのがこの手法のポイントです。