Slashdot Mirror
Ask Slashdot: How Do You Sort?
camperdave writes "I was recently going through a pile of receipts and other papers to put them into order by date. Lacking one of those fancy sorting sticks they have at the office, I wound up with all sorts of piles and I was getting confused as to which pile was for what. Finally, it struck me: Why don't I use one of the many sorting algorithms I learned back in my computer science classes? So I swept all the papers back into the box and did a radix sort on them. It worked like a charm. Since then, I've had occasion to try quicksorts and merge sorts. So, when you have to physically sort things, what algorithm (if any) do you use?"
The obligatory xkcd
http://www.geoffreylandis.com
Given that your pile was probably pretty well sorted to begin with, a bubble sort could actually have been the best solution. After all, the pile probably grew in chronological order.
I just drop a pile of papers on the staircase, and then repeat if they did not land in the right order.
In theory there is no difference between theory and practice. In practice there is. - Yogi Berra
I find Shredsort to be the fastest.
Can the shader units of a GPU be harnessed to accelerate sorting?
They can, but you have to either use a very slow GPU, or have very fast fingers.
Ezekiel 23:20
Human sorting tends to be rather ad-hoc, and this isn't necessarily a bad thing. Yes, if someone is sorting a large number of objects/papers according to a simple criterion, then they are likely to be implementing a version of some sort of formal searching algorithm... But one of the interesting things about a human sorting things is that they can, and do, leverage some of their intellect to improve the sorting. Examples: ...).
1. Change sorting algorithm partway through, or use different algorithms on different subsets of the task. E.g. if you are sorting documents in a random order and suddenly notice a run that are all roughly in order, you'll intuitively switch to a different algorithm for that bunch. In fact, humans very often sub-divide the problem at large into stacks, and sub-sort each stack using a different algorithm, before finally combining the result. This is also relevant since sometimes you actually need to change your sorting target halfway through a sort (when you discover a new category of document/item; or when you realize that a different sorting order will ultimately be more useful for the high-level purpose you're trying to achieve;
2. Pattern matching. Humans are good at discerning patterns. So we may notice that the documents are not really random, but have some inherent order (e.g. the stack is somewhat temporally ordered, but items for each given day are reversed or semi-random). We can exploit this to minimizing the sorting effort.
3. Memory. Even though humans can't juggle too many different items in their head at once, we're smart enough that we encounter an item, we can recall having seen similar items. Our visual memory also allows us to home-in on the right part of a semi-sorted stack in order to group like items.
The end result is a sort that is rather non-deterministic, but ultimately successful. It isn't necessarily optimal for the given problem space, but conversely their human intellect is allowing them to generate lots of shortcuts during the sorting problem. (By which I mean, a machine limited to paper-pushing at human speed, but implementing a single formal algorithm, would take longer to finish the sort... Of course in reality mechanized/computerized sorting is faster because each machine operation is faster than the human equivalent.)
I punch 3 holes in every receipt: one each for parent, left, and right. Then I attach them all by string, in a balanced tree. If I need multiple search keys, I just use different colors of string, and different sets of holes. Rebalancing can be a bit of a bitch, after insertion. (I never delete.)
HSJ$$*&#^!#+++ATH0
NO CARRIER
First by rank (13 buckets) then by suit (4 buckets). I can typically sort a well-shuffled deck of bridge cards in about 85 seconds. That's far from the world record, but significantly faster than most people can do.
Assuming the bottom of the pile is the oldest....
1) decide how tall you would like the pile.
2) move that much of the pile to a temp location.
3) remove the remaining pile to the garbage/recycle/shred bin, as appropriate
4) move the temp pile back to the production pile area.
You never said you were looking for anything... sorting piles of kipple seems to be a rather dull hobby.
This issue is a bit more complicated than you think.
Yes, they are called compute shaders. There are several parallel algorithm, of of which is called the bitonic sort.
http://en.wikipedia.org/wiki/B...
You just load all your data into GPU memory, with one data element per thread, then at each stage, use one thread to compare pairs of data.
There's a very specific pattern which is specified by this web page.
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
When I'm sorting things in meatspace, I use a heap sort.
I throw all the shit into a heap, then pick out the good bits.