C++による再帰的挿入ソートの解説と実装例

挿入ソート（Insertion Sort）は、トランプの手札を並べ替えるように、要素を適切な位置へ挿入しながらデータを整列させるソートアルゴリズムの一つです。すべての要素を左から右へ順に走査し、最初の要素を「すでにソート済み」とみなします。その後、残りの要素を1つずつ取り出し、左側のソート済みリストの中で正しい位置に挿入していきます。各要素は、自分より小さい（または等しい）要素が見つかるまで、左側の要素と順番に比較されます。

挿入ソートのアルゴリズム

• int arr[5] = { 5,4,2,1,3 };

• int i, j;

• インデックス j = i+1 から j ＜ 配列サイズ まで走査します。

• 各要素 arr[j] について、「arr[i] ＜ arr[j] かつ arr[i+1] ＞= arr[j]」となる位置が見つかるまで、リスト arr[0〜i] 内の要素と比較します。

• arr[j] をその位置に挿入し、それより大きい要素をすべて1つずつ右へ移動します。

• 終了

再帰的挿入ソート

• 配列の長さが1の場合は、そこで処理を終了して返します（ベースケース）。

• インデックス0から 配列サイズ−1 までの要素を再帰的にソートします。

• 最後の要素を、ソート済み配列内の正しい位置に挿入します。

例

入力 − Arr[] = { 5,7,2,3,1,4 }; 長さ=6

出力 − ソート済み配列: 1 2 3 4 5 7

説明 −

5 7 2 3 1 4 → 5 はすでにソート済み
5 7 2 3 1 4 → 7 は正しい位置にある
2 5 7 3 1 4 → 2 を 5,7 と比較して挿入
2 3 5 7 1 4 → 3 を 5,7 と比較して挿入
1 2 3 5 7 4 → 1 を 2,3,5,7 と比較して挿入
1 2 3 4 5 7 → 4 を 5,7 と比較して挿入

入力 − Arr[] = { 1, 2, 3, 3, 2 };

出力 − ソート済み配列: 1 2 2 3 3

説明 −

1, 2, 3, 3, 2 → 1 はすでにソート済み
1, 2, 3, 3, 2 → 2 は正しい位置にある
1, 2, 3, 3, 2 → 3 は正しい位置にある
1, 2, 3, 3, 2 → 3 は正しい位置にある
1, 2, 2, 3, 3 → 2 を 3,3 と比較して挿入

本プログラムで採用しているアプローチ

再帰的な挿入ソートでは、ベースケースを「配列の長さが1」とします。それ以外の場合は、まず先頭から n−1 個の要素を再帰的にソートし、その後、最後の要素をソート済み部分の正しい位置へ挿入します。

• 入力として配列 Arr[] と、その要素数である長さを受け取ります。

• 関数 recInsSort(int arr[], int len) が配列とその長さを受け取り、再帰的に挿入ソートを実行します。

• 配列の長さが1以下の場合は、何もせずに返します（void）。

• それ以外の場合は、recInsSort(arr, len−1) を再帰呼び出しし、先頭の len−1 個の要素をソート済みにします。

• 最後の要素 last = arr[len−1] を取り出し、変数 j を len−2 で初期化します。

• j ＞= 0 かつ arr[j] ＞ last の間、arr[j+1] = arr[j] として要素を1つずつ右へずらし、j を減らしていきます。

• ループを抜けたら、last を arr[j+1] に挿入します。

• すべての再帰呼び出しが完了し、len が1になると再帰から抜け、配列全体がソートされた状態になります。

• main 関数内でソート済みの配列を出力します。

例

#include <bits/stdc++.h>
using namespace std;

void recInsSort(int arr[], int len){
    // ベースケース：要素が1個以下ならソート済み
    if (len <= 1){
        return;
    }
    // 先頭の len-1 個の要素を再帰的にソート
    recInsSort(arr, len - 1);
    // 最後の要素をソート済み部分に挿入
    int last = arr[len - 1];
    int j = len - 2;
    while (j >= 0 && arr[j] > last){
        arr[j + 1] = arr[j];
        j--;
    }
    arr[j + 1] = last;
}

int main(){
    int Arr[] = {21, 34, 20, 31, 78, 43, 66};
    int length = sizeof(Arr)/sizeof(Arr[0]);

    recInsSort(Arr, length);

    cout<<"Sorted array : ";
    for(int i=0;i<length;i++){
        cout<<Arr[i]<<" ";
    }

    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Sorted array : 20 21 31 34 43 66 78