Single-subscripted array into a row of bucket array

jam2142 · #1 11-Oct-2008, 20:55

This is the problem from our book...so i hope you can help me..Im a new member of this forum..tnx anyway...

a.Place each value of the single-subscripted array into a row of bucket array based on the value's ones digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This is called a "distribution pass."
b) Loop through the bucket array row by row, and copy the values back to the original array. This is called a "gathering pass." The new order of the preceding values in the single-subscripted array is 100, 3 and 97.
c) Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.).

On the second pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no ten digit) and 97 is placed in row 9. After the gathering pass, the order of values in the single-subscripted array is 100, 3 and 97. On the third pass 100 is placed in row 1, 3 is placed in row zero and 97 is placed in row zero (after the 3). After the last gathering pass, the original array is now in sorted order.
Note that the double-subscripted array of buckets is 10 times the size of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. The bubble sort requires space for only one additional element of data. This is an example of the space-time trade-off: The bucket sort uses more memory than the bubble sort, but performs better. This version of the bucket sort requires copying all data back to the original array on each pass. Another possibility is to create a second double-subscripted array and repeatedly swap the data between the two bucket arrays.

Howard_L · #2 11-Oct-2008, 21:33

Why don't you start us off with a program:
- declaring the two arrays
- and maybe an attempt to do the 'first pass' processing of part 'a.'.
Then build from there.

Peter_APIIT · #3 12-Oct-2008, 00:20

I have coded a simple bucket sort.

Here it is.

CPP / C++ / C Code:

void bucketSort(int *originalArray, int size, int maxRange)
{

	int bucketElement;
	int bucket[3][5];

	int firstColumnLoop = 0;
	int SecondColumnLoop = 0;
	int thirdColumnLoop = 0;

	for (int myLoop=0;myLoop<size;myLoop++)
	{
		if (originalArray[myLoop] < 6 )
		{	
			bucket[0][firstColumnLoop++] = originalArray[myLoop];
		}
		
		else if (originalArray[myLoop] > 5 && originalArray[myLoop] < 11)
		{
			bucket[1][SecondColumnLoop++] = originalArray[myLoop];
		}
		else if (originalArray[myLoop] > 10 && originalArray[myLoop] < 16)
		{	
			bucket[2][thirdColumnLoop++] = originalArray[myLoop];
		}
	}

	
	int myLoop=0;

	for (int loop=0;loop<3;loop++)
	{
		for (int innerLoop=0;innerLoop<5;innerLoop++)
		{
			if (myLoop < 17)
			{
				originalArray[myLoop++] = bucket[loop][innerLoop];
				
			}
		}
	}

	/*
		A common optimization is to put the 
		elements back in the original array 
		first, then run insertion sort over the 
		complete array
	*/

	// Insertion Sort
	int index, value;

	for (int loop=1;loop<15;loop++)
	{
		index = loop;
		value = originalArray[loop];

		while(index > 0 && originalArray[index-1] > value)
		{
			originalArray[index] = originalArray[index-1];
			--index;
		}
		originalArray[index] = value;

	}

	for (int loop=0;loop<size;loop++)
	{
		cout << "\n" << originalArray[loop];
	}


}

Hope this helps.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Connect MS SQL Server 2005 to MFC Dialog application	-girl-	MS Visual C++ / MFC Forum	22	20-Aug-2008 16:58
Calculator Java Class	sneakerhead724	Java Forum	12	26-Mar-2008 21:16
I need help with three C++ assignments asap please	silverneon	C++ Forum	2	26-Apr-2007 05:40
Array 1 dimensional help please asap	lion123	C Programming Language	10	18-Feb-2005 22:53
Need Help ASAP	yeshwanth	C++ Forum	0	04-Oct-2004 02:22

Single-subscripted array into a row of bucket array

Re: help me..i need it asap..

Re: help me..i need it asap..