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か所を入れ替えるので、間にある等しいキーの要素との前後関係が変わります。