Sorting cards

[Gregory Woodhouse]

If you are handed 5 cards and asked to arrange them in ascending order, my guess is that you would follow a procedure something like this:

1. Spread the cards in a fan, face up.

2. Scan through the cards, find the smallest one, and move it to the leftmost position.

3. Repeat this process with the four remaining cards, placing that card in the second position.

4. Continue until all 5 cards are placed in ascending order.

Now, imagine that you are given a deck of 52 cards and place them in ascending order. Don't think too hard about what you "should" do, just try to picture yourself going through this process. If you really aren't sure, and if you have a deck of cards handy, actually go through this process. Again, don't think too hard, just do it.

Now, how did you sort the cards? Did you follow the same procedure as with the 5 cards?

Gregory Woodhouse

gregory....@sbcglobal.net

"Mathematics is the science of patterns."

--Lynn Arthur Steen, 1988

[Jim Self]

Gregory Woodhouse wrote:
> If you are handed 5 cards and asked to arrange them in ascending
> order, my guess is that you would follow a procedure something like this:
>
> 1. Spread the cards in a fan, face up.
> 2. Scan through the cards, find the smallest one, and move it to the
> leftmost position.

> 3. Repeat this process with the four remaining cards, placing /that/

> card in the second position.
> 4. Continue until all 5 cards are placed in ascending order.
>
> Now, imagine that you are given a deck of 52 cards and place them in
> ascending order. Don't think too hard about what you "should" do, just
> try to picture yourself going through this process. If you really
> aren't sure, and if you have a deck of cards handy, actually go
> through this process. Again, don't think too hard, just do it.
>
> Now, how did you sort the cards? Did you follow the same procedure as
> with the 5 cards?

I would just reserve 13 places for cards on a table and drop each card
in its place by face value - done.

[Chris Richardson]

Is there an explicite order of suits? Are all Clubs bigger than Spades,
which are smaller than Diamonds, and Diamonds are smaller than Hearts? Are
Aces high or low? Then 13 slots won't do.

Now, what about shuffling a deck of cards. How about a means of randomizing
52 cards quickly?

The shuffled deck is in DECK, SHUFFLE is a string with the shuffle
Spades = 1:13
Clubs = 14:26
Diamonds=27:39
Hearts = 40:52

K DECK
F I=1:1:52 F S V=$R(1000000) I '$D(DECK(V)) S DECK(V)=I Q
S SHUFFLE="",I=""
F S I=$O(DECK(I)) Q:I="" S SHUFFLE=SHUFFLE_DECK(I)_":"
; Now to sort the shuffle
S (SORT,I)=""
F I=1:1:$L(SHUFFLE,":") S V=$P(SHUFFLE,":",I),$P(SORT,":",V)=V
; Big deal, SORT="1:2:3:4:5:6:7:8...51:52", but look at SHUFFLE
; Your actual values will vary widely for SHUFFLE
QUIT
; ===============

[kdt...@gmail.com]

Gregory Woodhouse wrote:
> If you are handed 5 cards and asked to arrange them in ascending
> order, my guess is that you would follow a procedure something like
> this:
>

Do you have to hold them in your hand? If we are using a computer
analagy, then I think we should have to. I know that sorting is a fine
art among Mumps programmers ;-)

Actually, the only sort I can remember is the bubble-sort method (slow
and ineffecient)

Kevin

[Gregory Woodhouse]

On Oct 19, 2006, at 9:59 PM, Jim Self wrote:

I would just reserve 13 places for cards on a table and drop each card 

in its place by face value - done.

Interesting. That's not quite the answer I had expected. Anyone else?

[Gregory Woodhouse]

On Oct 19, 2006, at 10:32 PM, Chris Richardson wrote:

Is there an explicite order of suits?  Are all Clubs bigger than Spades,

which are smaller than Diamonds, and Diamonds are smaller than Hearts?  Are

Aces high or low?  Then 13 slots won't do.

For the sake of definiteness, take

Club < Diamond < Heart < Spade

2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 1o < J < Q < K < A

Now, what about shuffling a deck of cards.  How about a means of randomizing

52 cards quickly?

