All Sorts of Sorters
A packet of playing cards is a wonderful invention. It’s the major ingredient to countless possible nights of fun. There’s nothing like gathering around a table to test bonds of friendship and familial tolerance as you let your competitive nature overcome you, body and soul.
Whether you’re sitting down to play a game of Bridge, Big 2, or Bullsh*t, your first priority is always the same: get your cards into order! Even though sorting your hand is almost a universal first step to any card game, everyone has their own way of approaching this task each round.
The dealer deals you in, and you pick up your cards off the table … what do you do next?
Image by TerriersFan via Wikimedia Commons (public domain)
What sort of sorter are you?
Maybe you’re the type of person who sorts by selection: you select the highest-value card in your hand, and move that to one side. Then, you select the next highest card, and move that to the end, next to the first card. You keep going, until your hand is all sorted.
In Computer Science, we call this method selection sort. It’s a pretty common strategy for ordering a hand of playing cards, because it’s really easy to pick out the highest card in your hand, and it’s not too awkward to pick that card up and shift it to one end.
But selection isn’t the only hand-sorting strategy!
Maybe you sort by insertion, instead. Inserters start at one end of their hand. They progress through their cards from one side to the other. They take each card in turn, and insert it in its rightful place on the already-sorted side: in between a card that’s higher and a card that’s lower in value. When they reach the last card and put it into place, they have sorted their hand!
This method’s Computer Science name is insertion sort. It also seems to be a pretty common strategy. Although, in my experience, it can be a little awkward to repeatedly make space for a card in a specific place while you’re holding them all in one hand.
What sort of sorter are you? I think I fall somewhere short of both a selector and an inserter: I gracelessly push the cards around with my left thumb as I pick out random cards and try to put them in some semi-sensible place. There’s no technical name for this kind of sorting strategy, because no Computer Scientist (except me) has ever used it to sort anything!
Why can’t I hold all these cards?
Image by Nayuki via Flickr (CC BY 2.0)
Don’t look now, but you just learned some Computer Science!
These sorting strategies are examples of algorithms: a foundational Computer Science concept. Simply put, algorithms are step-by-step procedures for solving some problem. In this case, we’re talking about the problem of sorting: taking a randomly-ordered bunch of things (like cards) and changing their order to arrange them by some kind of value (like the numbers on the cards).
Insertion sort and selection sort are two of the first algorithms a Computer Science student will ever learn. They’re elegant, they’re simple to understand, and they perform fine on a hand of 10 or so cards.
But, what if I asked you to sort a hand of … more like 1000 cards!? When you have 1000 cards to sort, what was quick for 10 cards becomes slow, instead:
- Selecting the card with the highest value means you have to look through all 1000 cards. That might take you a while!
- Likewise, imagine inserting the final card into a list of the other 999 cards. You have to find the right place, and then you have to move all the cards over to make room!
It turns out, using one of these algorithms could take you about 100 times longer than using a more advanced and clever strategy like quicksort or merge sort. If you were really keen, you could use the special-purpose bucket sort, finishing around 1000 times faster than insertion sort or selection sort.
Sorting algorithms are staples of a Computer Scientist’s problem-solving arsenal. There are almost as many of them as cards in a standard deck. While sorting a big list of things isn’t exactly a common real-world problem, it turns out to be a powerful trick that can form one small step in a larger strategy in a surprising number of situations.
Unfortunately, understanding advanced sorting algorithms won’t help me handle the 10 random cards I pick at the start of a game. These strategies all require a lot more card-coordination than I can manage with one hand, without spilling my aces all over the table.