(Bucket Sort) A bucket sort begins with a one-dimensional array of positive integers to be sorted and a two-dimensional array of integers with rows subscripted from 0 to 9 and columns sub- scripted from 0 to n – 1, where n is the number of values in the array to be sorted. Each row of the two-dimensional array is referred to as a bucket. Write a function bucketSort that takes an integer array

and the array size as arguments and performs as follows:

a) Place each value of the one-dimensional array into a row of the 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 one-dimensional 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 tens digit) and 97 is placed in row 9. After the gathering pass, the order of the values in the one-dimensional 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 two-dimensional array of buckets is 10 times the size of the integer array being sorted. This sorting technique provides better performance than a insertion sort, but requires much more memory. The insertion 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 insertion sort, but performs better. This version of the bucket sort requires copying all the data back to the original array on each pass. Another possibility is to create a second two-dimensional bucket array and repeatedly swap the data between the two bucket arrays.

```
#include
using namespace std;

// constant size must be defined as the array size for bucketSort to work
const int SIZE = 12;

void bucketSort( int [] );
void distributeElements( int [], int [][ SIZE ], int );
void collectElements( int [], int [][ SIZE ] );
int numberOfDigits( int [], int );
void zeroBucket( int [][ SIZE ] );

int main()
{
int array[ SIZE ] = { 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21 };

// display the unsorted array
cout << "Array elements in original order:\n";

for ( int i = 0; i < SIZE; i++ )
cout << setw( 3 ) << array[ i ];

cout << '\n';
bucketSort( array ); // sort the array

cout << "\nArray elements in sorted order:\n";

// display sorted array
for ( int j = 0; j < SIZE; j++ )
cout << setw( 3 ) << array[ j ];

cout << endl;
} // end main

// Perform the bucket sort algorithm
void bucketSort( int a[] )
{
int totalDigits;
int bucket[ 10 ][ SIZE ] = {};

totalDigits = numberOfDigits( a, SIZE );

// put elements in buckets for sorting
// once sorted, get elements from buckets
for ( int i = 1; i <= totalDigits; i++ )
{
distributeElements( a, bucket, i );
collectElements( a, bucket );

if ( i != totalDigits )
zeroBucket( bucket ); // set all bucket contents to zero
} // end for
} // end function bucketSort
// Determine the number of digits in the largest number
int numberOfDigits( int b[], int arraySize )
{
int largest = b[ 0 ];
int digits = 0;

// find largest array element
for ( int i = 1; i < arraySize; i++ )
{
if ( b[ i ] > largest )
largest = b[ i ];
} // end for

// find number of digits of largest element
while ( largest != 0 )
{
digits++;
largest /= 10;
} // end while

return digits;
} // end function numberOfDigits

// Distribute elements into buckets based on specified digit
void distributeElements( int a[], int buckets[][ SIZE ], int digit )
{
int divisor = 10;
int bucketNumber;
int elementNumber;

for ( int i = 1; i < digit; ++i ) // determine the divisor
divisor *= 10; // used to get specific digit

for ( int k = 0; k < SIZE; ++k )
{
// bucketNumber example for hundreds digit:
// (1234 % 1000 - 1234 % 100) / 100 --> 2
bucketNumber = ( a[ k ] % divisor - a[ k ] %
( divisor / 10 ) ) / ( divisor / 10 );

// retrieve value in buckets[bucketNumber][0] to determine
// which element of the row to store a[i] in.
elementNumber = ++buckets[ bucketNumber ][ 0 ];
buckets[ bucketNumber ][ elementNumber ] = a[ k ];
} // end for
} // end function distributeElements

// Return elements to original array
void collectElements( int a[], int buckets[][ SIZE ])
{
int subscript = 0;
// retrieve elements from buckets
for ( int i = 0; i < 10; i++ )
{
for ( int j = 1; j <= buckets[ i ][ 0 ]; j++ )
a[ subscript++ ] = buckets[ i ][ j ];
} // end for
} // end function collectElements

// Set all buckets to zero
void zeroBucket( int buckets[][ SIZE ] )
{
// set all array elements to zero
for ( int i = 0; i < 10; i++ )
{
for ( int j = 0; j < SIZE; j++ )
buckets[ i ][ j ] = 0;
} // end for
} // end function zeroBucket
```
Array elements in original order:
19 13 5 27 1 26 31 16 2 9 11 21
Array elements in sorted order:
1 2 5 9 11 13 16 19 21 26 27 31