Yes, I did sort of skip over that step!

  The shuffled deck is in DECK, SHUFFLE is a string with the shuffle

  Spades = 1:13

  Clubs    = 14:26

  Diamonds=27:39

  Hearts   = 40:52

 K DECK

 F I=1:1:52   F     S V=$R(1000000)    I '$D(DECK(V))    S DECK(V)=I    Q

 S SHUFFLE="",I=""

 F     S I=$O(DECK(I))   Q:I=""   S SHUFFLE=SHUFFLE_DECK(I)_":"

 ;  Now to sort the shuffle

 S (SORT,I)=""

 F I=1:1:$L(SHUFFLE,":")  S V=$P(SHUFFLE,":",I),$P(SORT,":",V)=V

 ;  Big deal, SORT="1:2:3:4:5:6:7:8...51:52", but look at SHUFFLE

 ;    Your actual values will vary widely for SHUFFLE

 QUIT

 ;   ===============

Gregory Woodhouse

gregory....@sbcglobal.net

"You can't win if you don't finish the race."

--Richard Petty

[Gregory Woodhouse]

On Oct 20, 2006, at 4:56 AM, kdt...@gmail.com wrote:

Do you have to hold them in your hand?  If we are using a computer

analagy, then I think we should have to. 

I didn't say, but how does it change your answer if you do? Or does it?

I know that sorting is a fine

art among Mumps programmers ;-)

Do you mean fine as in "refined" or fine as in "small"? :-)

Actually, the only sort I can remember is the bubble-sort method (slow

and ineffecient)

Now you're thinking! Remember, the point is not to think about how you might do it. Just describe how you would intuitively perform the task.

Kevin

Gregory Woodhouse

gregory....@sbcglobal.net

I hear and I forget.

I see and I remember.

I do and I understand.

--Attributed to Confucius, 500 BCE

[K.S. Bhaskar]

kdt...@gmail.com wrote, on 10/20/2006 07:56 AM:

[KSB] <...snip...>

> Do you have to hold them in your hand? If we are using a computer
> analagy, then I think we should have to. I know that sorting is a fine
> art among Mumps programmers ;-)

[KSB] Sorting should not be an art among MUMPS programmers because the
MUMPS implementation keeps variables sorted at all times.

Regards
-- Bhaskar

[Gregory Woodhouse]

On Oct 20, 2006, at 4:56 AM, kdt...@gmail.com wrote:

Actually, the only sort I can remember is the bubble-sort method (slow

and ineffecient)

By the way, bubble sort is easy enough to understand, but I've never found it particularly intuitive. Does that sound like I just contradicted myself? Maybe so.

At any rate, the idea is to proceed in a series of "rounds", interchanging elements that are out of order. After each round, the unsorted sublist will be 1 smaller. It's best understood with an example,

Start with 7 2 8 1 12

Round 1:

interchange 7 and 2  => 2 7 8 1 12

7 and 8 are in order => 2 7 8 1 12

interchange 8 and 1 => 2 7 1 8 12

8 and 12 are in order => 2 7 1 8 12

Now, 12 is at the end

Round 2:

2 and 7 are in order => 2 7 1 8 12

interchange 7 and 1 => 2 1 7 8 12

7 and 8 are in order => 2 1 7 8 12

