Сортування Гільберта

Розміщення елементів у базах даних відповідно до числового ключа не лише спрощує пошук конкретного елемента, але й сприяє ефективнішому використанню кешу центрального процесора: будь-який неперервний сегмент пам'яті містить елементи з близькими значеннями ключів. Це особливо корисно, наприклад, при доступі до всіх елементів, ключі яких лежать у заданому діапазоні.

Ситуація ускладнюється, якщо ключі являють собою точки на двовимірній сітці, як це відбувається, наприклад, у системах GPS-навігації. Якщо точки $(x,y)$ сортувати спочатку за $x$, а потім за $y$, то елементи, розташовані поруч у пам'яті, матимуть однакові значення $x$, але можуть суттєво відрізнятися за $y$. Водночас точки з однаковими значеннями $y$ можуть знаходитися далеко одна від одної на площині. Для кращого збереження просторової локальності дані сортують вздовж неперервної кривої, що заповнює простір.

Розглянемо одну з таких кривих — криву Гільберта. Вона починається в точці $(0,0)$ і закінчується в $(S,0)$, проходячи через усі точки квадрата з вершинами $(0,0)$ та (S, S). Крива будується рекурсивно таким чином: квадрат ділиться на чотири рівні частини зі спільною точкою (S/2, S/2), після чого кожна частина заповнюється зменшеною і відповідним чином повернутою копією повної кривої Гільберта.

Спочатку заповнюється нижній лівий квадрат — крива проходить від $(0,0)$ до (0, S/2). Потім заповнюється верхній лівий квадрат — від (0, S/2) до (S/2, S/2). Після цього обробляється верхній правий квадрат — від (S/2, S/2) до (S, S/2). Нарешті, заповнюється нижній правий квадрат — від (S, S/2) до $(S,0)$.

З іншого боку, криву Гільберта можна розглядати як граничний об'єкт послідовності ламаних, перші кілька з яких показані на рисунку.

Вам задано набір точок, які потрібно відсортувати в порядку їх обходу кривою Гільберта. Незважаючи на те що крива самоперетинається нескінченну кількість разів (наприклад, у точці (S/2, S/2)), умова непарності числа $S$ гарантує, що кожна точка з цілочисельними координатами відвідується рівно один раз.