sorting algorithms for people
February 3, 2009 12:58 PM Subscribe
Given, for example, a table and a deck of cards or numbered sheets or whatever, what's a good way to put them in order? I feel like this is the sort of knowledge that would be passed around as tricks of the trade among secretaries, but, more generally, is there any field that makes systematic study of algorithms for humans instead of computers?
Or maybe you mean a device? You can buy cardboard or plastic sorter thingies to arrange papers alphabetically or numerically.
posted by fish tick at 1:18 PM on February 3, 2009
posted by fish tick at 1:18 PM on February 3, 2009
Response by poster: I'm looking more for answers like metastability's. Half of this is for curiosity's sake, and also I don't do this often enough to justify buying anything.
By the way, mergesort is basically what I do now, except bottom-up. So I insertion-sort out little sorted sheafs, stored compactly on a table by stacking them with every other one turned sideways, and then mergesort the sheafs.
I'm wondering, is there a better algorithm?
posted by d. z. wang at 1:32 PM on February 3, 2009
By the way, mergesort is basically what I do now, except bottom-up. So I insertion-sort out little sorted sheafs, stored compactly on a table by stacking them with every other one turned sideways, and then mergesort the sheafs.
I'm wondering, is there a better algorithm?
posted by d. z. wang at 1:32 PM on February 3, 2009
For cards I do a half-bucket-half-selection sort method. Separate into suits (bucket), and then sort by number (select).
posted by that girl at 1:32 PM on February 3, 2009
posted by that girl at 1:32 PM on February 3, 2009
Insertion Sorts work well for people, since there's little cost for the insertion part, and generally locating the point of insertion is aided by natural heuristics. ("The M's are about .. here.")
posted by cameradv at 1:35 PM on February 3, 2009
posted by cameradv at 1:35 PM on February 3, 2009
Best answer: A K Dewdney wrote a classic Scientific American column on "real-world" algorithms in the 80s. i seem to recall it was a recurring theme. He approached it from an analogue-algorithms angle, rather than a practical-for-humans angle. Try googling "spaghetti sort" - it's an O(1) sort algorithm. Not often you can say that.
As to the discipline... http://en.wikipedia.org/wiki/Scientific_management
I don't know about sorting, but a classic paper searching technique uses knitting needles... Cope-Chat cards.
posted by Leon at 1:50 PM on February 3, 2009
As to the discipline... http://en.wikipedia.org/wiki/Scientific_management
I don't know about sorting, but a classic paper searching technique uses knitting needles... Cope-Chat cards.
posted by Leon at 1:50 PM on February 3, 2009
fish tick and metastability have it. you toss into piles (optionally using a device) then sort the piles and then stack the piles. Plastic sorter thingies help a lot, but you can just sit on the floor and make piles of paper otherwise. Went through about 40,000 campus directory updates like this. It's sorta the fastest way.
posted by zengargoyle at 2:05 PM on February 3, 2009
posted by zengargoyle at 2:05 PM on February 3, 2009
And, you want to look at Process Management as your starting searches.
posted by zengargoyle at 2:07 PM on February 3, 2009
posted by zengargoyle at 2:07 PM on February 3, 2009
Best answer: doh Process Management Hand Sorting.
posted by zengargoyle at 2:09 PM on February 3, 2009
posted by zengargoyle at 2:09 PM on February 3, 2009
Radix sorting would be my first choice if the items are numbered in some sort of radix way (like numbers or cards with suit/value). Failing that, merge sort as already noted.
posted by chairface at 2:19 PM on February 3, 2009
posted by chairface at 2:19 PM on February 3, 2009
Least Significant Digit Radix Sort is clean and reasonably fast.
posted by Chocolate Pickle at 2:20 PM on February 3, 2009
posted by Chocolate Pickle at 2:20 PM on February 3, 2009
The problem with insertion sort for physical objects is that the insertion is slow and difficult.
The problem with merge sort for physical objects is that it isn't very intuitive.
But I've used a radix sort on sales receipts and it's really easy and fast.
posted by Chocolate Pickle at 3:15 PM on February 3, 2009
The problem with merge sort for physical objects is that it isn't very intuitive.
But I've used a radix sort on sales receipts and it's really easy and fast.
posted by Chocolate Pickle at 3:15 PM on February 3, 2009
Insertion sort and merge sort are the ones generally used by humans.
A K Dewdney wrote a classic Scientific American column on "real-world" algorithms in the 80s. i seem to recall it was a recurring theme. He approached it from an analogue-algorithms angle, rather than a practical-for-humans angle. Try googling "spaghetti sort" - it's an O(1) sort algorithm. Not often you can say that.
It's actually O(n).
posted by Netzapper at 3:25 PM on February 3, 2009
A K Dewdney wrote a classic Scientific American column on "real-world" algorithms in the 80s. i seem to recall it was a recurring theme. He approached it from an analogue-algorithms angle, rather than a practical-for-humans angle. Try googling "spaghetti sort" - it's an O(1) sort algorithm. Not often you can say that.
It's actually O(n).
posted by Netzapper at 3:25 PM on February 3, 2009
Best answer: I find that the easiest way to sort stuff is a sort of bucket or pigeon hole sort. I find that this scales fairly well for sorting things, if one chooses their "buckets" wisely. I base this on the fact that, at least for me, the fewer different decisions I have to choose from, the easier it is for me.
For a deck of cards, first run through them and split the deck into piles of the four suits, and then sort the suits individually.
For a pile of numerical or alphabetical papers, I like to choose my piles in a way that is relevant to the data at hand. If I have a pile of invoices and their most significant digit varies between 3 4 and 5, I'll first split them into those three groups. Then, keep splitting the groups until the smaller groups are of a size that "raw" (insertion) sorting is easy. It is tedious, but after some practice, you can get to know your own brain and balance the tedium with the difficulty of decision making so that it's the least tiring.
If you don't have too much room to be able to spread out all these different piles of things, I would do it like this. Say they are documents to be alphabetized. You set up three piles, your source, your intermediate and your final. Flip through the source, and pull out all the Zs. Put them in the intermediate pile. Then, sort that pile and put it in the final pile. Continue doing this all the way up the alphabet. Now your pile is sorted. Tedious, but space saving.
The key, for me, is not making it so complex that I get confused with what decision I'm supposed to be making for each thing.
posted by gjc at 5:19 PM on February 3, 2009
For a deck of cards, first run through them and split the deck into piles of the four suits, and then sort the suits individually.
For a pile of numerical or alphabetical papers, I like to choose my piles in a way that is relevant to the data at hand. If I have a pile of invoices and their most significant digit varies between 3 4 and 5, I'll first split them into those three groups. Then, keep splitting the groups until the smaller groups are of a size that "raw" (insertion) sorting is easy. It is tedious, but after some practice, you can get to know your own brain and balance the tedium with the difficulty of decision making so that it's the least tiring.
If you don't have too much room to be able to spread out all these different piles of things, I would do it like this. Say they are documents to be alphabetized. You set up three piles, your source, your intermediate and your final. Flip through the source, and pull out all the Zs. Put them in the intermediate pile. Then, sort that pile and put it in the final pile. Continue doing this all the way up the alphabet. Now your pile is sorted. Tedious, but space saving.
The key, for me, is not making it so complex that I get confused with what decision I'm supposed to be making for each thing.
posted by gjc at 5:19 PM on February 3, 2009
I did a lot of sorting as an ESL teacher: Assignment books and the like. I never did find a better method than the bottom-up merge sort. Source stack in nondominant hand, insertion sort into a stack in the other hand until it becomes unwieldy, set it down and start another, merge later. Small merges are easier for me: If I have six stacklets, I'll merge three and three, then merge the two bigger stacks, rather than scan six items every time.
posted by eritain at 6:54 PM on February 3, 2009
posted by eritain at 6:54 PM on February 3, 2009
[Spaghetti sort]
It's actually O(n).
Only if you include the I/O stages. The sort itself is O(1).
posted by Leon at 7:44 PM on February 3, 2009
It's actually O(n).
Only if you include the I/O stages. The sort itself is O(1).
posted by Leon at 7:44 PM on February 3, 2009
Best answer: Experienced librarian staff sort a pile of books using a simple insertion sort, with a shelf to place the books on. Pick up a book, scan the shelf, insert the book where it belongs. Simple, human-compatible, you handle each book only once. However, it does require the sorting information to be visible on the book's spine.
For a stack of papers, I use a most-significant-digit radix sort with a large surface (table, floor) to place the piles on. Go through the stack, placing each item in the pile corresponding to its first (leftmost) character or numeral. (For numerals, ten stacks or fewer.) Then pick up the first pile and sort by the second character or numeral. For many actual situations, the second pass is the final one, and the sorted pile can be placed face-down in the output stack. Then proceed to the second pile, and so on.
Most-significant-digit radix sort is just a fancy name for many of the sorts described above. I find it more human-compatible than Chocolate Pickle's least-significant-digit radix sort.
posted by exphysicist345 at 10:14 PM on February 3, 2009
For a stack of papers, I use a most-significant-digit radix sort with a large surface (table, floor) to place the piles on. Go through the stack, placing each item in the pile corresponding to its first (leftmost) character or numeral. (For numerals, ten stacks or fewer.) Then pick up the first pile and sort by the second character or numeral. For many actual situations, the second pass is the final one, and the sorted pile can be placed face-down in the output stack. Then proceed to the second pile, and so on.
Most-significant-digit radix sort is just a fancy name for many of the sorts described above. I find it more human-compatible than Chocolate Pickle's least-significant-digit radix sort.
posted by exphysicist345 at 10:14 PM on February 3, 2009
I've always used the MSD radix sort as described above. Nice to know it has a name!
posted by neckro23 at 11:25 PM on February 3, 2009
posted by neckro23 at 11:25 PM on February 3, 2009
I'm in the bucket & selection/bubble sort camp, only my bucketing is aided by human "hardware optimization". When I'm sorting a deck of cards, I ribbon-spread them out on the table and then slide cards towards me into the four suit buckets (which are later sorted using a combination of selection & bubble sort depending on the initial conditions). I pull out the buckets one at a time in red-black-red-black order so that after I've done two buckets, the remaining unbucketed cards consist of reds and blacks (instead of two red suits or two black suits). Humans are really good at quickly searching these to pull out just the reds or just the blacks. We are also pretty good at spotting each suit in a big pile. Clubs are easiest for me to start with since they seem to stand out the most (the pointy end of the red hearts can look like a diamond when you are trying to search quickly).
posted by RobotNinja at 10:26 AM on February 4, 2009
posted by RobotNinja at 10:26 AM on February 4, 2009
This thread is closed to new comments.
posted by metastability at 1:11 PM on February 3, 2009