sorting cards again

[Greg Woodhouse]

I ws a little surprised that no one said anything about Bhaskar's proposed solution (with 52 empty slots in front of you on the table, just go through the deck once, placing each card in its proper place). This solution seems to "violate the laws of physics". Allow me to explain: The sorting algorithms we've discussed can be broadly divided into two groups. The slower solutions (like bubble sort and selection sort) are called O(n^2) sorts (or just quadratic sorts). This means that in the limit, as n becomes large, the running time will be approximate proportional to n^2 (n squared). For bubble sort, this is obvious because in each round, you go through the unsorted cards just once, potentially interchanging cards at each step. But each round will add just one card to the sorted tail, so the number of steps is roughly

1 + 2 + 3 + ... + n = n * (n - 1) / 2

and this is approximately n^2/n when n becomes large (the differenc e is proportional to 1/n which approaches 0).

The other group of sorts (quicksort and merge sort, for example) are O(n * log n), and so hese are called n log n sorts (in mathematics, the "*" indicating multiplication is usually dropped). In fact, it can be shown that a comparison based sort (one in which decisions are made by comparing individual values) cannot be faster than O(n log n). What is possible is for one sort to be faste than another by a constant factor, but that is all.

But Bhaskar's sort just involves running through the cards once, it is a O(n) sort. What's going on here? Shouldn't that be impossible?

===
Gregory Woodhouse

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

[K.S. Bhaskar]

Yes, this is part of a good interview discussion when hiring a computer
scientist (e.g., for GT.M development). Ask what their reaction would
(should) be - and why - if someone were to come to them claiming to have
an O(n) sorting algorithm.

[Side note: This immediately eliminates the majority of candidates - I
find it sad how many people have Masters degrees in Computer Science and
can't answer a question as basic to computer science as, say, the need
for an ER doctor to be able to identify and treat for shock.]

Once they have explained why it can be proved that an algorithm cannot
possibly do better than O(n log(n)), give them the apparent O(n)
technique for sorting, and ask them to explain what's going on...

-- Bhaskar

[Greg Woodhouse]

I'll bet you could eliminate more than a few candidates that way!

So... Does anyone care to hazard a guess as to how Bhaskar managed to break the laws of physics (after all, computer science is just a branch of physics)?

===
Gregory Woodhouse

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

[Holloway, Thomas (EDS)]

Greg,
I don't see any logical difference between Bhaskar's 52 slots on the
table and my 2nd solution; 'sort as you go'. I simply reserve 52
positions in my left hand, pick up a card with my right hand and place
it in its allocated spot in my left hand. The fan of cards in my hand
acts a bit like a sparse array whereas the spots on the table are
equivalent to a pre-defined array but the process of filling the array
is logically the same, i.e. select the location, in relationship to the
other cards, where the new card belongs and place it there. If the
desired result is a stack of cards in sorted order, then my method has
the advantage that you just have to fold the fan whereas the cards on
the table would have to be picked up one by one, but that's a separate
issue from the sorting.

tjh

[Greg Woodhouse]

How do you find the correct spot in "sort as you go" (a.k.a. insertion sort)?

===
Gregory Woodhouse

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

----- Original Message ----
From: "Holloway, Thomas (EDS)" <Thomas....@va.gov>
To: Hard...@googlegroups.com
Sent: Tuesday, October 24, 2006 12:53:55 PM
Subject: [Hardhats] Re: sorting cards again

[r...@rcresearch.us]

Greg;

It is so easy. Start with one card in the sorting hand and place it in
the holding hand. Pick up the next card and look at the value. Does it
go before or after the card already in the holding hand? If greater,
put it behind the card already there. If less, then put it in front of
that card. Go get the next card and read the value of the card. You
now have 3 places that this card can go, before, between, or after the
two cards in the holding hand. In each successive card sort, you will
have n+1 (where n is the number of cards in the holding hand) possible
locations to place the next card. Finding the location is the trick.

Obviously as the number goes up, the time to find the proper place to
put it goes up as well. People are lumpers, and computers are usually
rigorous. Humans make intuitive jumps to get us close to the answer
while computers usually check every possibility. I suspect that humans
are scalable in this task up until the fist full of cards gets akward
and we re-invent that wonderful randomization game, 52-pickup.

