Ask Slashdot: How Do You Sort? 195
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?"
Ob xkcd (Score:5, Funny)
The obligatory xkcd [xkcd.com]
Re: (Score:1)
Tiny bubbles
in the Wine.org
Re: (Score:2)
"We don't. We declare chaos as the standard."
I agree, as long as you wash on cold sorting should not be an issue.
Bucket sort or bin sort (Score:2, Funny)
Some days I use one; other days I use the other.
Bubble sort (Score:3, Insightful)
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.
Re: Bubble sort (Score:2)
Yes - the Pile sort... (Score:5, Funny)
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.
Re: (Score:3)
Gaston Lagaffe (belgian comics character) had a similar pile sort method, somewhat more elegant.
1) pile stuff next to the table/desk's border
2) wait so much that you have multiple piles, horizontally arranged
2) when you have too many piles, push them so that the first one falls off the table
I can't google it successfully, so instead here's this one : Gaston sorts an office cupboard's content http://jfmabut.blog.tdg.ch/media/02/01/979637923.jpg [blog.tdg.ch]
Re: (Score:3)
Re: (Score:2)
I scan all of my receipts, bills, product manuals, boxes, etc. into my PC and recycle the physical waste. This way I can quickly and easily sort and search. It also makes it simple to make backups or place copies online that I can access at any time from anywhere.
Interesting. So, do you OCR the scan? Or do you tag the resulting scan somehow? How do you store them? PDFs? Maybe Microsoft OneNote?
Re: (Score:2)
Yeah, but bubbles are messy, but they are fun, but it's so hard to get them in order with them floating around, and people popping them. That's the worst. Just once I have them all in order, someone goes and pops one of them. I could never figure out where to put the bubbles that have another bubble inside them.
merge sort (Score:1)
if you are piling your receipts up chronologically, it should be merge sort
Bogosort (Score:5, Funny)
Shredsort (Score:5, Funny)
I find Shredsort to be the fastest.
Re:Shredsort (Score:5, Funny)
Hmm, that's O(n).
Trashsort is O(1)
Re: (Score:3, Funny)
Hmm, that's O(n).
Trashsort is O(1)
But IdentityTheftSort is O(n!).
Re: (Score:3)
I just compromise - when I have a large amount of old paperwork I need to dispose of, rather than waste time overheating my shredder, I just toss piles into a sink of hot water, stir a bit, crumple, tear, knead, then put in a trash bag, preferably on "fish night", after dinner.
Since I work from home, I can wait until just be
Re: (Score:2)
Re: (Score:2, Funny)
> But IdentityTheftSort is O(n!).
I thought it was O(noes!) ?
Re: (Score:2)
Hmm, that's O(n).
Bah, you just need a bigger shredder! [wikipedia.org]
Re: (Score:2)
Assistant-sort is by far the least work though.
Re: (Score:2)
So you use virtualization to sort?
Trippy.
Ditto. (Score:2)
Any of the more complex algorithms just don't work well in the real world - You either need too much (brain) stack space, or too much extra storage (desktop), to make it worth doing.
Re: (Score:2)
Actually for small sets insertion-sort is probably the easiest and is O(n) or faster when executed by a processor that can simultaneously observe the entire sorted list in a medium that allows O(1) insertions at any point. Bubble-sort on the other hand is horribly tedious.
GPUs (Score:1)
Re:GPUs (Score:5, Funny)
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.
Re: (Score:3)
Re: (Score:2)
Re:GPUs (Score:4, Interesting)
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... [wikipedia.org]
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.
I'd say heapsort (Score:2)
given that what I have would be characterized as a "piling" system... but in fact it ends up being a merge sort generally, with individual stores sorted by bubble sort before the merge.
The Ignatius P. Reilly System (Score:3)
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.
Re: (Score:2)
Actually...
Way back when, I had a filing system that worked fairly well for me. It was "On my desk." Everything that I got was put near me. Over time, it would end up being buried by other things. As those stacks got too high, it would be pushed away from me to create space for new items. So I could find things on my desk based on when I last used it. Stuff that I used often was close by, stuff that I didn't use was far away from me.
Eventually, things would fall off the desk and the cleaning people wo
Radix sort (Score:2)
Usually by whites and colors. (Score:2)
Re: (Score:1)
Racist.
How About SecretarySort? (Score:2)
How about Administrative Assistant sort? (Score:3)
the ultimate sort (Score:1)
Bucket sort followed by insertion sort (Score:1)
Bucket sort to keep each individual stack small enough for the following insertion sort.
Re: (Score:2)
Bucket sort to keep each individual stack small enough for the following insertion sort.
I think that's what people generally do: Bucket sort anything more than a couple dozen items, and insertion sort anything less.
I've tried various other sorting algorithms on decks of cards just for educational purposes. I've found them to be mostly very hard for humans to perform. I think that's probably because what's usually kept in a computer's stack is not evident in the layout of items, so all that info must be juggled in your head. I think that I remember heapsort being especially hard to keep track o
Give every page a number. (Score:2)
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.
Non-deterministic sort (Score:5, Interesting)
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.)
Re: (Score:2)
Smart people however use the CS sorting algorithms, and not some random, changed partway through, invented on the spot method. And that's because smart people know that the classic CS sorting methods have the optimal complexity among all comparison based sorting algorithms. There simply aren't any better methods that take less work, if you're going to compare iterms pairwise. BT
Re: (Score:3)
And that's because smart people know that the classic CS sorting methods have the optimal complexity among all comparison based sorting algorithms.
And even smarter people know that the classic CS sorting methods ONLY have the optimal complexity among all comparison based sorting algorithms when certain assumptions hold.
Are you are in fact limited to comparison sorts? In practice, you aren't.
I may realize that I don't actually need something chronologically, that I only need it down to a month so I can buck
Re: (Score:2)
Re: (Score:2)
You're confused about bucket sorting and radix sorting.
I doubt it, but you might be. Why do think I am?
You may also want to look at probabilistic and randomized algorithms.
And doing that by hand sounds a treat. Roll a fair dice between each action?
and always beat ad hoc methods devised by the uneducated
I contend for small sets, where the content of the set is known in advance by the sorter, and is largely already in order, that ad hoc human methods can beat formal classical methods.
Why? Because several o
Re: (Score:2)
Receipts I would always attach to an A4-sized paper (if not already that size), give it a serial number, enter it into my administration (GnuCash) using the actual date and add that serial number, and file it. As serial numbers are assigned while filing, no sorting needs to be done.
Years later I can easily find a transaction using GnuCash's search function, and find it in the file with the serial number.
Works like a charm.
And as long as you do this on a regular basis, the receipts end up in your administrat
Re: (Score:2)
And as long as you do this on a regular basis, the receipts end up in your administration more or less sorted by date as well.
It's the "on a regular basis" thing that is the heart of the problem. I've let things pile up, and with GnuCash's date manipulation keyboard shortcuts having things sorted by date makes data entry easier.
My method (Score:5, Funny)
Re: (Score:3)
Your office must be interesting.
Why don't you adopt a b-tree? That way you'll be able to delete. Yet, the best is running several sets of horizontal wires, and attaching each receipt on them (with strings, 1 receipt to many wires) based on the data you want to index...
Or maybe you should start organizing the receipts in blocks in a cabinet, with only directions attached to the wires. But then you'll have an extra lookup... And don't forget to write what you'll add to the cabinet before you do so, somebody m
merge or bin sort (Score:2)
I suppose what could make this story more interesting is what sort of
Two-pass bucket sort (Score:4, Interesting)
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.
Re: (Score:3)
I do not have physical things that need sorting (Score:2)
paper? you are kidding, right?
Insertion Sort (Score:2)
Books on a shelf. A loose binary search then a linear search for a tiny subset of 3-4 books and finally insertion of the book.
I suppose you could call it a hash table- where the whole book is hashed down into a short string... called the TITLE...
Sorting papers or anything? (Score:2)
I name them, and I have individual shelves for them, not necessarily in alphabetical order, but more like groups...like those I'd need for certain purposes. Like...Coils in one section (a matrix/row of various values) and resistors in a increasing value row...like 1 ohm to 20 Mega Ohm. etc. And Capacitors...etc...you get the point. How do I file those? I don't... I just make sure that I'
Context-sensitive (Score:3)
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.
Re: (Score:2)
Physically? (Score:4, Funny)
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.
Combination Insertion and Merge (Score:2)
Re: (Score:2)
I think that that is also how perl does it.
This is how I sort: (Score:2)
One at a time.
In practice... (Score:2)
If I were sorting something alphabetically, I would do radix sort to sort everything by letter, then I do insertion sort on each pile.
I studied computer science too, but I think the overhead of doing a sort with better time complexity actually is a significant hindrance for me to actually use it in practice. I'm never going to sort more than like a hundred things (because I'm lazy), and a computer is never going to take longer than a second to sort a million things. So it makes sense for me to use the sor
I don't sort (Score:2)
Mainly because I'm out of sorts...
Fond memories (Score:2)
Fond memories of bucket-sorting (I always called it bin sorting) on temp jobs in the early 90s. The early 90s had a lot of paper-to-digital temp jobs like that. It was an OK way to pick up cash when "real jobs" were hard to find. Entering insurance claims from paper forms was probably the most interesting. The last time I did anything like this was business reply cards in 2004. That one came off Craigslist. Gigs like that have to be getting few and far between since everybody has a device now. BTW, i
Re: (Score:2)
I'll bite. What joke address was it?
Re: (Score:2)
Nothing particular that I remember. Nothing particularly ingenious--just your standard sexual or scatalogical humor. Sometimes they'd draw a penis on the card or something.
Radix sort well fits human skills (Score:2)
I've got some experience sorting huge stacks of pages. You basically want to maximize the work done per trivial-human-step. If you stick with some algorithm based on binary-comparisons you're missing out on some of the work a brain can do essentially for free.
If you're sorting based on a number, it's a pretty quick easy step to drop the current paper in one of ten piles. If you're sorting by alphabetical then you can do one pass 26 piles (bulky but workable) or two pass (first pass A-F, G-M, N-S, T-Z, secon
Re: (Score:2)
Garbage Truck. (Score:2)
The garbage truck sorts my paperwork for me.
half-bucket sort, runs in N time (Score:2)
For things like receipts, I use a half-bucket sort, which runs in N time.
There are 12 piles, one for each month. Items from the first half of the year go on the bottom of the pile, items from the second half go on the top of the pile. That of course means that physically there are 12 stacks, but logically there are 24 buckets - early January, late January, early February, late February, etc.
The next step is - nothing. For receipts, sorting into 24 buckets is close enough that I'll be able to find what I'm
Re: (Score:2)
damn, no mod points. mod up please.
sonsort (Score:2)
list sonsort( list ) {
static father me;
return me->son("sort!",list);
}
Quicksort (Score:2)
I actually sorted a large stack of numbered papers using quicksort. I chose it because it seemed to work well in the case of slow to move/compare paper.
You pick the pivot, initially at random but with re-selections based on the knowledge of the total set. After that, you can step through the whole stack in a fairly automatic way, paper by paper, easily putting papers into the left/right stacks by just shifting them left and right. No slow paper by paper insertions or other checks. Just a paper by paper step
Bucket sort (Score:2)
always a bucket sort. but they don't teach those in CS courses.
Sorting by bin? (Score:2)
A slightly different question: how do you optimize 'bins' to sort things into? There's a pile of paper on your desk, some of it clearly belongs to one of the multiple projects you're working on, but some belongs to multiple projects. Some are in the pile because they seemed "interesting" or "revelant" in some way to things you're thinking about, but not in ways that are clear or straightforward.
How do you take a random pile of paper and *quickly* come up with the smallest set of categories with at least o
Re: (Score:2)
Box Stapler (Score:2)
However you sort, make sure you staple them to keep your receipts in order.
This is particularly important if you subsequently enter them into an accounting program or even a spreadsheet.
What sort? (Score:2)
Insertion + Merge (Score:2)
First, I construct medium-size piles via insertion sort. That works great as long as there are few enough things that I can spread them all out and see where to insert new ones. Once that gets crowded, I stack that into a pile and put it aside. Repeat until every document is in a sorted stack.
Then I merge-sort the stacks.
All in all, I find it a reasonably efficient method.
But seriously... (Score:2)
Every now and then, I need to sort a stack of a few dozen numbered envelopes in numerical order. The first two digits are the same (year) and the last two digits go up to 70-something.
I once used quicksort, but found it too cumbersome for the task at hand.
What I do now is just deal them into piles by the second digit. Each stack is small enough that it's easy to just eyeball-sort them, starting with the 0 stack and ending at the 7 stack.
The most important question... (Score:2)
I keep all my receipts (and bank statements etc...) in a binder without sorting them. One binder per year (sort of).
If/when I need one of the receipts, I simply look through the binder for the relevant year (s). Time spent per search is a fracion of the time I would need to sort them.
As I usually do not know the date of the receipt when I start looking, sorting by date would not provide a benefit anyway.
Perry Mason sort. (Score:2)
Paul Drake: "Do you know his name?"
Perry Mason: "No"
Paul Drake: "Do you really want me to take all these receipts and compare each against everything else? Do you know how long will it take, Perry?
Perry Mason: "Paul, Just sort these receipts by name and look for duplicates"
Donald Knuth, quoting Erle Stanley Gardener, in the chapter on sorting in the TeX book.
[Quoting from memory, please forgive inaccuraci
52-pick-up (Score:2)
I use the 52-pick-up sort
Shuffle sort into a linear merge (Score:2)
If you remember, the O(N^2) shuffe sort is fastest on piles n =6 So I. make sorted piles of 6. These sorted piles of 6 are done using the brains only internal intutitve sort. Then you linear sort the piles of 6 together. I try to go for as many piles at the same time, not just 2. If fact this is more limited by distance than anything else. Since you are sorting things with a physical representation you need to take the time cost of moving yourself into account. With a deck of cards, there is no move costs
AndySort (Score:2)
O(n*n) Insertion sort (Score:2)
Grab a paper, go through the already sorted papers and put it at the right place. Its n*(n/2) (approximately), because i do no binary search, but search from top/bottom whats more likely to be the shorter way (with some intuition about the already inserted papers). So its O(n)
Re: (Score:2)
O(n^2). Slashdot breaks superscript. Maybe finally a feature, the beta could fix.
Perfect solution (Score:2)
Merge sort (Score:2)
Most teachers I knew naturally used a variant of merge sort when sorting a pile of test papers. Most didn't know anything about formal sorting algorithms.
Hmm, chicken grease works good too and it smells l (Score:1)
Hmm, chicken grease works good too and it smells like "home"
Seriously, "news for nerds eh?"
Re: (Score:1)
wouldn't it be a shame if this thread is the most responded to within the whole topic discussion?
Way to go DICE over-lords.
commander Taco, where are you???
but to stay on topic, Zogs would not be good, Chicken fat is :)
Re: (Score:2)
Inserting a card in the middle of a deck is very easy and can be considered as being O(1): you don't need to move cards one by one to make space for the card you want to insert.
It's exactly the opposite case compared to an array: finding the place is O(1) for an array, the insertion is O(N). With a deck of cards, the insertion is O(1), but finding the place definitely isn't O(1). Could be O(log N), though.
Re: (Score:2)
That depends - the nature of the processor is also inherently different, and can look at far more than one card at a time - spread most of a sorted deck of cards in front of you, and I bet you can find the insertion point for a new card *far* faster than O(log N).
Re: (Score:2)
Re: (Score:2)
For receipts, it takes a little while to identify, so only binary compares are appropriate. Therefore, I'd go thru py pairs, sort the pairs, and stack them together crosswise on the bottom of the pile. That's sort groupsize one. Then take two groups, sort the groups with top-receipt compares, and join the groups and stack on the bottom. You're done when the receipts are all aligned correctly.
Sorting coins, I designate clock positions for each coin type, grab the largest group and slide the group to the quad
Re: (Score:3)
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.
Re: (Score:2)
A rough sort to throw out irrelevant debris reduces the whole task by 90%. It's a lot like code review: once you've thrown out all the useless legacy crap, mercilessly, what's left is a lot more useful and easier to understand.
A rough sort to throw out irrelevant debris reduces the whole task by 90%. It's a lot like code review: once you've thrown out all the useless legacy crap, mercilessly, what's left is a lot easier to rewrite from scratch.
FTFY
Re: (Score:2)
Re: (Score:2)
The way is shut.
These documents were made by those who are dead.
The dead keep their order,
And none may these sort save those who are dead.
The way is shut.
The algorithm that can be named is not the eternal algorithm.