2026-10-17
job_order.c
#include <stdio.h>
static void sort(const char *a[], int n, int k) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && a[j - 1][k] >= a[j][k]; j--) {
const char *t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
int main(void) {
const char *jobs[] = {"a21", "b12", "c22", "d12", "e21"};
sort(jobs, 5, 2);
sort(jobs, 5, 1);
for (int i = 0; i < 5; i++) {
putchar(jobs[i][0]);
}
putchar('\n');
}
これは何を出力するでしょうか?
Answer
bdcae です。
sort は挿入ソートで、内側のループは、左隣の鍵が自分の鍵以上である間、左隣と入れ替わり続けます。等しい鍵の左隣とも入れ替わるので、各要素は同じ鍵の要素をすべて飛び越して、その並びの先頭に入ります。後から来た要素ほど前に出るため、鍵が等しい要素どうしの順は、並べ替えるたびにちょうど逆になります。等しい要素の元の順を保つ並べ替えを安定ソート(stable sort)といいますが、この sort はそうなっていません。
1回目は3文字目の日付で並べます。日付が 1 の a と e は e a に、2 の b、c、d は d c b になり、jobs は e a d c b の順です。2回目は2文字目の優先度で並べます。この順のまま、優先度 1 の d b が b d に、優先度 2 の e a c が c a e に反転し、結果は b d c a e です。
sort を安定だと思って読むと、日付で並べてから優先度で並べる二段の並べ替えが「優先度順、同じ優先度なら日付順」を作るはずなので、答えは bdaec になります。2回目の反転にだけ気付いて1回目を安定だと考えると、dbcea です。実際は2回とも反転するので、同じ優先度の要素は日付の降順に並び、優先度も日付も同じ b と d だけが、2回の反転で元の順に戻ります。比較を >= から > に変えると sort は安定になり、bdaec が出ます。