[gregory....@sbcglobal.net]

Exactly. Now compare this with Bhaskar's algorithm: How do you go about finding the proper spot for each card there? How long does it take?

Am I spoiling all the fun?

===
Gregory Woodhouse

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

----- Original Message ----
From: r...@rcresearch.us
To: Hard...@googlegroups.com
Sent: Tuesday, October 24, 2006 1:24:12 PM
Subject: [Hardhats] Re: sorting cards again

[r...@rcresearch.us]

Of course you are, Greg, of course you are...

but we do save on the time it takes to put the deck back together.

This is actually doing the sort as a string expansion. In this specific
case, we know how many items we are sorting and in Bhaskar's example, we
see the cards we are missing immediately. As a string, it might be a bit
more confusing to identify missing members.

[Holloway, Thomas (EDS)]

Well, I might ask how you find the correct spot on the table. Is it
labeled? Or are there just 52 little rectangles drawn on the table
(either in a single long row, or multiple shorter rows)? In either case
I think that the mental process is the same or pretty much the same. I
want to cover another case in a minute but for this exercise we seem to
be assuming a logical, sequential relationship between the cards. If I
pick up card number 45 (or its playing card equivalent... the 7 of Clubs
maybe?) I "know" almost immediately that it belongs near the end of the
allocated spaces. I can look there quickly, ignoring at least 2/3s of
the spaces. Now I have some choices: if the spots are labeled I can do
a proximity search for the spot numbered 45, or I can do some quick math
and determine that the card belongs in the spot 8 places from the end
and count them out. If the spots are not labeled I must use the latter
method, OR if some cards are already placed I can evaluate the relative
position of the new card. Say 44 is already there. I don't have to
subtract or count, I "know" that 45 goes right next to 44 (or two spots
away from 43, etc). Even if the spots are pre-labeled, I might use the
existing cards to guide my search.
So my answer to your question is that I would use the same technique in
placing cards in my hand. The caveat is that I won't be able to have
labeled spots but the other aspects are the same. If I pull up card 1 I
know it goes on the far left, if I pick up card 52 I know it goes on the
far right. I use existing cards in the fan to guide me to the specific
location.

Ok, another case. Everything we've covered on this scenario relies on
a convenient, numeric sort order. What changes in your sorting
technique if I hand you a shuffled deck of 52 cards with pictures of a
house, a ball, a tree, a hammer, a cloud, etc., and I give you a list
that is the prescribed order? If the first card you pick up is an
acorn, where does it go? Near the beginning, in the middle somewhere or
near the end? Does it go between the rabbit and frying pan? Is it
higher or lower than the thumbtack? Can you quickly put everything in
stacks of 4 or 5 and then sort those smaller stacks into order? You
could do that with the playing cards (or numerically numbered cards) but
trying to do it with random picture cards, even though there is a
specified order, will be very difficult.

tjh

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

Sent: Tuesday, October 24, 2006 4:03 PM
To: Hard...@googlegroups.com
Subject: [Hardhats] Re: sorting cards again

How do you find the correct spot in "sort as you go" (a.k.a. insertion
sort)?

===
Gregory Woodhouse

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

----- Original Message ----
From: "Holloway, Thomas (EDS)" <Thomas....@va.gov>
To: Hard...@googlegroups.com
Sent: Tuesday, October 24, 2006 12:53:55 PM
Subject: [Hardhats] Re: sorting cards again

[Gaber, Roy G.]

Which implies that we are creatures of habit and limited in our approach
to certain, if not all, problems?

If we had learned early on in our development to recognize the pictures
as opposed to numbers, the task would be a simple as the logic defined
in the responses to the question.

The key, in my opinion, is to be comfortable with our individual
approaches to the logic we employ in response to the task at hand.

We can utilize the approaches listed in the threads of this message to
accomplish the task, as long as the task is completed, it does not
matter how we get there (within reason of course).

This does not imply that we should be sloppy, or disregard other
methods, only that we have the hardware to support most approaches to a
similar task.

[Jim Self]

