manually sorting cards

cyberfish · 05-12-2008, 10:18 PM

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 =)

whiteflags · 05-12-2008, 10:38 PM

Try mergesort.

cyberfish · 05-12-2008, 10:43 PM

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.

whiteflags · 05-12-2008, 10:50 PM

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.

**laserlight** · 05-12-2008, 11:01 PM

Quote:

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.

cyberfish · 05-12-2008, 11:03 PM

Quote:

I think you are thinking of insertion sort rather than merge sort.

That is what I thought, too.

MacGyver · 05-13-2008, 01:02 AM

Wow. We need lives.

**nvoigt** · 05-13-2008, 05:05 AM

Quote:

Is there a more efficient way?

Hire 10 Indians or Ukrainians to do it for you ?

twomers · 05-13-2008, 11:55 AM

Buy a new set.

brewbuck · 05-13-2008, 12:11 PM

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.

Neo1 · 05-13-2008, 12:31 PM

Quote:

Originally Posted by brewbuck

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!

Daved · 05-13-2008, 12:52 PM

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.

PING · 05-13-2008, 12:52 PM

Quote:

Hire 10 Indians or Ukrainians to do it for you ?

Or maybe 100 Germans

**CornedBee** · 05-13-2008, 01:15 PM

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.

**Thantos** · 05-13-2008, 01:22 PM

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.

05-12-2008, 10:18 PM	#1
cyberfish Registered User Join Date: Dec 2006 Location: Canada Posts: 2,007	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 =)
cyberfish is offline

05-12-2008, 10:38 PM	#2
whiteflags MENTAL DETECTOR Join Date: Apr 2006 Location: United States Posts: 3,292	Try mergesort.
whiteflags is offline

05-12-2008, 10:43 PM	#3
cyberfish Registered User Join Date: Dec 2006 Location: Canada Posts: 2,007	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.
cyberfish is offline

05-12-2008, 10:50 PM	#4
whiteflags MENTAL DETECTOR Join Date: Apr 2006 Location: United States Posts: 3,292	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.
whiteflags is offline

05-13-2008, 01:02 AM	#7
MacGyver Deathray Engineer Join Date: Mar 2007 Posts: 3,211	Wow. We need lives. __________________
MacGyver is offline

05-13-2008, 11:55 AM	#9
twomers The superheterodyne. Join Date: Dec 2005 Location: Ireland Posts: 2,215	Buy a new set. __________________ I blag!
twomers is offline

05-13-2008, 12:11 PM	#10
brewbuck Senior software engineer Join Date: Mar 2007 Location: Portland, OR Posts: 5,763	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.
brewbuck is offline

05-13-2008, 12:52 PM	#12
Daved Registered User Join Date: Jan 2005 Posts: 7,252	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.
Daved is offline

05-13-2008, 01:15 PM	#14
CornedBee Cat without Hat Join Date: Apr 2003 Posts: 8,492	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
CornedBee is offline

05-13-2008, 01:22 PM	#15
Thantos & the hat of GPL slaying Join Date: Sep 2001 Posts: 5,732	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.
Thantos is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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