(Before I explain - I had 5 megabytes to compress a gif of literal noise haha, so please forgive how absolutely crunchy it is. Below is a much higher quality video version!)
Ok, so here's the problem:
How do you sort a 2D array in 2 dimensions at once?
For example, in the above gif, I'm sorting both hue and lightness to make the final rainbow. Sounds simple to sort, until you consider two issues:
- You have to stick to the grid - you can't double up pixels.
- In normal situations, you'll have data that skews to certain hues.
The real-world scenario I encountered this in was my desire to sort player-made characters in a grid, by color. I can plot them by color, and I can place them in a grid arbitrarily, but how can I do both?
The solution I ended up with is what I call JostleSort™:
- I swap pixels with their nearby neighbors if doing so would make them more sorted.
- The swapping occurs further away if the pixel thinks it's less sorted.
- It "jostles" it around a bit, like sifting sand, in order to avoid local minima and stalemates.
My solution is honestly very slow, and it feels like a brute force solution. But I can't think of a better way to do it... can you think of any ideas?
Here's a much higher quality video than the first one (if you're on desktop at least; on mobile, Streamable compresses it a lot more), however I must warn you: tragically, it ends too early! Unfortunately I had to stop it so I could sleep.
For further research: the general problem in this post is one of dimensionality reduction. My concept feels similar to gradient descent, but... nothing seems to consider sorting things in a packed 2D array?
