Please create an account to participate in the Slashdot moderation system

typodupeerror
For the out-of-band Slashdot experience (mostly headlines), follow us on Twitter, or Facebook. ×

Ask Slashdot: How Do You Sort?195195

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?"
This discussion has been archived. No new comments can be posted.

Ask Slashdot: How Do You Sort?

• Ob xkcd (Score:5, Funny)

on Saturday March 01, 2014 @06:03PM (#46378009) Homepage

The obligatory xkcd [xkcd.com]

• Re: (Score:1)

Tiny bubbles

in the Wine.org

• Bucket sort or bin sort (Score:2, Funny)

by Anonymous Coward

Some days I use one; other days I use the other.

• Bubble sort (Score:3, Insightful)

by Anonymous Coward on Saturday March 01, 2014 @06:06PM (#46378027)

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)

Definitly bubble sort. I usually throw in the Matrix trillogy and if I'm not done, I can follow it up with the extended version of Lord of the Rings. The great thing is that if my wife checks in on me, I'm sorting like mad the whole time!
• Yes - the Pile sort... (Score:5, Funny)

on Saturday March 01, 2014 @06:43PM (#46378227) Journal
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.
• 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)

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.
• 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)

by Anonymous Coward

if you are piling your receipts up chronologically, it should be merge sort

• Bogosort (Score:5, Funny)

on Saturday March 01, 2014 @06:07PM (#46378035) Homepage Journal
I just drop a pile of papers on the staircase, and then repeat if they did not land in the right order.
• Shredsort (Score:5, Funny)

by Anonymous Coward on Saturday March 01, 2014 @06:08PM (#46378049)

I find Shredsort to be the fastest.

• Re:Shredsort (Score:5, Funny)

by Anonymous Coward on Saturday March 01, 2014 @06:26PM (#46378141)

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)

Is dumpster diving ID theft really that much of a threat from old receipts, which generally have no "interesting" information? Seems to me all the juicy ID data has gone digital...

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, Funny)

by Anonymous Coward

> 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.

• Ditto. (Score:2)

I too use radix sort, when I have a large number of unsorted items. I usually use a bidirectional bubble sort for smaller piles (ie, if I need to hold them all in my hand at once). And I've occasionally used a merge sort, which works great when you have to combine a handful of already-sorted piles.

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)

Can the shader units of a GPU be harnessed to accelerate sorting? I'm not sure if sorting is a problem which be adapted that way or not.
• Re:GPUs (Score:5, Funny)

on Saturday March 01, 2014 @06:17PM (#46378089)

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)

46.3.1 Implementing Odd-Even Merge Sort http://http.developer.nvidia.c... [nvidia.com]
• Re: (Score:2)

GPUs are great at doing stuff in parallel, so they should be great for modelling a quantum computer. Then you can use http://en.wikipedia.org/wiki/G... [wikipedia.org]
• Re:GPUs (Score:4, Interesting)

on Saturday March 01, 2014 @07:17PM (#46378343)

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)

on Saturday March 01, 2014 @06:14PM (#46378075) Homepage Journal

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)

I always did radix sort for that. Works nicely. Or was it an N-way merge sort? Sort of an ad hoc mixture of both, depending of the task at hand, I guess.
• Usually by whites and colors. (Score:2)

Sometimes I have to separate by material, but not often.
• Re: (Score:1)

by Anonymous Coward

Racist.

• How About SecretarySort? (Score:2)

Dude, you need to let people who are paid less than you to do menial tasks like this. Seriously.
• How about Administrative Assistant sort? (Score:3)

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.
• the ultimate sort (Score:1)

With real physical sorts I pipe everything to DEV NULL
• Bucket sort followed by insertion sort (Score:1)

by Anonymous Coward

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)

on Saturday March 01, 2014 @06:29PM (#46378157) Journal
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.)
• Re: (Score:2)

Except of course _successful_ sorting is trivial - all it takes is someone to carry through their favourite method until the end.

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)

You're confused about bucket sorting and radix sorting. You may also want to look at probabilistic and randomized algorithms. However, the important point is that best of class algorithms for sorting are already known, and always beat ad hoc methods devised by the uneducated. Given that sorting is rather boring to anyone but a collector or fetishist, there's no excuse for not using the proper algorithm.
• 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)

on Saturday March 01, 2014 @06:30PM (#46378161) Homepage
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.)
• 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)

If I'm sorting stuff lexicographically, I generally use bin sort (often grouping things into four or so large bins first like say A-G, H-M, N-S, and T-Z for sorts on people's surnames). For numerical records, I use merge sort. Sometimes I use both, like for sorting cards (bin sort on suit and then merge sort each suit). It can be quite a time saver when you have to sort a large number of paper records to learn these sorting algorithms.

I suppose what could make this story more interesting is what sort of
• Two-pass bucket sort (Score:4, Interesting)

on Saturday March 01, 2014 @06:42PM (#46378223) Journal

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)

if you have a table to work with sort directly into a 13x4 grid
• 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)

Sorting receipts, is like sorting anything else out there. So...how do I sort my VAST amounts of Electronic components?

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)

on Saturday March 01, 2014 @07:13PM (#46378329)

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)

I agree, bucket sort is the easiest for me to implement. Especially if there's a large amount of items. Once it gets down to a smaller collection I typically implement a variation on bubblesort on the vastly smaller piles. Unless I know it's already nearly sorted (as with stacked bills, oldest on the bottom), then I do an insertion sort to get the small handful of out of order items into the right places.
• Physically? (Score:4, Funny)

on Saturday March 01, 2014 @07:20PM (#46378355) Journal

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)

With the jazz band I play in, we have a book full of a few hundred charts. When resorting them after a gig, I typically grab a small stack, sort it insertion style, set it aside, then do the same to another pile. Once a few piles have been done, they get merge sorted into a big pile. Big piles themselves are merge sorted, until all of my music is in order.
• 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)

Strictly speaking, this is most-significant-digit-first radix sort. Alejo
• 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)

This is slashdot, ok, so I'm not surprised no one came up with sunsort
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)

You could use Paper Tiger [youtube.com]. It is an online indexing system. You would simply tag the paper's index with whatever projects or categories it belongs to, and then file the paper.
• 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)

How were you originally sorting? Were you partitioning the receipts into separate piles, based on some date? And then taking each pile and sorting them? How is this NOT one of those fancy sorting algorithms you learned in comp sci? And how was a radix search faster?
• 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)

...does sorting give any benefit in the long run?
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)

Perry Mason: "Someone rented a car, returned it and rented it again. We need to find that person."

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)

I sort things into what's known as a stack, or a pile, and then I put them in the freezer.
• 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)

I let the program import the sortable items in MS excel and sort them there.
• 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.

Related LinksTop of the: day, week, month.

Top Ten Things Overheard At The ANSI C Draft Committee Meetings: (5) All right, who's the wiseguy who stuck this trigraph stuff in here?

Working...