fuss•y•spi•der | ˈfəsēspīdər |
noun
an eight-legged arachnid who has an intense desire to keep her web neat and clean
verb
to clean one’s home, especially whilst adopting the persona of “Miss Fussyspider”: my studio is totally transliminal, I need to fussyspider the fuck out of it.
trans•lim•i•nal | tranzlimənl, translimənl |
adjective
1 messy, and stressfully so: I feel much better now that my studio is less transliminal.
…or in other words, I just beat back a lot of the chaos that’s accumulated due to conventions over the past month, and I feel a lot better about my working space now!
One of these days I really need to do that comic about sorting algorithms starring Ms. Fussyspider. “I prefer to use cycle sort when organizing the corpses of my previous lovers, as it minimizes the number of husks I have to haul around. But now that you’re here to help I can use quicksort* instead – it’s much faster!”
* sorts mentioned may not actually have these qualities, I haven’t done the research for that comic yet.
Cycle sort is the optimum solution when it comes to physically moving things around. Quicksort actually isn’t all that good in general; its best case only matches mergesort, and its worst case is as bad as bubble sort. Neither is very good for physical movements though. Recursive sorting strategies also require keeping track of a lot more state.
Also, apparently, spiders only kill/eat their mates if they’re in a situation where they’re low on food or worried for their own safety. (Same with praying mantises as well.)
Ha, thanks! I’ll probably continue to be unrealistic on the “eating mates” because creepy spider lady, but sorting notes are good.
Oh, by the way, any sorting algorithm can be used as the basis of an optimal shuffling-around if you have O(n) spare memory to store the final state in (and then it takes at most O(n) swap operations to put things in the final positions). You just have to be able to take notes and figure out where everything’s going first.
The advantage to cycle sort is that it doesn’t require any external state-tracking to determine this optimum shuffle, and in the case of hauling carcasses around that’s probably the bottleneck, not the sorting itself.
Basically, cycle sort takes O(n^2) comparisons and O(n) swaps. Most other in-place sorting algorithms take O(n lg n) comparisons, and O(n lg n) swaps. In-place QuickSort takes as much as O(n^2) for both – not very efficient. :)
These videos may be helpful. Or they may not. YMMV. https://www.youtube.com/user/AlgoRythmics