【C言語】選択ソートの比較回数はいくら？もっと早いソートはある？

2023-09-102024-06-03

この記事では、C言語を使った選択ソートの基本から実装方法、そしてその性能について詳しく解説します。

また、選択ソートと他のソートアルゴリズム(バブルソート、挿入ソート、クイックソート、マージソートなど)との比較や、もっと高速なソートアルゴリズム(ヒープソート、ラディックスソート)についても紹介します。

最後に、選択ソートの利点と欠点、そして適切なソートアルゴリズムの選び方についても触れます。

初心者の方でも理解しやすいように、サンプルコードや具体例を交えて説明しますので、ぜひ参考にしてください。

目次から探す

選択ソートとは

選択ソートは、配列の要素を順番に比較しながら並べ替えるシンプルなソートアルゴリズムの一つです。

選択ソートは、特に小規模なデータセットに対しては理解しやすく、実装も簡単なため、学習用としてよく使われます。

選択ソートの基本概念

選択ソートの基本的な考え方は以下の通りです：

配列の中から最小(または最大)の要素を見つける。
その要素を配列の先頭に移動する。
残りの配列について同じ操作を繰り返す。

この操作を配列全体に対して行うことで、配列が昇順(または降順)に並べ替えられます。

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

選択ソートのアルゴリズムは以下のステップで構成されます：

配列の最初の要素から始めて、最小の要素を見つける。
見つけた最小の要素と現在の要素を交換する。
次の要素に移動し、再び最小の要素を見つけて交換する。
配列の最後までこの操作を繰り返す。

具体的な手順は以下の通りです：

配列の最初の要素を仮の最小値とする。
配列の残りの要素と仮の最小値を比較し、より小さい値が見つかればそれを新しい最小値とする。
配列の最後まで比較を続け、最小値が見つかったら、最初の要素と交換する。
次の要素に移動し、同じ操作を繰り返す。

選択ソートの実装例(C言語)

以下に、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

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

選択ソートは、各ステップで最小の要素を見つけて交換するため、理解しやすく、実装も簡単です。

しかし、効率の面では他のソートアルゴリズムに劣ることが多いです。

次のセクションでは、選択ソートの性能について詳しく見ていきます。

選択ソートの性能分析

時間計算量

選択ソートの時間計算量は、入力データのサイズに依存します。

ここでは、最良の場合、平均の場合、最悪の場合の時間計算量について詳しく見ていきます。

最良の場合

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

選択ソートは、データが既にソートされているかどうかに関わらず、全ての要素を比較するため、最良の場合でも (O(n^2)) の時間がかかります。

平均の場合

選択ソートの平均の場合の時間計算量も (O(n^2)) です。

データの並び順に関わらず、全ての要素を比較して最小値を見つけるため、平均的なケースでも (O(n^2)) の時間が必要です。

最悪の場合

選択ソートの最悪の場合の時間計算量も (O(n^2)) です。

最悪の場合でも、全ての要素を比較して最小値を見つける必要があるため、時間計算量は変わりません。

空間計算量

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

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

つまり、入力データのサイズに関わらず、一定のメモリしか使用しないため、空間計算量は非常に効率的です。

比較回数の具体例

選択ソートの比較回数は、データセットのサイズに依存します。

ここでは、小規模データセットと大規模データセットでの比較回数を具体的に見ていきます。

小規模データセットでの比較回数

例えば、5つの要素を持つデータセットの場合、選択ソートの比較回数は以下のようになります。

最初の要素を選択するために4回の比較
次の要素を選択するために3回の比較
次の要素を選択するために2回の比較
次の要素を選択するために1回の比較

合計で (4 + 3 + 2 + 1 = 10) 回の比較が行われます。

大規模データセットでの比較回数

例えば、1000個の要素を持つデータセットの場合、選択ソートの比較回数は以下のようになります。

最初の要素を選択するために999回の比較
次の要素を選択するために998回の比較
次の要素を選択するために997回の比較
…

このように続き、合計で (\frac{n(n-1)}{2}) 回の比較が行われます。

具体的には、1000個の要素の場合、499500回の比較が必要です。

選択ソートはシンプルで理解しやすいアルゴリズムですが、比較回数が多いため、大規模なデータセットには向いていません。

次に、他のソートアルゴリズムと比較して、選択ソートの性能を見ていきましょう。

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

バブルソート

アルゴリズムの概要

バブルソートは、隣接する要素を比較し、必要に応じて交換することでリストをソートするシンプルなアルゴリズムです。

リストの末尾から始めて、隣接する要素を比較し、順序が逆であれば交換します。

この操作をリスト全体に対して繰り返し、リストが完全にソートされるまで続けます。

時間計算量と比較回数

バブルソートの時間計算量は以下の通りです。

最良の場合: O(n)(リストが既にソートされている場合)
平均の場合: O(n^2)
最悪の場合: O(n^2)

バブルソートの比較回数は、最悪の場合で n(n-1)/2 回となります。

これは、選択ソートと同じく O(n^2) の時間計算量を持つため、効率が良いとは言えません。

挿入ソート

アルゴリズムの概要

挿入ソートは、リストを部分的にソートされた部分と未ソートの部分に分け、未ソートの要素を順次ソートされた部分に挿入していくアルゴリズムです。

具体的には、リストの先頭から順に要素を取り出し、ソート済みの部分に適切な位置に挿入します。

時間計算量と比較回数

挿入ソートの時間計算量は以下の通りです。

最良の場合: O(n)(リストが既にソートされている場合)
平均の場合: O(n^2)
最悪の場合: O(n^2)

