Namaran

Code daily. Without assist.

2026-08-26

selection_sort.c

#include <stdio.h>

int main(void) {
    const char* a[] = {
        "b1", "b2", "b3", "a1"};
    for (int i = 0; i < 3; i++) {
        int m = i;
        for (int j = i + 1; j < 4; j++)
            if (a[j][0] < a[m][0])
                m = j;
        const char* t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
    for (int i = 0; i < 4; i++)
        printf("%s\n", a[i]);
}

これは何を出力するでしょうか?

Answer

Output

a1
b2
b3
b1

このループは選択ソートで、i 番目から後ろのうち頭文字がいちばん小さい要素を探し、i 番目と入れ替えます。比べるのは頭文字の a[j][0] だけなので、"b1"、"b2"、"b3" は互いに等しいキーです。i = 0 では、後ろから見つかる 'a' の "a1" が最小になり、0番目の "b1" と入れ替わります。配列は a1 b2 b3 b1 になり、"b1" は2つの 'b' を飛び越えて末尾へ移ります。

i = 1 と i = 2 では、残りはどれも頭文字が 'b' です。比較は < なので、等しい要素では m が更新されず、i 番目は自分自身と入れ替わるだけです。最初の交換で崩れた b2 b3 b1 の順は、そのまま最後まで残ります。

頭文字で並べるのだから、'b' どうしは元の順のまま a1 b1 b2 b3 になる、と読むと外れます。等しいキーの要素が元の順を保つのは、隣どうしだけを動かす挿入ソートのような並べ方の性質です。選択ソートは離れた2か所を入れ替えるので、間にある等しいキーの要素との前後関係が変わります。