Namaran

Code daily. Without assist.

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 のまま変わりません。