2026-08-26
sort_by_abs.c
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {3, -1, 1, -3};
for (int i = 1; i < 4; i++) {
int v = a[i], k = abs(v), j = i;
while (j > 0 && abs(a[j - 1]) >= k) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
}
for (int i = 0; i < 4; i++)
printf("%d ", a[i]);
}
配列を絶対値の小さい順に並べ、絶対値が同じ要素どうしは元の順のまま残すつもりのコードです。配列 {3, -1, 1, -3} を並べて -1 1 3 -3 と出力するはずが、いまは 1 -1 -3 3 と出力されます。
Answer
Wrong
int v = a[i], k = abs(v), j = i;
while (j > 0 && abs(a[j - 1]) >= k) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
挿入ソートは、a[i] を取り出して v に置き、左隣の要素を1つずつ右へずらしながら v を入れる位置を探します。ずらすのをやめるのは、左隣の絶対値が k より小さくなったときです。条件が >= k なので、絶対値が等しい左隣も右へずらされ、v はその前へ入ります。i = 2 の v = 1 では、3 をずらしたあと、元の配列で前にあった -1 もずらし、1 が先頭に来ます。i = 3 の v = -3 も、絶対値が等しい 3 の前へ入ります。
絶対値の順だけを見れば、1 -1 -3 3 も小さい順に並んでいます。崩れているのは、絶対値が同じ組 -1 と 1、3 と -3 の前後で、どちらも元の順と逆になっています。
Right
int v = a[i], k = abs(v), j = i;
while (j > 0 && abs(a[j - 1]) > k) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
条件を > k にすると、絶対値が等しい左隣のところで止まり、v はその後ろに入ります。v より左にある要素は、どれも元の配列で v より前にあったものです。絶対値が等しい要素を追い越さなければ、等しいものどうしは元の順のまま並びます。
i = 2 では 3 をずらしたあと -1 で止まり、配列は -1 1 3 -3 になります。i = 3 の -3 は 3 で止まってその後ろに残るので、出力は -1 1 3 -3 のまま変わりません。