2026-08-26
stable_qsort.c
int cmp_by_value(const void* a,
const void* b) {
}
ptrs は、int の配列 scores の各要素を指すポインタを、添字の順に並べた配列です。qsort(ptrs, n, sizeof ptrs[0], cmp_by_value) で ptrs を指す先の値の小さい順に並べ、値が等しいものどうしは scores での順のまま残るように、比較関数 cmp_by_value を書いてください。a と b は ptrs の要素を指し、a を前に置くべきなら負、後ろに置くべきなら正を返します。例では、入力に scores の中身を、出力に並べたあとの ptrs が指す要素の添字を書きます。
入力例 1
{2, 1, 2, 1}
出力例 1
1 3 0 2
入力例 2
{5, 5, 5}
出力例 2
0 1 2
入力例 3
{3, 2, 1}
出力例 3
2 1 0
Reference
Reference
int cmp_by_value(const void* a,
const void* b) {
const int* p = *(const int* const*)a;
const int* q = *(const int* const*)b;
if (*p != *q)
return (*p > *q) - (*p < *q);
return (p > q) - (p < q);
C の規格は、qsort が等しいと判定された要素どうしをどの順に置くかを決めていません。比較関数が0を返した2つの要素は、元の順のまま残るとも、入れ替わるとも限らないということです。そこで、指す先の値が等しいときも0を返さず、scores の中での位置で前後を決めます。比較関数が0を返すのは同じ要素どうしを比べたときだけになり、並べ終えた結果は1通りに決まります。掲載したのは参考実装で、唯一の正解ではありません。
位置を比べるのに添字は要りません。ptrs の要素はどれも同じ配列 scores の要素を指しているので、p > q のような大小比較が使え、その結果は添字の大小と一致します。別々の配列を指すポインタどうしの大小比較は未定義動作ですが、ここではその心配がありません。a が指すのは型が const int* の ptrs の要素なので、const int* const* に変換してから1回たどると、scores の要素を指すポインタが取り出せます。
入力例 1 では、値1の scores[1] と scores[3] が位置の順に先頭へ並び、値2の scores[0] と scores[2] が続くので 1 3 0 2 になります。入力例 2 はすべての値が等しく、位置だけで並ぶので元の 0 1 2 のままです。値どうしを (*p > *q) - (*p < *q) で比べているのは、差 *p - *q を返すと、値の差が int に収まらないときに符号が壊れるからです。