Efficient ways to sort a deck of actual cards

I often have to sort decks of cards. These are "collector" cards numbered from 1 to 216 and there are doubles and missing numbers.

I'm looking for sorting algorithms that work well with physical cards. Insertion sort seems fine because inserting a card does not require a shift of the subsequent cards like in开发者_Go百科 a computer memory. However, scanning through a large deck is time consuming. With a large deck, there are even chances that you might drop the deck and have to restart the sort.

I could draw the cards on a large table and directly place each card to its correct location but this takes quite a lot of space and is not very convenient.

My usual approach is to do a first scan through the deck and put them in stacks 1-49, 50-99, 100-149, 150-199, 200+. Then I scan each deck and put them in stacks 0, 1, 2, 3, 4. And finally, I apply an insertion sort on each 10-pack. This remains a tedious process though.

Another idea is to take the 50 stacks and sort them roughly. 25 would go around the middle, 40 somewhere near the end of the stack and so on. That quickly brings a roughly sorted 50-deck and I can easily scan through it and fix the sorting.

I was wondering whether a more sophisticated algorithm could be applied conveniently to a physical deck. I don't see how we could apply quick sort and thing like heap sort require to know the index of the card within the deck.

I think that a kind of quick sort is the easiest way for this. I think there were even some Youtube videos showing people doing this with a normal poker deck.

You go through the deck and put all cards smaller than 100 on a left pile, all bigger on a right pile. Then you recurse through the piles, depth first (so you do not have too many piles at once). At some threshold (perhaps about 5 cards), you simply sort "in hand" (similar to insertion sort, perhaps). Finally, you stack the piles together.

You could also do a merge sort: Divide the pile into two, recurse depth first, until you arrive at two piles of 5 cards each. Sort these two piles "in hand", then put them face up side by side. Merge them into a result pile by always putting the lower of the showing cards on the result pile. You can see which piles are already sorted by leaving those face up. Make sure to always merge piles of similar size, otherwise proceed to split up the next unsorted pile.

Edit: radix sort could be good, too: Put the cards into ten piles by their last digit, stack these piles together in order. Then, put the cards into ten piles by their second-to-last digit, stack them together in order again. Finally, put them into piles by their third-to-last digit (according to your discription, that is the first digit), and stack these together, done. This might be the easiest, after all, and it is O(n) (you need three passes through the deck).

I have taught university classes that are sometimes on the large side, and I have had practice with the similar task of sorting graded exams. I almost always use bucket sort, like you do. You also mention a merge sort approach, which I also sometimes do, but it only saves time when you start with sorted subpiles, not with a totally scrambled set of cards.

There are tricks to speed up the bucket sort. Much of the time in a human bucket sort is spent calculating the bucket for the next item. You can try two tricks. First, you can bucket sort by digit, which I guess is called radix sort, so that you never have to compare numbers. The first stage uses three buckets, which is not very many but could be okay. The second stage is the "main" work, with ten buckets. In the third stage, you are sorting ten numbered cards and common sense suggests insertion sort. But even for that stage, a radix sort could speed things up, even though each bucket only gets one card. Of course, you shouldn't use "buckets" with four sides, but just piles of cards on a table. You would only use the bucket method for the units digit if it is easy to sweep up the cards in order. Possibly for the middle stage, a slot with three sides would work better than an open pile of cards.

A second trick is to label the locations on the table 0 through 9 so that you can find the right pile more quickly. The labels can be taped onto the table so that you can reuse them.

I'm not sure if this particular bucket sort strategy is the best one. The point is that bucket sort is the most common method for sorting midterms, and probably best for large decks of cards too. There are several variations to try and you should experiment a little to see which one works best.

Eric,

Not sure if you still run into ordering physical decks of cards, but I was researching this (card sorts, needle sorts, sorting machiens etc.) and stumbled across your post. If you don't, then I hope someone else might find it useful/helpful.

If you have the ability to use a hole punch and modify an edge of the card deck - then a sorting technique can be used to order the entire pile in log2(#of cards) operations. So it would take 8 operatons for ~ 200 cards.

One way I found worked well is as follows:

1.) Order the deck the way you want and give each card a #.

2.) Convert this # to binary at a length of log2(# of cards). e.g. log2(216) ~ 8, then you would only need 8 places... so 0x0 would become 00000000

