MENU

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

この記事では、初心者向けにC言語の選択ソートについて解説します。

目次から探す

選択ソートの仕組み

選択ソートは、配列の中から最小値を選び、それを先頭の要素と交換するという操作を繰り返すことで、配列を昇順にソートするアルゴリズムです。

以下では、選択ソートの手順と例題について説明します。

選択ソートの手順

  1. 配列の先頭から順に、最小値を探します。
  2. 最小値を見つけたら、それを先頭の要素と交換します。
  3. 先頭の要素を除いた残りの部分に対して、同じ操作を繰り返します。
  4. ソートが完了するまで、上記の操作を繰り返します。

選択ソートの例題

以下の例を使って、選択ソートの手順を具体的に見てみましょう。

例題:配列 [5, 2, 8, 3, 1] を昇順にソートする

  1. 最小値を探すため、配列の先頭から順に要素を比較します。

最小値は1です。

  1. 最小値1を先頭の要素と交換します。

配列は [1, 2, 8, 3, 5] となります。

  1. 先頭の要素を除いた残りの部分に対して、同じ操作を繰り返します。
  2. 次に最小値を探すため、配列の2番目の要素から順に要素を比較します。

最小値は2です。

  1. 最小値2を2番目の要素と交換します。

配列は [1, 2, 8, 3, 5] のままです。

  1. 同様に、残りの要素に対しても最小値を探し、交換を繰り返します。
  2. 最終的に、配列は [1, 2, 3, 5, 8] の昇順にソートされます。

選択ソートの実装方法

選択ソートを実装するためには、以下の基本的な実装方法を理解する必要があります。

また、最適化の方法についても紹介します。

選択ソートの基本的な実装

選択ソートを実装するためには、以下の手順に従います。

  1. 配列の先頭から順に、最小値を探します。
  2. 最小値を見つけたら、それを先頭の要素と交換します。
  3. 先頭の要素を除いた残りの部分に対して、同じ操作を繰り返します。
  4. ソートが完了するまで、上記の操作を繰り返します。

以下は、C言語での選択ソートの基本的な実装例です。

#include <stdio.h>
void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    for (i = 0; i < n-1; i++) {
        minIndex = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
int main() {
    int arr[] = {5, 2, 8, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    printf("ソート後の配列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

上記のコードでは、selectionSort関数で選択ソートを実装しています。

arrはソートする配列であり、nは配列の要素数です。

selectionSort関数内で、最小値を探し、要素を交換する操作を繰り返しています。

最後に、ソート後の配列を表示しています。

選択ソートの最適化

選択ソートは、要素の交換回数が多いという欠点があります。

この欠点を改善するために、以下の最適化方法があります。

  • 最小値の探索を行わず、最大値を探すようにする。
  • 交換操作を行わず、最小値(または最大値)のインデックスを記録しておき、最後に一度だけ交換する。

これらの最適化方法を組み合わせることで、選択ソートの性能を向上させることができます。

以上が、選択ソートの仕組みや実装方法についての解説です。

選択ソートはシンプルなアルゴリズムですが、理解して実装することで、配列のソートができるようになります。

目次から探す