All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
The Card Sorting Machine (Posted on 2004-11-12) Difficulty: 3 of 5
A bridge catalogue has a machine for dealing cards. It can take a randomly arranged deck and divide it into four piles in any way you choose, but the order of the cards in each pile will be in the same order as they were in the deck.

Example: Deck starts as {5H 4C 3S 4S 4H 2D 3D 5S 2S 2C 5D 2H 5C 3C 4D 3H} Sort by suits creates piles: {5H 4H 2H 3H} {4C 2C 5C 3C} {2D 3D 5D 4D} {3S 4S 5S 2S}

Suppose that we run a deck through the machine several times, each time taking the four piles and placing them on top of each other in a fixed order. How many runs does it take to sort a deck into complete rank order, from ace of clubs to king of spades?

See The Solution Submitted by Brian Smith    
Rating: 3.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution re: A less pure conjecture | Comment 3 of 4 |
(In reply to A less pure conjecture by owl)

This is exactly the same method as Oskar's, though with a different numbering. Writing numbers in base 4, here clubs are given numbers 0xx, hearts 1xx, diamonds 2xx, and spades 3xx, where xx is 00 for an ace, 01 for a 2, 02 for a 3, and so on up to 30 for a King.

CS people will note that the answer (3) is really an optimum, because "Radix Sort" is the only sort that works in O(N) time -- with log(N) in base B runs, B being 4 in this case.
  Posted by Federico Kereki on 2004-11-13 16:25:58

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information