2D sort
In The Farmer Was Replaced there is a subgame in which you are to sort a 2D field. I tried several options and liked the 2D insertion-sort algorithms the most. It’s exactly what I want to speak about today.
First of all, let’s recall what we can do in the game. There is:
🌵 move(East|North|West|South) for movement;
🌵 till() to switch soil type;
🌵 plant() to, sorry, plant different, sorry, plants;
🌵 swap(East|North|West|South) to swap the current cell with a neighbouring cell in a given direction;
🌵 harvest() to harvest ripe plants.
This story is about cacti. You have an enormous bonus if you harvest the whole field at once — and it happens when all cacti are sorted.
What does “sorted” mean here?
🌵 For each cell: measure() <= measure(East) and measure() <= measure(North) (when those neighbours exist).
🌵 In other words: each row goes in non-decreasing left-to-right order and each column goes in non-decreasing bottom-to-up order.
Now let’s check the picture. In our algorithm we traverse the field right-to-left, top-to-bottom, and apply one “insertion” iteration to each new cactus we meet. For a new cactus a[p][q] the invariant is:
the subfield to the right and above is already sorted.
In one sorting iteration our task is to move a[p][q] to its place inside that already-sorted piece and not to break the order we already have.
At first I tried to reason directly:
if our cactus is lower than both of its upper and right neighbours, it should already be in place.
If it is taller than the right one but lower than the upper one, we swap with the right.
If it is taller than both neighbours… wow, wow, wow… stop.
Too many ifs. Hard to think about, hard to write a program — and we haven’t even started to handle borders (top row, rightmost column, missing neighbours).
When I stumbled upon it, I recalled that it reminds me something… exactly: sift_down in a heap. And there is a clever trick one can use.
Two stages.
Stage 1: take up to three cells — current, right, and up (skip the neighbours that don’t exist) — and find the minimum value among them.
This is a very common mini-routine, so it’s easy to implement even with strict movement/swap restrictions.
Stage 2: make a decision.
If the minimum is at our current position — do nothing, we’re done.
Otherwise swap the current cell with the cell that holds the minimum, move to that swapped position, and repeat.
That’s it. No giant decision tree.
Let’s check the complexity of this approach.
Worst case: T = O(n³).
We have n² elements and for each of them insertion can travel O(n) steps through the already-sorted region.
Bad news is that it can be quite long on a totally shuffled field.
Good news is that insertion sort takes advantage of partial sorting and won’t do unnecessary work.