Now, 8 12 is at the end. (That 7 is in it's right place is "coincidental".)

Round 3:

interchange 1 and 2 => 1 2 7 8 12

2 and 7 are in order => 1 2 7 8 12

Now, 7 8 12 is at the end.

Round 4:

1 and 2 are in order => 1 2 7 8 12

Round 5:

There is no round 5. You're done.

Gregory Woodhouse

gregory....@sbcglobal.net

"If everything seems under control,

you're just not going fast enough."

-- Mario Andretti

[Gregory Woodhouse]

On Oct 20, 2006, at 5:18 AM, K.S. Bhaskar wrote:

[KSB] Sorting should not be an art among MUMPS programmers because the 

MUMPS implementation keeps variables sorted at all times.

Remember: The question is not one about programming, but arranging cards (actual, physical cards).

Gregory Woodhouse

gregory....@sbcglobal.net

"In the human mind, one-sidedness has 

always been the rule and many-sidedness the

 exception. Hence, even in revolutions of 

thought, one part of the truth usually sets while

 another rises."

--John Stuart Mill

[Gaber, Roy G.]

If this is a trick question then I have an answer, simply purchase a deck of cards, pull them out of their container and presto, a completely sorted deck.

 

On the other hand, if this is not a trick question, I would have to say that patience sorting would be the key here.

 

---

From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On Behalf Of Gregory Woodhouse
Sent: Friday, October 20, 2006 8:42 AM
To: Hard...@googlegroups.com
Subject: [Hardhats] Re: Sorting cards

 

 

On Oct 20, 2006, at 5:18 AM, K.S. Bhaskar wrote:

[Gregory Woodhouse]

On Oct 20, 2006, at 6:04 AM, Gaber, Roy G. wrote:

On the other hand, if this is not a trick question, I would have to say that patience sorting would be the key here.

What is "patience sorting"?

[Gaber, Roy G.]

Suffice it to say that by playing a game of solitaire you are effectively employing patience sorting.

 

Technically it is a non-recursive analog of the Robinson-Schensted-Knuth algorithm.

 

---

From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On Behalf Of Gregory Woodhouse
Sent: Friday, October 20, 2006 9:09 AM
To: Hard...@googlegroups.com
Subject: [Hardhats] Re: Sorting cards

 

 

On Oct 20, 2006, at 6:04 AM, Gaber, Roy G. wrote:

[Holloway, Thomas (EDS)]

I would not use the bubble sort (as you described on a separate reply in this thread) and the method for 52 cards would not match your description for sorting 5 cards.  Primarily, step 2 - scanning all of the cards and selecting the lowest value to be moved, is inefficient at the level of a full deck of cards.  Because you said a human was doing this, there are a couple of considerations.  One is the limitation of the human hand.  We cannot easily manipulate a fan of 52 cards so the problem needs to be broken down to something we can handle.  Second is the limitation of the human mind.  We can work with 5 to 7 objects fairly easily but begin to break down above that.   Keeping that in mind, I see two possibilities that I might choose for doing the sorting, one of which conflicts a bit with the restrictions I mentioned and might turn out to be slower. 

Method 1:  Follow Jim's idea... allocate 13 spots on the table, pull up a card and drop it on its appropriate stack (1 - 13).  When all cards are in stacks of four, pick up the first stack and sort it in suit order using the method described in the original 5-card example.  Since it is only 4 cards we can do this easily.  Place those cards face down (lowest value to the table, highest value on top) and move to the second stack placing it face down on the pile.  Repeat.  In this method we are manipulating cards in groups that are both physically and mentally easy to handle but each card is handled at least twice. 

 

Method 2:  Sort as you go.  Pull up a card.  Place it in your other hand.  Pull up the next card.  Place it either before or after the first card based on its appropriate order.  Pull up the next card.  Place it in its appropriate spot in the growing fan of cards.  Repeat for all cards.  In this method, each card is only handled once but the full fan is hard to hold and scanning for the appropriate spot becomes time consuming as the fan grows.

 

I think method 1 is more appropriate for humans whereas method 2 might be more appropriate for computers.

 

   tjh

---

From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On Behalf Of Gregory Woodhouse

Sent: Friday, October 20, 2006 8:01 AM

To: Hard...@googlegroups.com
Subject: [Hardhats] Re: Sorting cards

[Nancy Anthracite]

What is the native MUMPS sort - or did you already tell us that?

tjh

_____

From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On

Behalf Of Gregory Woodhouse
Sent: Friday, October 20, 2006 8:01 AM
To: Hard...@googlegroups.com
Subject: [Hardhats] Re: Sorting cards

On Oct 19, 2006, at 9:59 PM, Jim Self wrote:

I would just reserve 13 places for cards on a table and drop
each card

in its place by face value - done.

Interesting. That's not quite the answer I had expected. Anyone else?

Gregory Woodhouse
gregory....@sbcglobal.net

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

--
Nancy Anthracite

[Chris Richardson]

Well, that's Knuth to me.

[gregory....@sbcglobal.net]

Are you sure? Never having heard of this algorithm (sorry), I did a quick google search and found a number of interewsting references to the literature. Obviously, they are very relevant to sorting, as the distribution of non-decreasing runs (cards already in order) has a lot to do with how long it takes to sort. But I didn't find the actual algorithm.

 

For the curious, here's a sample abstract

 

Permutations without long decreasing subsequences and random matrices
Authors: Piotr Sniady
Comments: 7 pages
Subj-class: Combinatorics; Probability
MSC-class: 05E10, 15A52, 60J65

We study the shape of the Young diagram \lambda associated via the Robinson-Schensted-Knuth algorithm to a random permutation in S_n such that the length of the longest decreasing subsequence is not bigger than a fixed number d; in other words we study the restriction of the Plancherel measure to Young diagrams with at most d rows. We prove that in the limit n\to\infty the rows of \lambda behave like the eigenvalues of a certain random matrix (traceless Gaussian Unitary Ensemble) with d rows and columns. In particular, the length of the longest increasing subsequence of such a random permutation behaves asymptotically like the largest eigenvalue of the corresponding random matrix.

 

===
Gregory Woodhouse

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

[Chris Richardson]

MUMPS is intuitively sorting. By virtue of creating a data structure with
the sorted items in the subscripts, you are sorting. The results are
immediately available because the data in the subscripts is collated as it
is created. Basically, between any two nodes, there is an infinity of
additional nodes that can be created.

What Jim was describing with his 13 piles was a prescribed bucket sort. He
know the kinds of cards he was going to come in contact with and have
predefined the domain that he was going to project the "population to be
sorted" into. Fine. But what would happen if he got a hold of a tarot deck
instead of a standard deck of Bicycle Cards (or whatever). Ok, the 15 of
swords, now where would that go?, the 17 of Goblets, the Joker, you get the
idea.

Now suppose there was a bucket sort that you did not have to pre-allocate.
We start with no buckets. We sample the population we wish to sort and get
a 20 of castles. OK, now we have a challenge, we can sort the cards on
their value or their suit, or both (but which one is primary) (this is why
we will still need people to make these decisions as to what is more useful
to our purpose). For this purpose, we will sort these on the value/suite
combination. So we pull out a nice new bucket and slap a label on it that
says 20 of Castles. This might be a Tarot Pinocle deck so we may find more
of these as time goes on. In that this is the first bucket, we can pretty
much put it anywhere. All subsequent additions will be either before or
after this bucket. We then get a 2 of wands and create another bucket and
put this one in front of the first bucket. Now we get the 5 of swords. Where
do we put this? Are we sorting them by the value of the card
[(2,"Wands"),(5,"Swords"), (20,"Castles")] or the character order, ("2 of
Wands", "20 of Castles", "5 of swords", judging from the first character to
the second character, and so on). Once we have made this decision, it gets
pretty simple to continue the sorting process, adding new buckets into their
proper slot and then putting duplicates into their already assigned buckets.

When the population of cards has been exhausted, and all members are
consigned to their buckets, the sort is over. One need only to walk down
this long line of buckets and tally up the members found in each bucket
however that population is to be reported. MUMPS works much this same way.
Once the population has been sampled, sorting is complete. MUMPS means that
you never have to say you are sorting.

[gregory....@sbcglobal.net]

I find the variety of solutions being proposed here quite fasinating. It would be a real surprise to me if anyone used bubble sort. It is the slowest of the quadratic sorts, and not especially intuitive (to me, at any rate). It's probably introduced early on in programming classes because it's easy to analyze. But to me, insertion sort (sort as you go), seemed so "obvious". I read about it once and it was firmly ingrained in memory. Not so with bubble sort. It wasn't particularly natural, and ended up being something I needed to memorize. In a sense, that's part of the point of this exercise, too. Thinking about playing cards makes it easier to stop overanalyzing and listen to your intuition.

 

Interestingly, no one has mentioned what I think I'd do. I don't have any cards handy, so I can't really test myself, but here goes:

 

1. Divide the deck into two piles of approximately the same size, then repeat so there are actually four.

2. Turn over the first one and sort it using "sort as you go" (i.e., just put the cards in their proper position, one at a time). Repeat for each of the other three.

3. Now take two of the sorted piles and combine them into one, by turning them both face up, repeatedly selecting the smaller of the two cards, and placing it (face down) in a third pile. Repeat the process with the other two.

4. Finally, combine the two sorted piles to form one sorted pile using the same technique.

 

In practice, I think I'd "cheat" a bit, by picking up as many cards as were actually consecutive, treating them almost as if they were one card.
 

===
Gregory Woodhouse

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

[Nancy Anthracite]

Was that English?

===
Gregory Woodhouse

--
Nancy Anthracite

[Mike Schrom]

You're obviously not a bridge player! Ascending: clubs, diamonds,
hearts, spades (no trump)!

[gregory....@sbcglobal.net]

Yes Chris, I know MUMPS does that work for you. But to say that MUMPS makes sorting intuitive is like saying light switches make electricity intuitive. They're tremendously useful things, and you shouldn't have to know about Kirchoff's law(s), or the difference between a watt and an ampere to have a light to read by in the evening. But, then again, there are times when maybe you do want to know a bit about electricity.

===
Gregory Woodhouse

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

----- Original Message ----
From: Chris Richardson <r...@rcresearch.us>
To: Hard...@googlegroups.com
Sent: Friday, October 20, 2006 8:31:54 AM
Subject: [Hardhats] Re: Sorting cards

[Gaber, Roy G.]

Yes, patience sorting is real and is probably, in my opinion, the easiest way of sorting the cards given a human is doing the sorting. 

 

 

 

---

From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On Behalf Of gregory....@sbcglobal.net
Sent: Friday, October 20, 2006 11:19 AM
To: Hard...@googlegroups.com
Subject: [Hardhats] Re: Sorting cards

[gregory....@sbcglobal.net]

Probably not!

===
Gregory Woodhouse

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

----- Original Message ----
From: Nancy Anthracite <nanth...@verizon.net>
To: Hard...@googlegroups.com
Sent: Friday, October 20, 2006 8:38:14 AM
Subject: [Hardhats] Re: Sorting cards

Was that English?

[Darren Coolidge]

I like the solitare approach.  Make it fun.  Make sorting a game. But if I were to write a program i would probably use a binary sort.  Or as someone else put it a quad-sort with the different icons.  Just my 0.02

[Chris Richardson]

Shocking, Greg, just shocking. Greg, you know I am just trying to stay
current.

The bucket sort is a real tool which is very driven by the data that it
encounters. When implemented in other computer languages, it is sensitive
to granularity and range and requires some absolute knowledge about the
environment that the model will run in. The way MUMPS applies this model is
much more human intuitive than the mechanistic method that most languages
use to handle the problem.

When you get done with MUMPS, you only have as many buckets as you have
species from the population to fill them. Suppose you have a smaller deck
of cards. Not all suits and not all numbers are represented in the
population you are dealing with. In another language, you would have to
still prepare for all possible species of card that you are likely to
encounter. In MUMPS, you would only have as many buckets as the number of
species that you encountered and no more. That in itself is valuable and
tells you a lot more about the population by just listing the buckets that
were created. A search for empty buckets needs to be done in other
languages. Ain't sparse matricies fun?

[Chris Richardson]

Data out of context is noise.

What are you two talking about?

----- Original Message -----
From: <gregory....@sbcglobal.net>

[Nancy Anthracite]

Whether this was written in English, or not!

Permutations without long decreasing subsequences and random matrices
Authors: Piotr Sniady
Comments: 7 pages
Subj-class: Combinatorics; Probability
MSC-class: 05E10, 15A52, 60J65
We study the shape of the Young diagram \lambda associated via the
Robinson-Schensted-Knuth algorithm to a random permutation in S_n such that
the length of the longest decreasing subsequence is not bigger than a fixed
number d; in other words we study the restriction of the Plancherel measure
to Young diagrams with at most d rows. We prove that in the limit n\to\infty
the rows of \lambda behave like the eigenvalues of a certain random matrix
(traceless Gaussian Unitary Ensemble) with d rows and columns. In
particular, the length of the longest increasing subsequence of such a
random permutation behaves asymptotically like the largest eigenvalue of the
corresponding random matrix.

===
Gregory Woodhouse

--
Nancy Anthracite

[Chris Richardson]

That's right, Pilgraham. In Texas I hear that they play bridge with real
bridges. Who needs suits.

Is there a different implied order in some other game? Hearts and Spades??
It has been a long time.

The last card game I learned was "Hands and Feet" or was it "Hand and Foot".
That was fun, but it takes a lot of decks of cards.

----- Original Message -----
From: "Mike Schrom" <mikes...@nycap.rr.com>
To: <Hard...@googlegroups.com>

[kdt...@gmail.com]

Gregory Woodhouse wrote:
...

>
> Now, imagine that you are given a deck of 52 cards and place them in
> ascending order. Don't think too hard about what you "should" do,
> just try to picture yourself going through this process. If you
> really aren't sure, and if you have a deck of cards handy, actually
> go through this process. Again, don't think too hard, just do it.

OK, I guess you really want to know how I would do it as a human, with
not tricks.

I would fan out the cards as best I could, then start putting the low
numbers towards the start of the deck and the high numbers at the end
of the deck, trying to put them into rough numerical order. Then, as I
got the deck closer to being in order, I would fine tune the sort.

Kevin

[Nancy Anthracite]

Human sorting:

I just alphabetized the consent forms on the 40 flu shots I gave this
afternoon. I made sorted groups of 10 because they were easy to hold, then I
picked them up in the correct order from the tops of the piles I made.

Cards I might separate the suits into 4 piles, then sort the 4 suits
individually while holding them fanned in my hand, then stack the piles.

Kevin

--
Nancy Anthracite

[Maury Pepper]

----- Original Message -----
From: "Nancy Anthracite"
Sent: Friday, October 20, 2006 4:09 PM
>
> Cards I might separate the suits into 4 piles, then sort the 4 suits
> individually while holding them fanned in my hand, then stack the piles.
>

BINGO !!! I've been wondering if anyone would hit (what to me is) the
obvious. As a compulsive kid, I often did sort an entire deck, and that was
my method -- exactly.

[gregory....@sbcglobal.net]

Now that you mention it...That probably IS what I'd end up doing. Interesting.

This discussion reminds of a joke about mathematics (or perhaps university professors) that is only funny because it is so, well, true. The story goes that a mathematicis professor is giving a lecture and utters the words "Now, it is obvious that..." and suddenly begins to look very agitated. He (or she, of course) begins pacing, growing very quiet, with an increasing distraught look. Eventually, he (or she) announces a 20 minute break. Then, after he class reassembles, comes out and exclaims "Yes! It is obvious!"

===
Gregory Woodhouse

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

----- Original Message ----
From: Maury Pepper <mpe...@ieee.org>
To: Hard...@googlegroups.com
Sent: Friday, October 20, 2006 2:15:33 PM
Subject: [Hardhats] Re: Sorting cards

[gregory....@sbcglobal.net]

An interesting aspect of the techniques (or algorithms) that have been proposed, is that they can almost all easily be implemented as computer programs. They all have their stong and weak points. And, in many cases, they are things that we might not of thought of if asked to write a program to sort a sequence of numbers (or number/letter pairs).

[Jim Self]

Holloway, Thomas (EDS) wrote:
> Method 1: Follow Jim's idea... allocate 13 spots on the table, pull
> up a card and drop it on its appropriate stack (1 - 13). When all
> cards are in stacks of four, pick up the first stack and sort it in
> suit order

The original problem did not mention suit order. If it did, I would have
put the cards on the table in 4 rows by suit.

When I did have occasion to sort cards as a child many years ago, it was
generally to prove that we had a full deck or to separate a stack of 4
or more (possibly incomplete) decks into as many complete and undamaged
decks as possible as quickly as possible so that a dozen or more people
of various levels of maturity could play card games at the same time.

The solution was generally highly parallel with 3 or more people
grabbing a manageable handful of cards to toss into 13 or more stacks
by face value. Others would watch over the stacks to make sure that
cards landed in the right pile and they would start the process of
breaking them down into complete sets of 4 by card back and size.

Odd cards like the 15 of blueberries or the 20 of castles or the Jeckyl
of Hydes might be tossed in the first pass into one or more special
stacks and not sorted further.

Depending on the numbers and capabilities and interests of the card
players and the condition and prior groupings of the cards, we might
start by separating the cards into stacks by card back or size. Some
stacks, like the tarot cards that Chris mentioned, might be put aside at
that point.

[Gregory Woodhouse]

On Oct 20, 2006, at 6:10 PM, Jim Self wrote:

The original problem did not mention suit order. If it did, I would have 

put the cards on the table in 4 rows by suit.

That's right, it didn't. But it wasn't by design, it just wasn't something I thought of when posing the original question. Yesterday, when I read your response, my immediate reaction was: "Of course! What could be more obvious?" Certainly, it is intuitively natural to think that sorting the cards by suit would be an advantage. After all, if the cards come with extra structure (a suit and a value), shouldn't you be able to take advantage of this structure to make sorting the cards easier? One would think so.

But then I started to think about it. Do we actually save any time by first sorting the cards into suits? How would you know? Does it make any difference whether a human being or a computer is doing the sorting? To my knowledge, Quicksort (an algorithm no one ever mentioned) is the fastest known in-memory general purpose sort. It works something like this:

1. Select the top card of the deck (call it the pivot), and place it face up in front of you.

2. Now, go through all the cards, one by one, placing them (face down) to the left of the pivot if they are smaller, or to the right if they are larger than the pivot.

3. Now, you have two piles of cards (one of which may be empty), to the right and the left of the pivot card (which is face up).

4. If either of those piles of cards contains only a single card, just turn it face up leaving it in the same place, and do not consider it further.

5. Now, starting with the leftmost face down pile of cards, turn the top card face up, and divide the remaining cards in that pile into two smaller piles, just as you did in step 2. 

6. Continue with this process, moving from left to right, until all 52 cards are face up (and in order) in front of you.

It's not hard to go through this process, but it will take a fair amount of space on your table or floor. It may also not feel like the most natural or obvious way to sort cards. (Why?)

You may recall that I proposed another method (technically known as merge sort) that uses much less space on the table (or floor), but takes no advantage of the fact that the cards come with suits. You may as well assume they are labeled 1 to 52. The basic procedure is:

1. Separate the deck into two piles, setting one aside.

2. Take the the other one, and divide it in two, setting the other aside (placing these side-by side, going right to left).

3. Keep going until you only have on card.

4. Now, combine it with the right-most pile (1 or 2 cards) to form a sorted pile of cards.

5. At each stage, "merge" the cards in hand with the rightmost pile, by setting them face up and side-by side, repeatedly selecting the smallest of the two, adding them to a new pile.

6. Eventually, you will have two piles of cards, one sorted and one not sorted. Repeat steps 1-6 to sort the pile of cards you initially set aside.

7. Finally, merge the two remaining (sorted) piles of cards as in step 5 to obtain a sorted deck.

Of course, i suggested an optimization (or maybe just a simplification?) where after two splits, you fan the remaining cards and resort to "sort as you go" (selection sort). This technique of switching algorithms as you get closer the end of an execution path (branch) is called "pruning" and can be quite useful.

When I did have occasion to sort cards as a child many years ago, it was 

generally to prove that we had a full deck or to separate a stack of 4 

or more (possibly incomplete) decks into as many complete and undamaged 

decks as possible as quickly as possible so that a dozen or more people 

of various levels of maturity could play card games at the same time.

The solution was generally highly parallel with 3 or more people 

grabbing a manageable handful of cards to toss into 13  or more stacks 

by face value. Others would watch over the stacks to make sure that 

cards landed in the right pile and they would start the process of 

breaking them down into complete sets of 4 by card back and size.

This is interesting because it shows how the task of sorting can be profitably split up across processes. It's an example of what's called a distributed algorithm.

Odd cards like the 15 of blueberries or the 20 of castles or the Jeckyl 

of Hydes might be tossed in the first pass into one or more special 

stacks and not sorted further.

That's great! I guess I'd better check to see if Robert Louis Stevenson has been following this list. Maybe he's enjoying a long, long retirement at UC Davis. :-)

Depending on the numbers and capabilities and interests of the card 

players and the condition and prior groupings of the cards, we might 

start by separating the cards into stacks by card back or size. Some 

stacks, like the tarot cards that Chris mentioned, might be put aside at 

that point.

[Aylesworth, Marc A Ctr AFRL/IFSE]

I would do it the other way making 13 piles and sorting them by value
1,2,3... then place each value into another pile by suit.

Thanks
Marc Aylesworth

RRC C3I Group
AFRL/IFSE
Systems and Information Interoperability Branch

525 Brooks Rd
Rome, NY 13441-4505

Tel:315.330.2422
Fax:315.330.7009

Email: Marc.Ay...@rl.af.mil

-----Original Message-----
From: Hard...@googlegroups.com [mailto:Hard...@googlegroups.com] On Behalf

[K.S. Bhaskar]

I could just put each card down a pre-assigned place on the table and
pick them up in the right order... 8-)

Not a very scalable technique, but the fastest for a single deck of
cards, since it is easy to preassign a spot for each of 52 cards on a
kitchen table.

-- Bhaskar

[Jim Self]

Chris Richardson wrote:
> What Jim was describing with his 13 piles was a prescribed bucket sort. He
> know the kinds of cards he was going to come in contact with and have
> predefined the domain that he was going to project the "population to be
> sorted" into.

That (13 piles) was just for brevity of description of the solution to
the original problem.

The actual process I was thinking of was two parts.
1) Separate the cards into stacks by value.
2) reassemble the deck by picking up the stacks in order.

Knowing that playing cards have 13 values means that you can preassign
the location of the stacks in numerical order, so the process can be a
little quicker, but the layout of the stacks can be random and sorting
doesn't have to occur until the final step.