C++でソート済み配列を実装するプログラム：選択ソートの基本と実装例

ソート済み配列とは、数値順やアルファベット順など、何らかの基準に従ってすべての要素が整列された配列のことです。配列をソートするためのアルゴリズムには、バブルソート、挿入ソート、選択ソート、マージソート、クイックソート、ヒープソートなど、さまざまな種類があります。

本記事では、その中でも「選択ソート」を使って配列をソートする方法について、サンプルコードを交えながら詳しく解説します。

選択ソートとは

選択ソートは、未ソート部分の中から最小の要素を繰り返し見つけ出し、それを未ソート部分の先頭にある要素と入れ替えることで、徐々にソート済み配列を作り上げていく手法です。実装がシンプルで理解しやすいことが特徴ですが、計算量は O(n²) となるため、大量のデータを扱う場合にはマージソートやクイックソートの方が効率的です。

以下に、選択ソートを使用してソート済み配列を実装するC++プログラムを示します。

サンプルコード

#include<iostream>
using namespace std;
void selectionSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
        if (a[j] < a[min])
        min = j;
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}
int main() {
    int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
    int n = sizeof(a)/ sizeof(a[0]);
    int i;
    cout<<"Given array is:"<<endl;
    for (i = 0; i < n; i++)
    cout<< a[i] <<" ";
    cout<<endl;
    selectionSort(a, n);
    printf("\nSorted array is: \n");
    for (i = 0; i < n; i++)
    cout<< a[i] <<" ";
    return 0;
}

実行結果

Given array is:
22 91 35 78 10 8 75 99 1 67
Sorted array is:
1 8 10 22 35 67 75 78 91 99

プログラムの解説

上記のプログラムでは、selectionSort() 関数が選択ソートを用いて配列 a[] をソートしています。selectionSort() の中には2つのforループがあり、外側のforループの各反復処理において、インデックス i 以降の残りの要素の中から最小値を探し出し、現在 i の位置にある要素と交換します。この操作を、配列全体が完全にソートされるまで繰り返します。該当するコードは以下の通りです。

void selectionSort(int a[], int n) {
    int i, j, min, temp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
        if (a[j] < a[min])
        min = j;
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

一方、main() 関数では、まず配列 a[] を定義し、続いて sizeof(a)/sizeof(a[0]) によって配列のサイズ n を求めます。その後、配列 a[] とサイズ n を引数として selectionSort() を呼び出してソートを実行し、最後にソート後の配列を画面に表示します。該当するコードは以下の通りです。

int main() {
    int a[] = { 22, 91, 35, 78, 10, 8, 75, 99, 1, 67 };
    int n = sizeof(a)/ sizeof(a[0]);
    int i;
    cout<<"Given array is:"<<endl;
    for (i = 0; i < n; i++)
    cout<< a[i] <<" ";
    cout<<endl;
    selectionSort(a, n);
    printf("\nSorted array is: \n");
    for (i = 0; i < n; i++)
    cout<< a[i] <<" ";
    return 0;
}

まとめ

選択ソートは、最小値を探して先頭と交換するという単純な手順を繰り返すだけで配列を整列できる、初心者にもわかりやすいアルゴリズムです。計算量は O(n²) と決して高速ではありませんが、ソートの基本的な考え方を学ぶ題材として非常に有用です。ぜひ実際にコードを動かしながら、その動作を確認してみてください。