Namaran

Code daily. Without assist.

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 が出ます。