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
Some days I use one; other days I use the other.
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.
By throwing all the files in the trash, you will create more filing space and avoid potential fire hazards.
It's a truly revolutionary filing system which eases my pyloric valve.
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
46.3.1 Implementing Odd-Even Merge Sort http://http.developer.nvidia.c...
send + more == money?
They don't let us call them secretaries anymore, but I agree with stevegee58. Let an administrative assistant sort, or better yet run them through a Fujitsu SnapScan and then let the computer do the sorting.
0 Give every item a number.
1 enter the date in excel.
2 Enter the number in excel.
3 Add one other search criteria in excel
4 Sort in excell/
Leave the papers alone. If you need to find a certain date, you know what numbers to look for.
5 swear at person that threw them in the wrong order.
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.
Sorting things alphabetically, as in the original example, I tend to start with a bucket sort, with the number of buckets depending on how many things I'm alphabetizing. This works well because I don't have to keep any state in memory other than what buckets there are (and if things are bad enough, I can do two stages of buckets - often mimicking a binary search in reverse, if there's a massive number). Once I've gotten everything at least first-letter alphabetized, I go through with a mergesort on each bucket, or if I'm able to hold all the documents or books at once, I just do an insertion sort.
However, whenever I need to sort a deck of cards (to make sure it's a full deck, for instance), I just play a game of Klondike solitaire, cheating as needed. It's slower, sure, but more fun that way.
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.
Which fits with something which characterizes most effective sorting algorithms: they get rid of a lot of entropy early on. This works for tidying the house too. Start by throwing out stuff, then by moving things to the room they belong in, then putting them away.
To answer the question, I tend to quick sort things into manageable unsorted piles, insertion sort the piles and reassemble the piles.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.