2026-09-19
sort_overflow.c
#include <stdio.h>
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
int main(void) {
int values[] = {2000000000, -2000000000, 0, 5};
qsort(values, 4, sizeof(int), cmp_int);
for (int i = 0; i < 4; i++)
printf("%s%d", i ? " " : "", values[i]);
printf("\n");
}
valuesを昇順に並べるつもりですが、このコンパレータでは正しくソートされないことがあります。何が問題で、どう直せばよいでしょうか?
Answer
*(const int *)a - *(const int *)bは、2つの値が十分離れていると引き算の結果がintの範囲に収まらず、符号付き整数オーバーフローという未定義動作を起こします。ここでは2000000000 - (-2000000000) = 4000000000となり、intの最大値(2147483647)を超えます。qsortのコンパレータは「aが大きいなら正、小さいなら負、等しいなら0」を常に一貫して返す必要がありますが、オーバーフローするとその前提が崩れ、この全順序としての一貫性(推移性)が保証できなくなります。結果としてソートが正しく行われる保証はなくなります。引き算ではなく、大小比較だけから-1・0・1を作る方法に直せば、オーバーフローそのものが起こりません:
int cmp_int(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}