2D сортировка
В игре The Farmer Was Replaced есть подигра, в которой вам предстоит сортировать 2D-поле. Я попробовал несколько вариантов, и мне больше всего понравились алгоритмы 2D-сортировки вставками. Именно об этом я хочу сегодня поговорить.
Прежде всего, давайте вспомним, что мы можем делать в игре. Существует:
🌵 move(East|North|West|South) для перемещения;
🌵 till() для смены типа почвы;
🌵 plant() для посадки растений;
🌵 swap(East|North|West|South) для обмена текущей ячейки с соседней в указанном направлении;
🌵 harvest() для сбора созревших растений.
Эта история о кактусах. У вас есть огромный бонус, если вы уберете все поле сразу — и это происходит, когда все кактусы отсортированы.
Что здесь означает «отсортировано»?
🌵 Для каждой ячейки: measure() <= measure(East) и measure() <= measure(North) (если эти соседи существуют).
🌵 Другими словами: каждая строка идет в неубывающем порядке слева направо, а каждый столбец — в неубывающем порядке снизу вверх.
Теперь проверим картинку. В нашем алгоритме мы проходим поле справа налево, сверху вниз и применяем одну итерацию «вставки» к каждому новому кактусу, который встречаем. Для нового кактуса a[p][q] инвариант:
подполе справа и выше уже отсортировано.
За одну итерацию сортировки наша задача — переместить a[p][q] на его место внутри уже отсортированного фрагмента и не нарушить уже имеющийся порядок.
Сначала я попытался рассуждать прямо:
если наш кактус ниже, чем его верхний и правый соседи, он уже должен быть на месте.
Если он выше правого, но ниже верхнего, меняем местами с правым.
Если он выше обоих соседей… вау, вау, вау… стоп.
Слишком много «если». Трудно об этом думать, сложно написать программу — и мы даже не начали обрабатывать границы (верхняя строка, крайний правый столбец, отсутствующие соседи).
Когда я уткнулся в эту логику, понял, что она напоминает sift_down в куче. И здесь есть удобный трюк.
Два этапа.
Этап 1: взять до трёх ячеек — текущую, правую и верхнюю (пропустить несуществующих соседей) — и найти среди них минимальное значение.
Это стандартная мини-рутина, поэтому ее легко реализовать даже при жестких ограничениях на перемещения и обмены.
Этап 2: принять решение.
Если минимум находится в нашей текущей позиции — ничего не делайте, все готово.
В противном случае поменяйте местами текущую ячейку на ячейку, содержащую минимум, перейдите к этой замененной позиции и повторите.
Вот и все. Никакого гигантского дерева решений.
Давайте проверим сложность этого подхода.
Худший случай: T = O(n³).
У нас есть n² элементов, и для каждого из них вставка может пройти O(n) шагов через уже отсортированную область.
Плохая новость заключается в том, что на полностью перетасованном поле это может занять довольно много времени.
Хорошая новость заключается в том, что сортировка вставками использует преимущества частичной сортировки и не выполняет ненужной работы.