(Bucket Sort) A bucket sort begins with a one-dimensional vector of positive integers to be sorted and a two-dimensional vector of integers with rows indexed from 0 to 9 and columns indexed from 0 to n – 1, where n is the number of values to be sorted. Each row of the two-dimensional vector is referred to as a bucket. Write a class named BucketSort containing a function called sort that

operates as follows:

a) Place each value of the one-dimensional vector into a row of the bucket vector, based on the value’s “ones” (rightmost) digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This procedure is called a distribution pass.
b) Loop through the bucket vector row by row, and copy the values back to the original vector. This procedure is called a gathering pass. The new order of the preceding values in the one-dimensional vector is 100, 3 and 97.
c) Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.).
On the second (tens digit) 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 vector is 100, 3 and 97. On the third (hundreds digit) pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after the 3). After this last gathering pass, the original vector is in sorted order.Note that the two-dimensional vector of buckets is 10 times the length of the integer vector 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 comparison 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 the data back to the original vector on each pass. Another possibility is to create a second two-dimensional bucket vector and repeatedly swap the data between the two bucket vectors.

```
// Class BucketSort contains a vector of random integers and a function
// that uses bucket sort to sort the integers.
#include
using namespace std;

class BucketSort
{
public:
BucketSort( int ); // constructor initializes vector
void displayElements() const; // display vector elements
void sort(); // perform a bucket sort on vector
private:
int size; // vector size
vector< int > data; // vector of ints
vector< vector < int > > bucket; // two-dimensional vector of ints

// utility functions used by member function bucketSort
void distributeElements( int );
void collectElements();
int numberOfDigits();
void zeroBucket();
}; // end class BucketSort
```
```
// BucketSort class member-function definitions.
#include
#include // prototypes for functions srand and rand
#include // prototype for function time
using namespace std;

#include "BucketSort.h" // BucketSort class definition

// constructor
BucketSort::BucketSort( int vectorSize )
{
size = ( vectorSize > 0 ? vectorSize : 10 ); // validate vectorSize
srand( time( 0 ) ); // seed using current time

// fill vector with random ints in range 10-99
for ( int i = 0; i < size; i++ )
data.push_back( 10 + rand() % 90 ); // 10-99

// create bucket vector of appropriate size
for ( int i = 0; i < 10; i++ )
bucket.push_back( vector < int >( size ) );
} // end BucketSort constructor

// display vector elements
void BucketSort::displayElements() const
{
for ( int i = 0; i < size; i++ )
cout << data[ i ] << " ";

cout << endl;
} // end function displayElements

// perform a bucket sort on vector
void BucketSort::sort()
{
int totalDigits;
zeroBucket();

totalDigits = numberOfDigits();

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

if ( i != totalDigits )
zeroBucket(); // set all bucket contents to zero
} // end for
} // end function sort

// distribute elements into buckets based on specified digit
void BucketSort::distributeElements( 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 = ( data[ k ] % divisor - data[ k ] %
( divisor / 10 ) ) / ( divisor / 10 );

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

// return elements to original array
void BucketSort::collectElements()
{
int subscript = 0;

// retrieve elements from bucket vector
for ( int i = 0; i < 10; i++ )
{
for ( int j = 1; j <= bucket[ i ][ 0 ]; j++ )
data[ subscript++ ] = bucket[ i ][ j ];
} // end for
} // end function collectElements

// determine the number of digits in the largest number
int BucketSort::numberOfDigits()
{
int largest = data[ 0 ];
int digits = 0;

// find largest vector element
for ( int i = 1; i < size; i++ )
{
if ( data[ i ] > largest )
largest = data[ i ];
} // end for

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

return digits;
} // end function numberOfDigits

// set all buckets to zero
void BucketSort::zeroBucket()
{
// set all vector elements to zero
for ( int i = 0; i < 10; i++ )
{
for ( int j = 0; j < size; j++ )
bucket[ i ][ j ] = 0;
} // end for
} // end function zeroBucket
```
```
// Test program that demonstrates bucket sort.
#include
#include "BucketSort.h" // BucketSort class definition
using namespace std;

int main()
{
BucketSort sortVector( 12 ); // create BucketSort object

cout << "Vector elements in original order:\n";
sortVector.displayElements();

sortVector.sort(); // sort the vector

cout << "\nVector elements in sorted order:\n";
sortVector.displayElements();
return 0;
} // end main
```
Vector elements in original order:
88 84 80 96 15 30 76 51 88 52 11 71
Vector elements in sorted order:
11 15 30 51 52 71 76 80 84 88 88 96