Thread: manually sorting cards

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229

    manually sorting cards

    Not exactly programming but...

    I have a stack of 100 cards numbered 1-100. Distribution is random. With a memory restraint of the size of a desk, what is the most efficient way to sort it manually?

    I did a bucket sort (into piles of 10) and then insertion sorts on the individual piles. Is there a more efficient way?

    Thanks =)

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Try mergesort.

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Is mergesort more efficient? Since it's a comparison sort, it has a lower bound of O(nlogn) where bucket sort would do it in O(n) avg if I understand it correctly (according to wikipedia). And in this case, I do have the information required for bucket sort.

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    No, I wasn't being helpful. I just wanted to see if you could do it. But mergesort is quite intiutive to real life, and you can definitely make minimal use of your desk. The only thing you need is a sorted pile and an unsorted pile. The idea is to build the sorted pile by inserting cards yourself. I think you can do it pretty fast. Maybe I'm too quick to judge on the helpfulness thing.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    But mergesort is quite intiutive to real life, and you can definitely make minimal use of your desk. The only thing you need is a sorted pile and an unsorted pile. The idea is to build the sorted pile by inserting cards yourself.
    I think you are thinking of insertion sort rather than merge sort.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    I think you are thinking of insertion sort rather than merge sort.
    That is what I thought, too.

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Wow. We need lives.

  8. #8
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,130
    Is there a more efficient way?
    Hire 10 Indians or Ukrainians to do it for you ?
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  9. #9
    The superhaterodyne twomers's Avatar
    Join Date
    Dec 2005
    Location
    Ireland
    Posts
    2,273
    Buy a new set.

  10. #10
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Direct placement sort. Draw 100 squares on the ground, labeled 1-100. For each card, place it on the matching square. Now pick them up in order. (This is a special case of rank sort)

    Even more efficient, don't sort the cards at all, but merely imagine that they are sorted.
    Last edited by brewbuck; 05-13-2008 at 12:13 PM.

  11. #11
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by brewbuck View Post
    Direct placement sort. Draw 100 squares on the ground, labeled 1-100. For each card, place it on the matching square. Now pick them up in order. (This is a special case of rank sort)

    Even more efficient, don't sort the cards at all, but merely imagine that they are sorted.
    Hmm

    Code:
    int* DPSort(int *Data)
    {
    	int Table[100];
    	int SortedData[100];
    	unsigned int i = 0;
    	for(; i < 100; i++)
    	{
    		Table[i] = i+1;
    	}
    	
    	for(i = 0; i < 100; i++)
    	{
    		for(unsigned int j = 0; j < 100; j++)
    		{
    			if(Data[i] == Table[j])
    			{
    				SortedData[j] = Data[i];
    				break;
    			}
    		}
    	}
    	
    	return SortedData;
    }
    Something tells me this will be very inefficient?

    Edit: Ready to flame the first one to comment my poor code!
    Last edited by Neo1; 05-13-2008 at 12:33 PM.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    That doesn't model brewbuck's idea. It relies on the fact that Table[j] always equals j+1. So remove your j loop and your if and simply set SortedData[Data[i]+1] = Data[i].

    I would make either 10 or 20 piles and sort by the first digit in the number on the card first, then sort each individual pile as I picked them up.

    The most efficient algorithm depends on how fast your mind can determine the proper location and deal the cards, not so much what the most efficient algorithm in code would be.

  13. #13
    Registered User
    Join Date
    Nov 2004
    Location
    USA
    Posts
    516
    Hire 10 Indians or Ukrainians to do it for you ?
    Or maybe 100 Germans
    Code:
    >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.

  14. #14
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I would indeed go for bucket sort. Have ten stacks. Put 1-9 into the first, 10-19 into the second, and so on. (The first stack will have 9 cards, and the last 11. That's fine. It's worth the faster recognition.)

    Then sort the individual stacks and put them together.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  15. #15
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    It kinda matters what type of cards these are also and how you want to sort them. For example if you were trying to sort two playing decks (104 cards) then I would just make a pile for each type of card (2s, 3s, Js, Qs, etc). If you wanted to do them by suit and rank then I'd probably just make 8 rows each with a suit and then put the card in the right spot (insertion sort) as I got to it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  2. Help it won't compile!!!!!
    By esbo in forum C Programming
    Replies: 58
    Last Post: 01-04-2009, 03:22 PM
  3. Help!For poker game simulation
    By tx1988 in forum C++ Programming
    Replies: 24
    Last Post: 05-25-2007, 09:59 PM
  4. Cribbage Game
    By PJYelton in forum Game Programming
    Replies: 14
    Last Post: 04-07-2003, 10:00 AM
  5. playing ... cards??
    By GiraffeMan in forum C Programming
    Replies: 16
    Last Post: 02-06-2002, 03:51 PM