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

2023-09-102024-07-22

この記事では、C言語を使って「選択ソート」というソートアルゴリズムについて学びます。

選択ソートは、配列の中から最小値を見つけて並べ替えるシンプルな方法です。

基本的な概念から実際のコード例、さらには選択ソートの応用や性能、利点と欠点、そして改善方法までを詳しく解説します。

プログラミング初心者でも理解しやすいように、ステップバイステップで説明していきますので、ぜひ最後まで読んでみてください。

目次から探す

選択ソートの基本概念

選択ソートとは？

選択ソートの定義

選択ソート(Selection Sort)は、配列の要素を順番に比較し、最小(または最大)の要素を選んで並べ替えるシンプルなソートアルゴリズムです。

基本的な考え方は、未ソート部分から最小の要素を選び、それをソート済み部分の末尾に追加していくというものです。

選択ソートの特徴

選択ソートの主な特徴は以下の通りです：

シンプルな実装：アルゴリズムが直感的で理解しやすく、実装も簡単です。
安定性：選択ソートは安定なソートではありません。

同じ値の要素の順序が保持されない場合があります。

時間計算量：選択ソートの時間計算量はO(n^2)です。

これは、配列の要素数が増えると、処理時間が急激に増加することを意味します。

空間計算量：選択ソートはインプレースソートであり、追加のメモリをほとんど必要としません。

空間計算量はO(1)です。

選択ソートの仕組み

選択ソートの仕組みは以下の通りです：

配列の最初の要素から始めて、未ソート部分の最小値を見つけます。
見つけた最小値を未ソート部分の最初の要素と交換します。
未ソート部分の範囲を一つ縮めて、再度最小値を見つけて交換します。
この手順を配列全体がソートされるまで繰り返します。

アルゴリズムの概要

ステップバイステップの説明

選択ソートのアルゴリズムをステップバイステップで説明します。

配列の最初の要素を基準にして、未ソート部分の最小値を見つけます。
見つけた最小値を未ソート部分の最初の要素と交換します。
未ソート部分の範囲を一つ縮めて、再度最小値を見つけて交換します。
この手順を配列全体がソートされるまで繰り返します。

最小値の選択

最小値の選択は、未ソート部分の全ての要素を順番に比較して、最小の要素を見つける作業です。

例えば、配列が [5, 3, 8, 4, 2] の場合、最初のステップでは 2 が最小値として選ばれます。

位置の交換

最小値が見つかったら、その最小値を未ソート部分の最初の要素と交換します。

例えば、配列が [5, 3, 8, 4, 2] で最小値 2 が見つかった場合、2 と 5 を交換して [2, 3, 8, 4, 5] となります。

繰り返し処理

この手順を配列全体がソートされるまで繰り返します。

次に、未ソート部分 [3, 8, 4, 5] から最小値 3 を見つけて、未ソート部分の最初の要素と交換します。

このプロセスを配列全体がソートされるまで続けます。

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

#include <stdio.h>
// 選択ソート関数
void selectionSort(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 最小値を未ソート部分の最初の要素と交換
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
// 配列を表示する関数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
// メイン関数
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("ソート前の配列: \n");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("ソート後の配列: \n");
    printArray(arr, n);
    return 0;
}

このコードを実行すると、以下のような出力が得られます。

ソート前の配列: 
64 25 12 22 11 
ソート後の配列: 
11 12 22 25 64

このように、選択ソートはシンプルで理解しやすいアルゴリズムですが、大規模なデータセットには向いていないことがわかります。

選択ソートの応用

昇順・降順のソート

選択ソートは、基本的には昇順ソートを行うアルゴリズムですが、少しの変更で降順ソートも実現できます。

以下に、昇順ソートと降順ソートの実装方法を解説します。

昇順ソートの実装

まずは、昇順ソートの実装を見てみましょう。

以下のコードは、選択ソートを用いて配列を昇順にソートする例です。

