[C言語] 選択ソートとは？仕組みや実装方法をコード付きで解説

2023-09-102024-08-25

選択ソートは、配列をソートするための単純なアルゴリズムです。基本的な仕組みは、未ソート部分から最小（または最大）の要素を選び出し、それをソート済み部分の末尾と交換することを繰り返します。

このプロセスは、配列全体がソートされるまで続きます。選択ソートは、時間計算量がO(n^2)であり、効率はあまり良くありませんが、実装が簡単で理解しやすいという利点があります。

C言語での実装では、二重ループを用いて最小値を見つけ、要素を交換する処理を行います。

この記事でわかること

選択ソートの基本的な仕組みと特徴
C言語での選択ソートの実装方法
選択ソートの応用例とその実装
他のソートアルゴリズムとの比較
選択ソートの適用場面とその利点・欠点

目次から探す

選択ソートの基本概念

選択ソートとは何か

選択ソートは、配列やリストをソートするための基本的なアルゴリズムの一つです。

このアルゴリズムは、未整列部分から最小(または最大)の要素を選び出し、それを整列済み部分の末尾に追加するという手順を繰り返します。

選択ソートは、直感的で理解しやすいアルゴリズムであり、教育目的でよく使用されます。

選択ソートの特徴

選択ソートには以下のような特徴があります：

単純さ: アルゴリズムが非常にシンプルで、実装が容易です。
安定性: 選択ソートは安定なソートではありません。

つまり、同じ値の要素の順序がソート後に変わる可能性があります。

時間計算量: 最悪、平均、最良のケースすべてで時間計算量はO(n^2)です。

これは、要素数が増えると計算時間が急激に増加することを意味します。

空間計算量: 追加のメモリをほとんど使用しないため、空間計算量はO(1)です。

選択ソートの利点と欠点

選択ソートの利点と欠点を以下の表にまとめます。

スクロールできます

利点	欠点
実装が簡単で理解しやすい	時間計算量がO(n^2)であり、大規模なデータセットには不向き
追加のメモリをほとんど必要としない	安定なソートではない

選択ソートは、特に小規模なデータセットや、メモリ使用量を最小限に抑えたい場合に適しています。

しかし、効率性を重視する場合は、他のソートアルゴリズムを検討することが推奨されます。

選択ソートの仕組み

アルゴリズムの流れ

選択ソートのアルゴリズムは、以下のような流れで進行します：

配列の最初の要素から順に、未整列部分の最小値を探します。
見つけた最小値を未整列部分の先頭の要素と交換します。
未整列部分の先頭を一つ進め、手順1と2を繰り返します。
配列全体が整列されるまで、手順1から3を繰り返します。

このプロセスを繰り返すことで、配列全体が昇順に整列されます。

手順の詳細解説

最小値の選択

選択ソートでは、未整列部分から最小値を選び出すことが重要です。

具体的には、以下の手順で最小値を選択します：

未整列部分の最初の要素を仮の最小値とします。
未整列部分の残りの要素と仮の最小値を比較し、より小さい値が見つかればそれを新たな最小値とします。
未整列部分全体を確認し終えた時点で、最小値が確定します。

要素の交換

最小値が確定したら、その値を未整列部分の先頭の要素と交換します。

交換の手順は以下の通りです：

最小値の位置と未整列部分の先頭の位置を記録します。
これらの位置にある要素を交換します。
交換が完了したら、未整列部分の先頭を一つ進めます。

計算量の分析

時間計算量

選択ソートの時間計算量は、最悪、平均、最良のケースすべてでO(n^2)です。

これは、n個の要素に対して、各要素ごとに残りの要素を比較するためです。

具体的には、n-1回の最小値選択と交換が行われ、それぞれがn回の比較を伴うため、合計で約n^2/2回の操作が必要となります。

空間計算量

選択ソートの空間計算量はO(1)です。

これは、ソートの過程で追加の配列やリストを使用せず、既存の配列内で要素を交換するだけであるためです。

この特性により、選択ソートはメモリ効率が高いアルゴリズムといえます。

C言語での選択ソートの実装

基本的な実装例

以下に、C言語での選択ソートの基本的な実装例を示します。

