Namaran

Code daily. Without assist.

2026-11-10

pick.c

#include <stdio.h>

int pick(int* a, int n, int k) {
    int p = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] <= a[n - 1]) {
            int t = a[i];
            a[i] = a[p];
            a[p++] = t;
        }
    }
    return k < p - 1 ? pick(a, p - 1, k) : k >= p ? pick(a + p, n - p, k - p) : a[k];
}

int main(void) {
    int a[] = {8, 2, 0, 1, 6, 3, 5};
    printf("%d\n", pick(a + 3, 4, pick(a, 4, 2)));
}

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

Answer

Output

6

pick は Quickselect です。for は最後の要素 a[n - 1] をピボットにし、ピボット以下の要素を見つけた順に前へ集めます。ピボット自身も a[i] <= a[n - 1] を満たし、しかも最後に調べられるので、集めた範囲の末尾 a[p - 1] に収まります。この時点でピボットより前にはそれ以下の値だけ、後ろにはそれより大きい値だけがあり、ピボットは並べ替えたときの位置にいます。return は、k がピボットの位置ならその値を返し、そうでなければ k を含む側だけで同じことを繰り返します。

そのため pick(a, n, k) は a[0..n-1] の中で小さい方から k + 1 番目の値を返し、戻ったときの配列では a[k] がその値になっています。a[k] より前には a[k] 以下の値が、後ろには a[k] 以上の値が並ぶので、途中の交換を追わなくても、どの位置にどの値の範囲が来るかはここから決まります。

内側の pick(a, 4, 2) は {8, 2, 0, 1} から3番目に小さい 2 を返します。戻ったとき a[2] は 2 で、その後ろの a[3] は2以上の値です。4つのうち2以上で残っているのは 8 だけなので、a[3] は 8 に決まります。外側の pick(a + 3, 4, 2) は a[3] から始まる4つ、{8, 6, 3, 5} から3番目に小さい値を選びます。並べると 3, 5, 6, 8 なので、出力は 6 です。

内側の呼び出しが配列を並べ替えたことを忘れると、a[3] を元の 1 のまま読み、{1, 6, 3, 5} の3番目の 5 と答えます。2つの呼び出しは範囲が a[3] で重なっており、外側が使う a[3] は内側の選択が終わったあとの値です。分割の交換を1回ずつ追っても {0, 1, 2, 8} にたどり着きますが、a[3] を決めるのに必要なのは、選んだ値より後ろにはそれ以上の値しか来ないという性質だけです。