3 ms·
I had a similar problem at a previous job. I was given bundles of orders that needed to be sorted and filed. Being the old days, these orders were sheets of pap
by pbiggar 14y ago
I had a similar problem at a previous job. I was given bundles of orders that needed to be sorted and filed. Being the old days, these orders were sheets of paper with numbers on them, and "filed" meant in filing cabinets.
I fairly quickly moved to an algorithm that I would later learn was MSB radix-sort. Basically, I made one iteration and divided them into buckets with the same value in the "hundreds" column, and then recurse into each pile and repeat for the "tens" column, then a quick sort for the final 10 orders.
As a concrete example, lets say I had 150 orders with order numbers between 7200 and 7499. Organize into piles containing the 7200s, the 7300s and the 7400s. Then take the 7200s, and split it into piles for 7200s, 7210s, 7220s, etc.
In sorting algorithms, it common to use insertion sort for the final step (actually, people often use any O(N^2) sort, but really should only ever use insertion sort because its the most efficient O(N^2) sort in terms of instruction count, cache locality, and branch mispredictions).
- chris_wot 14y agoI've been thinking about this algorithm. If you had millions of items, then wouldn't the process of dividing into buckets, and then sorting these buckets which are massive take a long time? Unless of course you recursively sort each bucket into sub-buckets...
- lotharbot 14y agoIt's typical to recurse until you're down to small enough sets to easily sort using some other algorithm (usually insertion sort on groups < 10 elements.)
- pbiggar 14y agoWith radixsort, you don't even need to. By the time you get to the deepest bucket, all the entries have an identical prefix and unique suffix. So they can all be sorted in O(N). You could construct situations where it would be faster to switch to insertion sort (maybe radix of 2, stop 3 recursions from the end), but in practice you'd pick a radix better (with a radix of 8, you could do the entire thing in 4 recursions and the final recursion over 64 items is faster than insertion sort of 64 items, probably). Note that you'd generally use LSB radixsort over MSB radixsort, so you'd have a set number of passes over the array, and no recursion.
- pbiggar 14y agoYou recursively sort each bucket into subbuckets, and there is a known recursion limit (3 in this case). Here's code for an LSB radix sort, which doesn't recurse, but is the same idea: https://github.com/pbiggar/sorting-branches-caching/blob/master/code/sorts/base_radixsort.c https://github.com/pbiggar/sorting-branches-caching/blob/mas...