C++で学ぶ再帰的選択ソートの実装方法とサンプルコード

選択ソート(Selection Sort)は、配列を先頭から順に走査しながら、各位置に「残りの要素の中で最も小さい値」を入れ替えていくことでデータを整列させる、基本的なソートアルゴリズムの一つです。

処理が進むにつれて、配列の左側はソート済みの領域となり、右側は未ソートの領域として扱われます。各ステップでは次に小さい要素を見つけて現在のインデックス位置と交換(swap)することで、整列済みの範囲を一つずつ広げていきます。

選択ソートのアルゴリズム

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

• int i, j;

• i = 0 から i < 配列サイズ - 1 まで走査する

  • j = i + 1 から 配列サイズ - 1 まで走査する

  • 最小値を見つけ、そのインデックス pos を記録する

• 見つかったインデックス pos の要素と arr[i] を交換する

• 終了

再帰的選択ソートとは

選択ソートは、forループなどの反復処理だけでなく、再帰呼び出しを使っても実装できます。再帰版の手順は以下の通りです。

• 最小要素のインデックスを求める

• 見つかった最小要素のインデックスが配列サイズと等しければ、そこで処理を終了して返す(ベースケース)

• そうでなければ、現在の要素と最小要素を交換する

• ソート済みの部分を除いた残りの配列に対して、上記の手順を再帰的に実行する

実行例

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

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

説明:

1回目のパス :-
5 7 2 3 1 4 → swap → 1 2 7 3 5 4
1 2 7 3 5 4 → 交換なし
1 2 7 3 5 4 → swap → 1 2 3 7 5 4
1 2 3 7 5 4 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 → 交換なし

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

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

説明:

1 2 3 3 2 → 交換なし
1 2 3 2 3 → 交換なし
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 → 交換なし

プログラムで使用するアプローチ

再帰的な選択ソートでは、ベースケース(再帰の終了条件)は「最小インデックス = 配列サイズ - 1」となります。それ以外の場合は、配列から最小値を見つけて現在のインデックスと交換し、右側の未ソート領域に対して再帰的にソートを実行します。

• 入力配列 Arr[] と、その要素数 length を受け取る。

• 関数 findMin(int arr[], int i, int j) は、配列とそのインデックスを受け取り、arr[i+1] から arr[j] の間で最小要素のインデックスを返す。

• 変数 minpos を用意する。

• i と j が同じ場合、両者が同一であるため i を最小要素のインデックスとして返す。

• そうでなければ、minpos = findMin(arr, i + 1, j) として、i+1 から j の範囲を再帰的に探索する。

• if(arr[i] < arr[minpos]) が成立すれば minpos = i と設定し、minpos を返す。

• 関数 recurselectSort(int arr1[], int len1, int pos1) は、入力配列を受け取り、再帰的な選択ソートによって昇順に並べ替える。

• pos1 == len1 の場合は最小要素が見つからないため、そのまま返す。

• それ以外の場合は minpos1 = findMin(arr1, pos1, len1-1) を設定する。

• 現在のインデックス pos1 と最小要素のインデックス minpos1 が異なる場合、一時変数 temp を使ってこれらのインデックスの要素を交換する。

• recurselectSort(arr1, len1, pos1 + 1) を呼び出し、配列の残りの部分に対して再帰処理を続ける。

• すべての呼び出しが完了し、len が 1 になると再帰を抜け、この時点で配列全体がソート済みとなる。

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

計算量について

選択ソートは、要素数 n に対して比較回数が約 n(n-1)/2 回となるため、時間計算量は平均・最悪・最良のいずれの場合も O(n²) です。一方、追加のメモリをほとんど必要としないインプレースなアルゴリズムであり、空間計算量は O(1) となります。ただし、再帰版では呼び出しスタックの深さ分のメモリ(O(n))が消費される点に注意が必要です。

サンプルコード

#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
    int minpos;
    if (i == j){
        return i;
    }
    minpos = findMin(arr, i + 1, j);
    if(arr[i]<arr[minpos]){
        minpos=i;
    }
    return (minpos);
}
void recurselectSort(int arr1[], int len1, int pos1){
    int temp;
    int minpos1;
    if (pos1 == len1){
        return;
    }
    minpos1 = findMin(arr1, pos1, len1-1);
    if (minpos1 != pos1){
        temp=arr1[pos1];
        arr1[pos1]=arr1[minpos1];
        arr1[minpos1]=temp;
    }
    recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
    int Arr[] = {1,5,3,0,9,3,5};
    int length = sizeof(Arr)/sizeof(Arr[0]);
    recurselectSort(Arr,length,0);
    cout<<"Sorted Array using recursive Selection sort: "<<endl;
    for (int i = 0; i<length ; i++){
        cout << Arr[i] << " ";
    }
    return 0;
}

出力結果

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

Sorted Array using recursive Selection sort:
0 1 3 3 5 5 9