選択ソートは、配列中の最小値を探し、それを配列の先頭側の要素と交換することで整列を行うアルゴリズムである。このアルゴリズムは、配列中の最小値を探し、それを配列の 1 番目の要素と交換する。続いて、配列中の 2 番目に小さい値を探して、その値を配列の 2 番目の要素と交換する。この操作を配列が終わるまで繰り返すことで、配列を整列される。

選択ソートは、i 回目の探索に i 番目に小さい値を配列の i 番目の位置の要素と交換を行なっている。この際に、配列の 1, 2, ..., i - 1 番目の位置にある要素は整列済みであるので、最小値の探索は配列の i, i + 1, ..., n 番目の位置から調べることになる。そのため、配列を整列させるためには探索する合計回数は n + (n - 1) + ... + 2 + 1 = n(n+1)/2 であり、その計算量は O(n²) である。選択ソートのアルゴリズムの探索回数は、バブルソートの探索回数と同じだが、値の交換回数は選択ソートの方が少ない。そのため、全体的に見たとき、選択ソートの方が比較的に速い。

#include <stdio.h>

void selectionSort(int array[], int array_size) {
    int i, j, m, min;

    for (i = 0; i < array_size - 1; i++) {
        m = i;
        for (j = i + 1; j < array_size; j++) {
            if (array[j] < array[m]) {
                m = j;
            }
        }

        min = array[m];
        array[m] = array[i];
        array[i] = min;
    }
}


int main (void) {

    int i;
    int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};

    printf("       array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    selectionSort(array, sizeof(array) / sizeof(array[0]));

    printf("sorted array: ");
    for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}