2026-11-10
kth.c
#include <stdio.h>
int kth(int* a, int n, int k) {
int pivot = a[n / 2];
int p = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= pivot) {
int t = a[i];
a[i] = a[p];
a[p++] = t;
}
}
return k < p - 1 ? kth(a, p - 1, k) : k >= p ? kth(a + p, n - p, k - p) : a[k];
}
int main(void) {
printf("%d\n", kth((int[]){4, 9, 7, 1, 8, 3, 6}, 7, 3));
}
配列 a を小さい順に並べ替えたとき添字 k の位置に来る値を、配列を並べ替えながら探す kth です。もとは最後の要素をピボットにしていましたが、整列済みの入力で毎回の分割が偏らないよう、真ん中の要素 a[n / 2] をピボットにしました。{4, 9, 7, 1, 8, 3, 6} と k = 3 を渡すと、本来は 6 が出力されるはずが、いまは 8 が出力されます。
Answer
Wrong
int pivot = a[n / 2];
int p = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= pivot) {
int t = a[i];
a[i] = a[p];
a[p++] = t;
}
}
return k < p - 1 ? kth(a, p - 1, k) : k >= p ? kth(a + p, n - p, k - p) : a[k];
return の行は、a[p - 1] にピボットがあり、そこが並べ替えたときの位置だと決めつけています。ところが for はピボット以下の値を見つけた順に前へ詰めるだけなので、a[p - 1] に来るのは、ピボット以下の値のうち最後に見つかったものです。最後の要素がピボットだったころは、ピボットが必ず最後に調べられたので、この2つが一致していました。真ん中の要素をピボットにすると、ピボットより後ろにあるピボット以下の値がその後に詰められ、ピボットは範囲の途中に取り残されます。
入力例では、1回目のピボット 1 は唯一の該当値なので正しく a[0] に来ます。2回目は残りの {9, 7, 4, 8, 3, 6} をピボット 8 で分け、{7, 4, 8, 3, 6, 9} になります。a[p - 1] にいるのは 8 ではなく最後に詰めた 6 で、return はこれをピボットとみなして、左側の {7, 4, 8, 3} だけを調べ直します。答えの 6 はここで候補から外れ、残りから選ばれた 8 が出力されます。
Right
int pivot = a[n / 2];
a[n / 2] = a[n - 1];
a[n - 1] = pivot;
int p = 0;
for (int i = 0; i < n; i++) {
if (a[i] <= pivot) {
int t = a[i];
a[i] = a[p];
a[p++] = t;
}
}
return k < p - 1 ? kth(a, p - 1, k) : k >= p ? kth(a + p, n - p, k - p) : a[k];
真ん中の要素を最後の要素と入れ替えてから分割します。ピボットに選ぶ値は真ん中の要素のままですが、置き場所が末尾になるので、for はピボットを必ず最後に調べ、ピボット以下の値を詰め終えた範囲の末尾 a[p - 1] に置きます。こうすれば a[p - 1] より前はピボット以下、後ろはピボットより大きい値だけになり、return の行が前提にしていることが成り立ちます。ピボットと同じ値がいくつあっても、ピボット自身が最後に詰められることは変わりません。