Namaran

Code daily. Without assist.

2026-11-16

sort_points.c

#include <stdint.h>

struct point {
    uint16_t x, y;
};

uint32_t morton(uint16_t x, uint16_t y);

int cmp_morton(const void* a, const void* b) {
}

morton(x, y) は、x の各ビットを偶数番目、y の各ビットを奇数番目に交互に並べた32ビットの値を返します。qsort で struct point の配列をこの値の小さい順に並べられるように、比較関数 cmp_morton を書いてください。a と b は配列の要素を指し、a の値が小さければ負、等しければ0、大きければ正を返します。例では、配列の要素を (x,y) で書き、並べる前と後の配列を示します。

入力例 1

(1,1)(0,1)(1,0)(0,0)

出力例 1

(0,0)(1,0)(0,1)(1,1)

入力例 2

(65535,65535)(0,0)

出力例 2

(0,0)(65535,65535)

入力例 3

(2,0)(1,1)

出力例 3

(1,1)(2,0)
Reference

Reference

#include <stdint.h>

struct point {
    uint16_t x, y;
};

uint32_t morton(uint16_t x, uint16_t y);

int cmp_morton(const void* a, const void* b) {
    const struct point* p = a;
    const struct point* q = b;
    uint32_t zp = morton(p->x, p->y);
    uint32_t zq = morton(q->x, q->y);
    return (zp > zq) - (zp < zq);
}

qsort は要素の型を知らないので、比較関数には要素を指す const void* を渡します。C では void* から別のオブジェクト型へのポインタへキャストなしで代入できるので、まず const struct point* の変数に受け、それぞれの morton の値を求めます。掲載したのは参考実装で、唯一の正解ではありません。

戻り値の (zp > zq) - (zp < zq) は、比較の結果が int の 0 か 1 になることを使っています。zp が大きければ 1 - 0 で 1、小さければ 0 - 1 で -1、等しければ 0 です。return zp - zq; と差を返すと、入力例 2 で壊れます。(65535,65535) の値はすべてのビットが立った 0xFFFFFFFF、(0,0) は 0 です。uint32_t どうしの差は uint32_t のまま 0xFFFFFFFF になり、これは int に収まりません。収まらない値を int に変換した結果は処理系定義で、GCC では -1 になるので、大きいほうの点が前に並びます。

入力例 1 では、4点の値は (0,0) が 0、(1,0) が 1、(0,1) が 2、(1,1) が 3 です。入力例 3 では (2,0) が 4、(1,1) が 3 なので、x が大きい (2,0) のほうが後ろに来ます。x や y の順で並べるのではなく、交互に並べたビットの値の順で並べるからです。