3 ms·

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 thing

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.

gus_massa 5y ago
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?).
tgb 5y ago
What's the optimal sorting algorithm for your Bridge hand? Sorting and holding 13 cards is tricky enough to make me wonder.
- yodelshady 5y ago
  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.
- thehappypm 5y ago
  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.
pezezin 5y ago
Something like this? https://en.wikipedia.org/wiki/Pancake_sorting https://en.wikipedia.org/wiki/Pancake_sorting

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 thing

gus_massa 5y ago

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?).

tgb 5y ago

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

yodelshady 5y ago
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.
thehappypm 5y ago
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.

pezezin 5y ago

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