#include <stdio.h>
void selectionSortAscending(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 最小値を先頭に移動
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSortAscending(arr, n);
    printf("昇順にソートされた配列: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、selectionSortAscending関数が配列を昇順にソートします。

main関数で配列を定義し、ソート関数を呼び出して結果を表示します。

降順ソートの実装

次に、降順ソートの実装を見てみましょう。

昇順ソートのコードを少し変更するだけで、降順ソートが実現できます。

#include <stdio.h>
void selectionSortDescending(int arr[], 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 (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }
        // 最大値を先頭に移動
        temp = arr[max_idx];
        arr[max_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSortDescending(arr, n);
    printf("降順にソートされた配列: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、selectionSortDescending関数が配列を降順にソートします。

昇順ソートと同様に、main関数で配列を定義し、ソート関数を呼び出して結果を表示します。

配列のサイズ変更

選択ソートは固定サイズの配列に対しても動作しますが、動的にサイズを変更する場合には注意が必要です。

C言語では、mallocやrealloc関数を使用して動的にメモリを確保することができます。

以下に、動的に配列のサイズを変更しながら選択ソートを行う例を示します。

#include <stdio.h>
#include <stdlib.h>
void selectionSort(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int *arr;
    int n;
    printf("配列のサイズを入力してください: ");
    scanf("%d", &n);
    arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("メモリの確保に失敗しました\n");
        return 1;
    }
    printf("配列の要素を入力してください:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    selectionSort(arr, n);
    printf("昇順にソートされた配列: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

このコードでは、ユーザーから配列のサイズと要素を入力させ、動的にメモリを確保して選択ソートを行います。

最後に、free関数で確保したメモリを解放します。

動的配列のソート

動的配列のソートも、基本的には固定サイズの配列と同じ方法で行えます。

動的配列を使用する場合、メモリ管理が重要です。

以下に、動的配列を使用して選択ソートを行う例を示します。

#include <stdio.h>
#include <stdlib.h>
void selectionSort(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int *arr;
    int n;
    printf("配列のサイズを入力してください: ");
    scanf("%d", &n);
    arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("メモリの確保に失敗しました\n");
        return 1;
    }
    printf("配列の要素を入力してください:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    selectionSort(arr, n);
    printf("昇順にソートされた配列: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

このコードは、動的にメモリを確保して選択ソートを行う例です。

ユーザーから配列のサイズと要素を入力させ、動的にメモリを確保して選択ソートを行います。

最後に、free関数で確保したメモリを解放します。

大規模データのソート

選択ソートは小規模なデータセットに対しては有効ですが、大規模なデータセットに対しては効率が悪いです。

選択ソートの時間計算量はO(n^2)であり、大規模データのソートには適していません。

大規模データをソートする場合、クイックソートやマージソートなどの効率的なソートアルゴリズムを使用することをお勧めします。

以下に、クイックソートを使用して大規模データをソートする例を示します。

#include <stdio.h>
#include <stdlib.h>
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}
int main() {
    int *arr;
    int n;
    printf("配列のサイズを入力してください: ");
    scanf("%d", &n);
    arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("メモリの確保に失敗しました\n");
        return 1;
    }
    printf("配列の要素を入力してください:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    quickSort(arr, 0, n - 1);
    printf("昇順にソートされた配列: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    free(arr);
    return 0;
}

このコードは、クイックソートを使用して大規模データをソートする例です。

ユーザーから配列のサイズと要素を入力させ、動的にメモリを確保してクイックソートを行います。

最後に、free関数で確保したメモリを解放します。

選択ソートは学習目的や小規模データのソートには適していますが、大規模データのソートには効率的なアルゴリズムを使用することが重要です。

選択ソートの性能

時間計算量

選択ソートの時間計算量は、アルゴリズムの効率を評価するための重要な指標です。

選択ソートは、最悪の場合でも平均の場合でも、O(n^2)の時間計算量を持ちます。

これは、配列の要素数が増えると、処理時間がその二乗に比例して増加することを意味します。

選択ソートの時間計算量を具体的に見てみましょう。

選択ソートは、以下のような手順で動作します。

配列の最初の要素から始めて、最小の要素を見つける。
最小の要素を配列の先頭に移動する。
次に、配列の2番目の要素から始めて、再び最小の要素を見つける。
この手順を配列の最後まで繰り返す。

この手順では、各ステップで配列の要素を比較するため、全体でn(n-1)/2回の比較が行われます。

したがって、時間計算量はO(n^2)となります。

実際のパフォーマンス

選択ソートの実際のパフォーマンスは、データのサイズや初期状態によって異なります。

選択ソートは、データがほぼ整列されている場合でも、完全にランダムな場合でも、同じ時間計算量を持ちます。

これは、選択ソートが常に全ての要素を比較するためです。

空間計算量

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

これは、選択ソートが追加のメモリをほとんど使用しないことを意味します。

選択ソートは、配列内の要素を直接交換するため、追加の配列やリストを必要としません。

このため、選択ソートはメモリ効率が非常に高いアルゴリズムと言えます。

メモリ使用量

選択ソートのメモリ使用量は、入力データのサイズに依存しません。

選択ソートは、入力データをその場で並べ替えるため、追加のメモリをほとんど消費しません。

これは、特にメモリが限られている環境で有用です。

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

#include <stdio.h>
// 選択ソート関数
void selectionSort(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 最小値を先頭に移動
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
// 配列を表示する関数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
// メイン関数
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("元の配列: \n");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("ソート後の配列: \n");
    printArray(arr, n);
    return 0;
}

このプログラムを実行すると、以下のような出力が得られます。

元の配列: 
64 25 12 22 11 
ソート後の配列: 
11 12 22 25 64

この例では、選択ソートが配列を昇順に並べ替えています。

選択ソートのアルゴリズムは、シンプルで理解しやすいですが、大規模なデータセットには向いていないことがわかります。

選択ソートの利点と欠点

利点

実装の簡単さ

選択ソートの最大の利点の一つは、その実装の簡単さです。

選択ソートは非常に直感的で理解しやすいアルゴリズムです。

基本的な考え方は、配列の中から最小(または最大)の要素を見つけ、それを配列の先頭に移動するというものです。

この操作を繰り返すことで、配列全体をソートすることができます。

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

#include <stdio.h>
void selectionSort(int arr[], 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 (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 最小値を見つけたら交換
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i=0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

このコードは、配列 arr を昇順にソートします。

選択ソートのアルゴリズムは非常にシンプルで、初心者でも理解しやすいです。

メモリ効率

選択ソートはインプレースソートアルゴリズムの一つであり、追加のメモリをほとんど必要としません。

これは、配列内の要素を直接交換するため、追加の配列やリストを作成する必要がないからです。

したがって、選択ソートはメモリ効率が非常に高いと言えます。

欠点

パフォーマンスの限界

選択ソートの最大の欠点は、そのパフォーマンスです。

選択ソートの時間計算量は O(n^2) であり、大規模なデータセットに対しては非常に非効率です。

これは、配列の各要素に対して最小値を見つけるために、残りの要素全てを比較する必要があるためです。

例えば、配列のサイズが 1000 の場合、選択ソートは約 1,000,000 回の比較を行う必要があります。

これは、他の効率的なソートアルゴリズム(例えば、クイックソートやマージソート)の O(n log n) の時間計算量と比較すると非常に遅いです。

他のソートアルゴリズムとの比較

選択ソートは、そのシンプルさとメモリ効率の高さから、小規模なデータセットや教育目的には適しています。

しかし、実際のアプリケーションでは、より効率的なソートアルゴリズムが好まれます。

以下に、選択ソートと他の一般的なソートアルゴリズムの比較を示します。

アルゴリズム	時間計算量(平均)	時間計算量(最悪)	空間計算量	安定性
選択ソート	O(n^2)	O(n^2)	O(1)	×
バブルソート	O(n^2)	O(n^2)	O(1)	○
挿入ソート	O(n^2)	O(n^2)	O(1)	○
クイックソート	O(n log n)	O(n^2)	O(log n)	×
マージソート	O(n log n)	O(n log n)	O(n)	○

この表からわかるように、選択ソートは他のソートアルゴリズムと比較してパフォーマンスが劣ります。

特に、大規模なデータセットに対しては、クイックソートやマージソートの方がはるかに効率的です。

以上のように、選択ソートにはいくつかの利点と欠点があります。

選択ソートを使用する際には、データセットのサイズや用途に応じて、他のソートアルゴリズムと比較検討することが重要です。

選択ソートの改善方法

選択ソートはシンプルで理解しやすいアルゴリズムですが、パフォーマンスの面では他のソートアルゴリズムに劣ることがあります。

ここでは、選択ソートの改善方法についていくつかのアイデアを紹介します。

改善のアイデア

二分選択ソート

二分選択ソートは、選択ソートの一種で、通常の選択ソートよりも効率的に動作します。

このアルゴリズムでは、配列の最小値と最大値を同時に見つけ出し、それぞれを配列の先頭と末尾に配置します。

これにより、ソートの回数を半分に減らすことができます。

他のソートアルゴリズムとの組み合わせ

選択ソートを他のソートアルゴリズムと組み合わせることで、パフォーマンスを向上させることができます。

例えば、選択ソートをクイックソートやマージソートと組み合わせることで、特定の条件下でのパフォーマンスを最適化することが可能です。

実装例

以下に、二分選択ソートの実装例を示します。

このコードは、配列の最小値と最大値を同時に見つけ出し、それぞれを配列の先頭と末尾に配置します。

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

改善された選択ソートのコード

上記の二分選択ソートのコードは、通常の選択ソートよりも効率的に動作します。

次に、他のソートアルゴリズムと組み合わせた例を示します。

ここでは、選択ソートと挿入ソートを組み合わせたハイブリッドソートを実装します。

#include <stdio.h>
void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
void hybridSelectionSort(int arr[], int n) {
    int threshold = 10; // 挿入ソートに切り替える閾値
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
        // 閾値を超えたら挿入ソートに切り替える
        if (n - i - 1 <= threshold) {
            insertionSort(arr, i + 1, n - 1);
            break;
        }
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11, 90, 45, 33, 21, 78};
    int n = sizeof(arr)/sizeof(arr[0]);
    hybridSelectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

パフォーマンス比較

選択ソート、二分選択ソート、ハイブリッドソートのパフォーマンスを比較するために、以下の表を参考にしてください。

アルゴリズム	時間計算量 (平均)	空間計算量	特徴
選択ソート	O(n^2)	O(1)	シンプルで実装が容易
二分選択ソート	O(n^2)	O(1)	最小値と最大値を同時に選択
ハイブリッドソート	O(n^2)	O(1)	小規模データに対して効率的