【図解】選択ソート：アルゴリズム【C言語】

本記事では、基本的なソートの一種である「選択ソート」のアルゴリズム解説・C言語による実装を確認していきます。

アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。

ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。

本記事でわかること

選択ソートの基本的な情報
アルゴリズムの流れ
C言語による実装方法

こちらの記事で、他のソートアルゴリズムをまとめています。

>>ソートアルゴリズム　計算量・特徴一覧

アルゴリズム入門書はこの一冊で十分！

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

created by Rinker

¥3,938 （2020/09/01現在 Amazon調べ・詳細）

1 選択ソートとは
2 選択ソートのアルゴリズム
3 選択ソートの実装【C言語】

選択ソートとは

選択ソートは、ソートアルゴリズムの一種であり、比較的簡単なソートです。

基本的な情報は以下になります。

最悪計算時間 \(O\)	安定性
\(O(n^2)\)	安定ではない

選択ソートは、「最小値を見つけては前に持っていき、また最小値を見つけては～」と繰り返すことで、全体をソートするアルゴリズムです。

イメージとしては、トランプを並び替える動きに近いです。

一番小さな数字から順番に左側に並べていく感じ。

また、バブルソートや挿入ソートと同じく、左端から徐々にソート済み部分が増えていくアルゴリズムとなっています。

>>【図解】バブルソート：アルゴリズム【C言語】

>>【図解】挿入ソート：アルゴリズム【C言語】

次の章で具体的な動きを確認していきます。

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

まずは、軽く全体的な流れを確認し、その後、図を用いた説明へと移ります。

選択ソートのアルゴリズムは以下のようになります。

配列のサイズを\(n\)としたとき、以下の処理を\(n – 1\)繰り返す。

未ソート部分の中から最小値の位置を特定する。
未ソート部分の先頭要素と、①で求めた最小値を交換する。

さっそく実例を見ていきましょう。

今回は、サイズが８の配列で昇順ソートの具体例を見ていきます。

ここでは、配列の初期状態を次のようにします。

初期状態では、すべての要素が未ソート部分となりますね。

では、上で確認したアルゴリズム通りに動かしていきます。

まずは、未ソート部分において最小値の位置を特定します。

最小値の位置を特定する方法は何でもいいのですが、一般的な方法として、配列の先頭から順番に見ていく方法があります。

この場合、未ソート部分の最小値は「１」です。

最小値の位置を特定したら、その値「１」と未ソート部分の先頭要素「８」を交換します。

これで、左側の１つの要素がソート済みとなりました。

後は、同様の処理を繰り返していきます。

もう１セット確認していきましょう。

まずは、未ソート部分の中から最小値を特定します。

今回は、「２」が最小値です。

最小値を特定したら、その値「２」と未ソート部分の先頭要素「３」と交換します。

これで、左側の2つの要素がソート済みとなりました。

選択ソートは、「最小値を見つけては前に持っていく」という単純な処理を繰り返すため、容易に理解できるかと思います。

では、ここまで行ってきた分を２セット分とし、ここからは１セットおきの配列の状態を示していきます。

これで配列の要素すべてがソート済みとなりました。

選択ソートは、最小値を前方に移動していくため、必ず最後に最大値が残ります。

そのため、7セット目で２つ同時にソート済み部分が増えています。

ここまでが選択ソートアルゴリズムの動きとなります。

次の章では、これをC言語で実装していきます。

実際に自分の手で実装することで、より理解が深まるので、是非確認してみてください。

選択ソートの実装【C言語】

さっそく、プログラム全体のコードを示します。

#include <stdio.h>
#define N 8

// 配列の全ての要素を出力する
void printArray(int A[], int n) {
    for (int i = 0; i < n; i++) {
        if (i == 0)
            printf("%d", A[i]);
        else
            printf(" %d", A[i]);
    }
    printf("\n");
}

// 配列の要素を入れ替える
void swap(int A[], int a, int b) {
    int temp;
    temp = A[a];
    A[a] = A[b];
    A[b] = temp;
}

// 選択ソートを行う
void selectiveSort(int A[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;

        // 未ソート部分内の最小値の位置を特定する
        for (int j = i+1; j < n; j++)
            if (A[j] < A[min_idx])
                min_idx = j;

        // 未ソート部分の先頭要素と最小値を交換
        swap(A, i, min_idx);
    }
}

int main(void) {
    int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

    printArray(A, N);   // ソート前の配列の要素を表示
    selectiveSort(A, N);   // 選択ソートを実行する
    printArray(A, N);   // ソート後の配列の要素を表示
    return 0;
}

#include <stdio.h>

#define N 8

// 配列の全ての要素を出力する

void printArray(int A[], int n) {

for (int i = 0; i < n; i++) {

if (i == 0)

printf("%d", A[i]);

else

printf(" %d", A[i]);

}

printf("\n");

}

// 配列の要素を入れ替える

void swap(int A[], int a, int b) {

int temp;

temp = A[a];

A[a] = A[b];

A[b] = temp;

}

// 選択ソートを行う

void selectiveSort(int A[], int n) {

for (int i = 0; i < n-1; i++) {

int min_idx = i;

// 未ソート部分内の最小値の位置を特定する

for (int j = i+1; j < n; j++)

if (A[j] < A[min_idx])

min_idx = j;

// 未ソート部分の先頭要素と最小値を交換

swap(A, i, min_idx);

}

int main(void) {

int A[N] = {8, 3, 5, 1, 7, 4, 2, 6};

printArray(A, N); // ソート前の配列の要素を表示

selectiveSort(A, N); // 選択ソートを実行する

printArray(A, N); // ソート後の配列の要素を表示

return 0;

}

長々としていますが、選択ソート本体は、24~36行目の selectiveSort関数の中で実装しています。

選択ソートの実装はソートアルゴリズムの中でも最も容易であるため、詳細の解説は割愛します。

selectiveSort関数のループ内で、配列の要素が交換されるたびに要素を出力するようなコードを書き加えると、前の章で確認したような数値の並びになることが確認できるかと思います。

では、今回はここまでとします。

お疲れさまでした。

別のソートを確認したい方は、ソートアルゴリズム　計算量・特徴一覧をご覧ください。