#include <stdio.h>
int main() {
    int array[] = {64, 25, 12, 22, 11};
    int n = sizeof(array) / sizeof(array[0]);
    int i, j, min_idx, temp;
    // 選択ソートの実装
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (array[j] < array[min_idx]) {
                min_idx = j;
            }
        }
        // 最小値を先頭と交換
        temp = array[min_idx];
        array[min_idx] = array[i];
        array[i] = temp;
    }
    // ソート結果の表示
    printf("Sorted array: ");
    for (i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

コードの説明

このコードは、整数の配列を選択ソートで昇順に並べ替えるプログラムです。

arrayはソート対象の配列で、nは配列の要素数を表します。

外側のループで未整列部分の先頭を決定し、内側のループで最小値を探して交換します。

最終的に、ソートされた配列を出力します。

Sorted array: 11 12 22 25 64

この実行例では、元の配列{64, 25, 12, 22, 11}が選択ソートによって昇順に並べ替えられています。

関数化による実装

選択ソートを関数化することで、再利用性を高めることができます。

関数の定義と呼び出し

以下に、選択ソートを関数化した例を示します。

#include <stdio.h>
void selectionSort(int array[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (array[j] < array[min_idx]) {
                min_idx = j;
            }
        }
        temp = array[min_idx];
        array[min_idx] = array[i];
        array[i] = temp;
    }
}
int main() {
    int array[] = {64, 25, 12, 22, 11};
    int n = sizeof(array) / sizeof(array[0]);
    selectionSort(array, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

コードの説明

このコードでは、selectionSortという関数を定義し、配列とその要素数を引数として受け取ります。

関数内で選択ソートのアルゴリズムを実行し、main関数から呼び出すことで、配列をソートします。

これにより、ソート処理を他のプログラムでも簡単に利用できるようになります。

ポインタを用いた実装

ポインタを用いることで、配列の操作をより効率的に行うことができます。

ポインタの活用方法

以下に、ポインタを用いた選択ソートの実装例を示します。

#include <stdio.h>
void selectionSort(int *array, int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (*(array + j) < *(array + min_idx)) {
                min_idx = j;
            }
        }
        temp = *(array + min_idx);
        *(array + min_idx) = *(array + i);
        *(array + i) = temp;
    }
}
int main() {
    int array[] = {64, 25, 12, 22, 11};
    int n = sizeof(array) / sizeof(array[0]);
    selectionSort(array, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", *(array + i));
    }
    printf("\n");
    return 0;
}

コードの説明

このコードでは、selectionSort関数がポインタを用いて配列を操作します。

配列の要素にアクセスする際に、インデックスを用いる代わりにポインタ演算を使用しています。

これにより、配列の操作がより柔軟になり、ポインタの理解を深めることができます。

選択ソートの応用例

降順ソートへの応用

選択ソートは、昇順だけでなく降順にも応用することができます。

アルゴリズムの変更点

降順ソートにするためには、最小値を探す部分を最大値を探すように変更します。

具体的には、比較演算子を変更することで実現できます。

コード例

以下に、降順ソートを行う選択ソートのコード例を示します。

#include <stdio.h>
void selectionSortDescending(int array[], int n) {
    int i, j, max_idx, temp;
    for (i = 0; i < n-1; i++) {
        max_idx = i;
        for (j = i+1; j < n; j++) {
            if (array[j] > array[max_idx]) { // 最大値を探す
                max_idx = j;
            }
        }
        temp = array[max_idx];
        array[max_idx] = array[i];
        array[i] = temp;
    }
}
int main() {
    int array[] = {64, 25, 12, 22, 11};
    int n = sizeof(array) / sizeof(array[0]);
    selectionSortDescending(array, n);
    printf("Sorted array in descending order: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、array[j] < array[max_idx]の部分をarray[j] > array[max_idx]に変更することで、最大値を探し出し、降順にソートしています。

部分ソートへの応用

選択ソートは、配列の一部だけをソートする部分ソートにも応用できます。

部分ソートの概念

部分ソートとは、配列全体ではなく、特定の範囲内の要素だけをソートすることです。

これにより、必要な部分だけを効率的に整列させることができます。

コード例

以下に、配列の一部をソートする選択ソートのコード例を示します。

#include <stdio.h>
void partialSelectionSort(int array[], int start, int end) {
    int i, j, min_idx, temp;
    for (i = start; i < end; i++) {
        min_idx = i;
        for (j = i+1; j <= end; j++) {
            if (array[j] < array[min_idx]) {
                min_idx = j;
            }
        }
        temp = array[min_idx];
        array[min_idx] = array[i];
        array[i] = temp;
    }
}
int main() {
    int array[] = {64, 25, 12, 22, 11, 90, 45};
    int n = sizeof(array) / sizeof(array[0]);
    partialSelectionSort(array, 1, 4); // インデックス1から4までをソート
    printf("Partially sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、partialSelectionSort関数を用いて、配列のインデックス1から4までの要素をソートしています。

二次元配列への応用

選択ソートは、二次元配列にも応用することができます。

二次元配列のソート方法

二次元配列をソートする場合、行ごとにソートするか、全体を一次元配列として扱ってソートする方法があります。

ここでは、行ごとにソートする方法を示します。

コード例

以下に、二次元配列の各行を選択ソートでソートするコード例を示します。

#include <stdio.h>
void selectionSort2D(int array[][3], int rows) {
    int i, j, k, min_idx, temp;
    for (i = 0; i < rows; i++) {
        for (j = 0; j < 3-1; j++) {
            min_idx = j;
            for (k = j+1; k < 3; k++) {
                if (array[i][k] < array[i][min_idx]) {
                    min_idx = k;
                }
            }
            temp = array[i][min_idx];
            array[i][min_idx] = array[i][j];
            array[i][j] = temp;
        }
    }
}
int main() {
    int array[3][3] = {{64, 25, 12}, {22, 11, 90}, {45, 33, 77}};
    int rows = 3;
    selectionSort2D(array, rows);
    printf("Sorted 2D array by rows:\n");
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
    return 0;
}

このコードでは、selectionSort2D関数を用いて、二次元配列の各行を選択ソートでソートしています。

各行が独立してソートされるため、行ごとの整列が可能です。