C言語で学ぶ再帰的挿入ソートのプログラムと実装方法

挿入ソート（Insertion Sort）は、その場（インプレース）で比較を行うソートアルゴリズムの一つです。

このアルゴリズムは、各要素を「その要素より前の部分配列（すでにソート済みのサブ配列）」の中の正しい位置へ順次挿入していくことで、配列全体を整列させます。

アルゴリズムの手順

ステップ1：1からn-1までループを回し、以下の処理を行います。

ステップ2.1：位置iにある要素 array[i] を選択します。

ステップ2.2：その要素を、ソート済みサブ配列 array[0]〜arr[i] の中の適切な位置に挿入します。

具体例で理解しよう

配列 = [34, 7, 12, 90, 51]

i = 1 のとき： arr[1] = 7 を、サブ配列 arr[0]〜arr[1] 内の正しい位置に挿入します。

[7, 34, 12, 90, 51]

i = 2 のとき： arr[2] = 12 を、サブ配列 arr[0]〜arr[2] 内の正しい位置に挿入します。

[7, 12, 34, 90, 51]

i = 3 のとき： arr[3] = 90 はすでに正しい位置にあるため、配列は変化しません。

[7, 12, 34, 90, 51]

i = 4 のとき： arr[4] = 51 を、サブ配列 arr[0]〜arr[4] 内の正しい位置に挿入します。

[7, 12, 34, 51, 90]

再帰的挿入ソートの考え方

ここでは、再帰を使った挿入ソートの動作を見ていきましょう。通常のループ版とは逆のアプローチを取ります。つまり、まず recursiveInsertionSort() 関数を再帰的に呼び出して「n-1個の要素」を先にソートし、その返されたソート済み配列に対して、n番目の要素を適切な位置に挿入するという流れです。

再帰的挿入ソートのサンプルプログラム

コード例

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
    if (n <= 1)
        return;
    recursiveInsertionSort( arr, n-1 );
    int nth = arr[n-1];
    int j = n-2;
    while (j >= 0 && arr[j] > nth){
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = nth;
}
int main(){
    int array[] = {34, 7, 12, 90, 51};
    int n = sizeof(array)/sizeof(array[0]);
    printf("Unsorted Array:\t");
    for (int i=0; i < n; i++)
        printf("%d ",array[i]);
    recursiveInsertionSort(array, n);
    printf("\nSorted Array:\t");
    for (int i=0; i < n; i++)
        printf("%d ",array[i]);
    return 0;
}

実行結果

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90

まとめ

再帰的挿入ソートは、「小さな問題から順に解いていく」という再帰の特性を活かした実装です。計算量は平均・最悪ケースともにO(n²)であり、要素数が少ないデータや、ほぼ整列済みのデータに対しては効率的に動作します。再帰呼び出しの構造を理解する良い教材としてもおすすめです。