3.) Enode each card with it's binary representation like the picture below

4.) Trim the 1's out like on card 1 below (the right or LSB is trimmed off) the second to the last on card 2 is also trimmed out...

5.) Grab a nail, or knitting needle or straight coat hanger etc... pack the deck together (unordered) w/ the holes all aligned

6.) insert the needle through the right hand hole on the entire deck (or the lsb in binary). lift the needle and let the cards that have no ring on that tab (you cut it out) fall down into a box. Move the cards hooked on the needle to the front of the deck. **DO NOT CHANGE THE ORDERING OF THE UNSELECTED CARDS WHILE LIFTING THE SELECTED CARDS OUT.... e.g. keep the deck in a loose fitting card box or something similar

7.) Pack the deck together again, this time use the needle on the adjacent hole previously used (the second to the right). do the same thing, let the unattached/unselected cards fall into a box and repeat.

8.) w/ 8 operations the entire deck should be sorted... Hope this helps someone

here's how it works: first operation (step 6) moves all odd intgers to the front, e.g. puts 1 in front of 2, 3 in front of 4 etc.

second operation moves (1/2 in front of 3/4), and 5/6 in front of 7/8. third operation moves 1/2/3/4 in front of 5/6/7/8 and 9/10/11/12 in front of 13/14/15/16.. fourth operation moves 1/2/3/4/5/6/7/8 in front of 9/10/11/12/13/14/15/16/ etc... the last move takes ~ one half the deck in and places it in front of the other... and it results in a completely ordered deck in a minimal amount of moves

Cheers, Jeremy

The reason I ask about actual total numbers and sizes is that if the total area of all possible cards is sufficiently small, it may well be possible to just: go through the deck laying them all out into a grid, each card going in its correct spot, and then simply pick them up in order.

For example, were there a maximum of 100 cards, numbered 1-100, imagine that your working surface is divided into a 10 x 10 rectangular grid; then as each card is processed, put eg card 67 in the 7th column of the 6th row. Once all the cards are laid out, pick them up in order.

This only works if your working surface is large enough to contain all the cards, but if they are normal playing card size and you have a nice big table, it should be able to cope with the 200 you mention, especially as you can easily overlap the 'cells' and have the method still work.

For me this is the approach which makes most use of the fact that this is a problem in physical space, rather than in bits - each physical object is processed only twice (once to put it in place, once to pick it up), because for an algorithm involving physical objects, moving them around has much greater cost than thinking about what to do.

I think counting sort together with your insertion sort approach could work well: scan for the ones and put them first, then the twos and so on.

This might look like a lot of work since your cards are numbered from 1 to over 200, but I think in this case everything will be a lot of work. You can speed things up by doing multiple cards at once, which shouldn't be too hard: scan for the ones, twos and threes (and more if you're up for it) all at once, and put them in corresponding positions (combining with "insertion sort" so you don't have to leave an empty space between cards).

I came across this post because I wanted to quickly sort a regular deck of 52 playing cards. A little experimentation suggests that I can sort the whole deck in about 1:30 using the algorithm of dealing each card into a pile for each suit then doing insertion sort one suit at a time (with almost no practice, so I'm sure it can be done faster with practice).

I tried a few different approaches including doing a red-black split then further splitting the Reds and blacks into their own suits, then doing insertion sort by suit, but this was notably slower. I also tried splitting each suit into 2-7,8-A to see if the insertion sort performed on smaller groups of cards was any faster, but it was also notably slower. So my take away is don't waste your time with excessive recursion to do the bucketing.

Extrapolating this method to your cards, it seems like the best approach is to deal the cards into buckets of a size that is easy for you to sort all at once in hand (10 or 20 cards perhaps since it's easy to figure out which bucket they go in) then do insertion sort on the buckets. Presumably you should be able to sort your 216 card decks in about 6-7 minutes this way.

There is specific method for sorting a deck of playing cards: it's named patience sorting.

http://geeksforgeeks.org/patience-sorting/

Updated Text description: There are two stages to sort a deck of cards:

1. To form several piles
2. Collect cards from piles

• Cards with lower value can be placed over the card.
• If there is no possible position for a card, then a new pile can be created.
• Goal is to form as much as few piles possible.
• To collect cards back is quite easy because top cards of all piles became visible in needed order from lower value to higher value.