挿入ソートの比較回数は、最悪の場合で n(n-1)/2 回となります。

バブルソートや選択ソートと同様に、効率が良いとは言えませんが、リストがほぼソートされている場合には効率的です。

クイックソート

アルゴリズムの概要

クイックソートは、分割統治法を用いた効率的なソートアルゴリズムです。

リストの要素の中から1つの要素(ピボット)を選び、ピボットより小さい要素と大きい要素に分割します。

その後、分割された部分に対して再帰的にクイックソートを適用します。

時間計算量と比較回数

クイックソートの時間計算量は以下の通りです。

最良の場合: O(n log n)
平均の場合: O(n log n)
最悪の場合: O(n^2)(ピボットの選び方が悪い場合)

クイックソートの比較回数は、平均的には O(n log n) となり、選択ソートやバブルソート、挿入ソートよりも効率的です。

マージソート

アルゴリズムの概要

マージソートも分割統治法を用いたソートアルゴリズムです。

リストを半分に分割し、それぞれの部分を再帰的にマージソートでソートします。

最後に、ソートされた部分をマージして1つのソート済みリストにします。

時間計算量と比較回数

マージソートの時間計算量は以下の通りです。

最良の場合: O(n log n)
平均の場合: O(n log n)
最悪の場合: O(n log n)

マージソートの比較回数は、常に O(n log n) となり、安定した効率を持つため、選択ソートやバブルソート、挿入ソートよりも優れています。

ただし、追加のメモリが必要となる点がデメリットです。

もっと早いソートアルゴリズム

選択ソートはシンプルで理解しやすいアルゴリズムですが、効率の面では他のソートアルゴリズムに劣ります。

ここでは、選択ソートよりも高速なソートアルゴリズムとして、ヒープソートとラディックスソートを紹介します。

ヒープソート

アルゴリズムの概要

ヒープソートは、データ構造の一つであるヒープを利用したソートアルゴリズムです。

ヒープは完全二分木の一種で、親ノードが子ノードよりも大きい(または小さい)という特性を持ちます。

ヒープソートは以下の手順で行われます。

配列をヒープ構造に変換する(ヒープ化)。
ヒープの最大値(または最小値)を取り出し、末尾の要素と交換する。
ヒープのサイズを1減らし、再度ヒープ化する。
2と3を繰り返し、全ての要素がソートされるまで続ける。

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

#include <stdio.h>
// ヒープ化関数
void heapify(int arr[], int n, int i) {
    int largest = i; // 親ノード
    int left = 2 * i + 1; // 左の子ノード
    int right = 2 * i + 2; // 右の子ノード
    // 左の子ノードが親ノードより大きい場合
    if (left < n && arr[left] > arr[largest])
        largest = left;
    // 右の子ノードが親ノードより大きい場合
    if (right < n && arr[right] > arr[largest])
        largest = right;
    // 親ノードが最大でない場合
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 再帰的にヒープ化
        heapify(arr, n, largest);
    }
}
// ヒープソート関数
void heapSort(int arr[], int n) {
    // 配列をヒープに変換
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // ヒープから要素を取り出し、ソート
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // ヒープ化
        heapify(arr, i, 0);
    }
}
// 配列を表示する関数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
// メイン関数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array is \n");
    printArray(arr, n);
    return 0;
}

時間計算量と比較回数

ヒープソートの時間計算量は、最良、平均、最悪の場合すべてで O(n log n) です。

これは、選択ソートの O(n^2) よりも効率的です。

ヒープソートは比較回数が少なく、安定した性能を発揮します。

ラディックスソート

アルゴリズムの概要

ラディックスソートは、数値の各桁を基にしてソートを行うアルゴリズムです。

基数ソートとも呼ばれます。

ラディックスソートは、以下の手順で行われます。

最下位桁から始めて、各桁ごとにソートを行う。
各桁のソートには安定なソートアルゴリズム(例：カウントソート)を使用する。
最上位桁までソートを繰り返す。

以下に、C言語でのラディックスソートの実装例を示します。

#include <stdio.h>
#include <stdlib.h>
// 最大値を取得する関数
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}
// カウントソート関数
void countSort(int arr[], int n, int exp) {
    int* output = (int*)malloc(n * sizeof(int));
    int count[10] = {0};
    // カウント配列を初期化
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    // カウント配列を累積和に変換
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    // 出力配列を構築
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    // 出力配列を元の配列にコピー
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
    free(output);
}
// ラディックスソート関数
void radixSort(int arr[], int n) {
    int m = getMax(arr, n);
    // 各桁ごとにカウントソートを実行
    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}
// 配列を表示する関数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
// メイン関数
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    printf("Sorted array is \n");
    printArray(arr, n);
    return 0;
}

時間計算量と比較回数

ラディックスソートの時間計算量は O(d * (n + k)) です。

ここで、d は数値の桁数、n は配列の要素数、k は基数(通常は10)です。

ラディックスソートは、特定の条件下で非常に高速に動作しますが、数値の桁数が多い場合や基数が大きい場合には効率が低下することがあります。

以上のように、ヒープソートとラディックスソートは選択ソートよりも高速なソートアルゴリズムです。

データの特性や用途に応じて、適切なソートアルゴリズムを選択することが重要です。

選択ソートの利点と欠点

利点

実装の簡単さ

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

選択ソートは直感的で理解しやすいアルゴリズムであり、プログラミング初心者でも容易に実装することができます。

以下に、選択ソートの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;
    }
}
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;
}

このコードは、選択ソートの基本的な動作を示しています。

アルゴリズムは、配列の中から最小の要素を見つけ、それを配列の先頭に移動するという操作を繰り返します。