Hacker News Reader

Comment by yodelshady | Hacker News Reader

Slightly OT, but it always slightly bugs me that sorting algorithms are taught *only* in the context of computers, which obey different physics to sorting things. Has anyone done work on sorting algorithms under different cost functions than just "minimise comparisons"? I'm thinking something like:

1. Allocation of new space is free, at least up to 2x the input size. 2. Moving a contiguous set of elements is as cheap as moving one element. 3. Moving an element, or set of elements, has a cost proportional to the distance moved.

View on HN

Not exactly what you are asking for but ...

To sort ~500 student tests by name, my favorite algorithm is

* Each person grabs a bunch of test. Split the test in 4 piles, using the first letter: A-F, G-L, M-Q, R-Z The same 4 piles for everyone. (I don't remember the exact borders. It may depend on your language. Perhaps 5 piles is better.)

* Each persons grabs a pile. Split each pile in subpiles by the first letter again. If some letter is too popular, split it using the second letter.

* Sort each small subpile, that has only 10-20 tests, probably using insert sort.

* Make a giant pile.

This can be classified as a combination of radix sort and insert sort. It's easy to parallelize to 5-10 persons.

If you later realize there are ~50 more test, just sort them using your favorite method and then use merge them, like in mergesort (or timsort?).

What's the optimal sorting algorithm for your Bridge hand? Sorting and holding 13 cards is tricky enough to make me wonder.

That's the sort of thing I hand in mind, yes. Should probably write what I think I'm doing down.

Though in that specific situation, the sufficiently smart and motivated could probably infer hand information.

Yeah it’s a little different because the human mind isn’t procedural — you can perceive multiple cards at once, at a fuzzy resolution. You look at a hand and see “okay an ace, 3 face cards, some other cards” then scan to resolve. So an optimal algorithm needs to take that cognition into account.

Something like this? https://en.wikipedia.org/wiki/Pancake_sorting

Reply on news.ycombinator.com