C++の選択ソートで文字列配列をソートする方法

選択ソートの仕組み

選択ソート(Selection Sort)は、未ソート部分から最小の要素を繰り返し見つけて先頭に移動させることで、配列全体を整列させるシンプルなアルゴリズムです。各反復処理において、未ソートの部分配列から最小要素を選び出し、ソート済み部分の末尾へ移動していきます。

文字列の配列を扱う場合は、数値の比較の代わりに strcmp() 関数を使って文字列を辞書順に比較する点がポイントです。

サンプルコード

#include <iostream>
#include <string.h>
using namespace std;
#define MAX_LEN 50

void selectionSort(char arr[][50], int n){
    int i, j, mIndex;
    char minStr[50];
    // 未ソート部分の境界を1つずつ移動
    for (i = 0; i < n-1; i++){
        // 未ソート配列内の最小要素を求める
        mIndex = i;
        strcpy(minStr, arr[i]);
        for (j = i + 1; j < n; j++){
            // 現在の最小要素が arr[j] より大きいか確認
            if (strcmp(minStr, arr[j]) > 0){
                // arr[j] を最小要素として更新
                strcpy(minStr, arr[j]);
                mIndex = j;
            }
        }
        // 最小要素を先頭の要素と交換
        if (mIndex != i){
            char temp[50];
            strcpy(temp, arr[i]);
            strcpy(arr[i], arr[mIndex]);
            strcpy(arr[mIndex], temp);
        }
    }
}

int main(){
    char arr[][50] = {"Tom", "Boyaka", "Matt", "Luke"};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;
    cout<<"Given String is:: Tom, Boyaka, Matt, Luke\n";
    selectionSort(arr, n);
    cout << "\nSelection Sorted is::\n";
    for (i = 0; i < n; i++)
        cout << i << ": " << arr[i] << endl;
    return 0;
}

コードの解説

このC++プログラムは、まず配列内の最小の要素を選択し、先頭の要素と交換します。次に、2番目に小さい要素を2番目の位置にある要素と交換します。この処理を繰り返すことで、各パスごとに最小要素が選択されて正しい位置へ配置され、最終的に配列全体が整列します。その結果、与えられた文字列は以下のように昇順にソートされます。

• strcmp(): 2つの文字列を辞書順に比較します。最初の引数の文字列が大きい場合は正の値を返すため、これを利用して最小要素を判定します。
• strcpy(): 文字列をコピーする関数です。文字列は代入演算子で直接コピーできないため、要素の交換にも使用します。

なお、選択ソートの計算量は O(n²) です。実装が非常にシンプルで理解しやすい反面、大量のデータを扱う場合にはクイックソートなどの高速なアルゴリズムが適しています。

実行結果

Given string is:: Tom, Boyaka, Matt, Luke
Selection Sorted::
Boyaka
Luke
Matt
Tom