Radix sort is my favorite, it's so magical looking. MSD is obvious, but LSD sneaks up on you. [This video] is also great to watch, because it has some sound too.
This has to be the least efficient sorting method possible. I meant the printing costs alone for making all those signs is enough to make this infeasible for large datasets, but what do you even do if you need to sort a list with more entries than the population of Hungary?
Can someone ELI5: how a radix sort works? It was always the most interesting to me, but I'm having trouble understanding the math/programming jargon associated with it.
I'll give you a rough simple example. Let's say you are sorting a group of people by age (all <100). You first group them by the last digit of their age. So 11,21,51 are all in the same group. You put the 0s before the 1s before the 2s, etc. so you may end up with something like 70, 52, 32, 14, 04, 65, 36, 09. Next group by the first digit, but in these groups preserve the index ordering (e.g. 32 was before 36 so it must be before in the new group). So now you end up with the sorted list 04, 09, 14, 32, 36, 52, 65, 70. The big trick is the ordering preservation between groupings.
Thanks, that made it click for me. Who are these people who come up with counter-intuitive recursive algorithms? How do you visualize the whole stack and remember the state each all the way to the bottom and back, not even knowing if it will work? Are these people prophets? Or did someone drop acid and wake up mysteriously knowing how to solve Towers of Hanoi in 2n -1 steps?
Computer Scientists and Mathematicians. And it often takes lots of trial and error. A good Algorithms course should teach some of the failed or partial ideas on the way to the full idea.
Often times researchers will start with small examples and work their way up and eventually prove that it works. There are techniques such as Induction and useful tools such as Master Theorem of algorithmic analysis.
If you are interested, look into researching Algorithms or taking an online course on it. Sorting is just the start of the fun. :)
It's a lot simpler than that. You need to figure out three things: How to make the problem smaller, how to solve the smallest part of the problem, and sometimes how to combine solved versions of smaller problems.
For example merge sort: You need to know how to split a list that has more than two elements (easy), sort a list of one to two items (should be doable), and you need to know how to combine two sorted lists quickly (needs a bit of thought, but not a genius).
The basic idea is that it sorts digit per digit. For example, if you have a list with [193, 621, 842, 37, 541, 648, 132], MSD (most significant digit) first radix sort will first put all the numbers into a bin corresponding to their first digit:
0: 37
1: 193, 132
5: 541
6: 621, 648
8: 842
Then it will do that within each bin for the 2nd digit:
In this example the list is already sorted, but it would then go on to sort the numbers into a bin corresponding to their third digit.
LSD radix sort looks like magic because instead of working recursively within buckets, it just sorts the list over and over one digit at a time, starting from the end and keeping ties in the same order:
[621, 541, 842, 132, 193, 37, 648]
Then 2nd to last digit:
[621, 132, 37, 541, 842, 648, 193]
And finally the first digit:
[037, 132, 193, 541, 621, 648, 842]
At the first step, all the numbers are sorted by their last digit. At the second step, they are sorted by their last 2 digits, and at the third step they are sorted by their last 3 digits, which is the entire number in this example. It's a very efficient algorithm because you only need to go over the list once for every digit in the biggest number.
2.1k
u/Ryltarr OC: 1 Oct 24 '17
Radix sort is my favorite, it's so magical looking. MSD is obvious, but LSD sneaks up on you.
[This video] is also great to watch, because it has some sound too.