Greg Woodhouse wrote:
> I ws a little surprised that no one said anything about Bhaskar's proposed solution (with 52 empty slots in front of you on the table, just go through the deck once, placing each card in its proper place).

I did (4 rows of 13). You evidently missed it.

[Greg Woodhouse]

Great observation. The "insertion" part of insertion sort involves linearly searching through a list that is already sorted to find the right insertion point. If the card you select is the ace of spades, then you probably can guess that it's going to go at the end, anyway, so why bother ith the search phase? If the card is the 10 of hearts, then it's reasonable to think the insertion point will be closer to th end than the beginning, so it's reasonable to select a starting position close to the end, even though you might have to back up a bit.

I'm not sure I fully understand what you are asking in your secon paragraph below. Is the idea that the cards will fit in 4 or 5 natural cagoerie (animal, vegetable, mineral and the like), but you don't know a priori what those categories are?

===
Gregory Woodhouse

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

----- Original Message ----
From: "Holloway, Thomas (EDS)" <Thomas....@va.gov>
To: Hard...@googlegroups.com
Sent: Tuesday, October 24, 2006 1:39:25 PM
Subject: [Hardhats] Re: sorting cards again

[Holloway, Thomas (EDS)]

Greg asked: "Is the idea that the cards will fit in 4 or 5 natural

cagoerie (animal, vegetable, mineral and the like), but you don't know a
priori what those categories are?"

Greg,
No, the reference was to one of your proposals which was to put the
cards in small stacks, then pick up each small stack and sort within
that, then somehow combine stacks. The reason that works is because of
the nature of a deck of playing cards (4 Aces, 4 Twos, 4 Jacks, etc. or
13 Clubs, 13 Hearts, etc.) and the human brain can easily grasp those
distinctions. My idea for the picture cards is that they do *not* have
any categorical distinctions. Thus there is no easy, visual, intuitive
grouping in the sort order. Your original sorting problem was tied to a
distinctive data set which lent itself to some specific techniques.
Even if the cards were numbered 1 - 52 and not marked as playing cards,
we (as educated humans) have a built-in sort order that we can mentally
refer to nearly instantaneously. If the card markings were not natural
to us and if the sort order were not instinctive but instead available
from a written list, we would be forced to approach the sort from an
entirely different stand point. For one thing, it is highly unlikely
that you would use the divide-and-conquer approach or the bubble sort.
Until you memorize the list, you can't even use any sort of proximity
search on a labeled layout. I guess my real point was that using
intuition (something you had mentioned doing) is highly dependent on the
type of cards and the desired sort results. And I wasn't sure where you
were going with the SORT question. Is there a best sort technique that
is independent of the data set? Is it ever worth implementing a human
oriented technique in a computer-based sort?

tjh

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

[Gregory Woodhouse]

On Oct 25, 2006, at 7:49 AM, Holloway, Thomas ((EDS)) wrote:

Greg asked: "Is the idea that the cards will fit in 4 or 5 natural

cagoerie (animal, vegetable, mineral and the like), but you don't know a

priori what those categories are?"  

Greg,

  No, the reference was to one of your proposals which was to put the

cards in small stacks, then pick up each small stack and sort within

that, then somehow combine stacks.  The reason that works is because of

the nature of a deck of playing cards (4 Aces, 4 Twos, 4 Jacks, etc. or

13 Clubs, 13 Hearts, etc.) and the human brain can easily grasp those

distinctions.  My idea for the picture cards is that they do *not* have

any categorical distinctions.  ...

   tjh

I think you may have misunderstood (or, more to the point, I may have not been very clear). The idea is to separate the cards into 4 stacks at random. Just cut the cards into two stacks of about the same size and repeat the process. The 4 stacks are then sorted independently, without regard to the contents of the other stacks. The contents can then be merged into 2, then 1 stack. The merge process is O(n + m) where n and m are the size of the two sorted stacks.

How does this work out? Well a a naive sort will take about 52^2 = 2704 steps. On the other hand 4 * 13^2 = 676. So the total number of steps is 676 + 2 * 26 + 52 = 780.

Gregory Woodhouse

gregory....@sbcglobal.net

"If everything seems under control,

you're just not going fast enough."

-- Mario Andretti