Bucket Sort in C++

/* Bucket Sort
Created by using MS2013
Coded by M. Hasan
(Bucket Sort) A bucket sort begins with a single-subscripted array of positive integers to be sorted and a double-subscripted
array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n - 1, where n is the number of values in the
array to be sorted. Each row of the double-subscripted 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 single-subscripted 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 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 tens digit) and 97 is placed in row 9. After the
gathering pass, the order of the 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, b ut
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 double-subscripted bucket array and repeatedly swap the data between the two bucket arrays.
*/
#include <iostream>
#include <iomanip>
using namespace std;
 
const int SIZE = 12;
int array[SIZE] = { 21, 43, 75, 23, 12, 5, 7, 28, 34, 65, 3, 82 };
 
void bucketSort(int[]);
int numberOfDigits(int[], int);
void distributeElements(int[], int[][SIZE], int);
void collectElements(int[], int[][SIZE]);
void zeroBucket(int[][SIZE]);
void printArray(int[]);
 
int main(){
 cout << "Array in actual order" << endl;
 printArray(array);
 bucketSort(array);
 printArray(array);
 return 0;
}
void printArray(int a[SIZE]){
 for (int i = 0; i < SIZE; i++)
  cout << setw(4) << a[i];
 cout << endl;
}
void bucketSort(int a[]){
 int totalDigits, bucket[10][SIZE] = { 0 };
 totalDigits = numberOfDigits(a, SIZE);
 
 for (int i = 1; i <= totalDigits; i++){
 
  distributeElements(a, bucket, i);
  collectElements(a, bucket);
  if (i != totalDigits)
   zeroBucket(bucket);
 }
}
//Determine the number of digits in the largest number
int numberOfDigits(int a[], int arraySize){
 int digit = 0;
 int largest = a[0];
 for (int i = 1; i < arraySize; i++)
  if (a[i] > largest)
   largest = a[i];
 
 while (largest != 0){
  digit++;
  largest = largest / 10;
 }
 return digit;
}
void distributeElements(int a[], int bucket[][SIZE], int digit){
 int divisor = 10;
 int bucketNumber, elementNumber;
 
 for (int i = 1; i < digit; i++)//determine the divisor
  divisor *= 10;    //get the specific digit
 
 for (int i = 0; i < SIZE; i++){
  //bucketNumber Example for 100 digits:
  //(1234 % 1000 - 1234 % (1000 / 10)) / (1000/10)
  //(234-34)/100 =2
  bucketNumber = (a[i] % divisor - a[i] % (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] = a[i];
  cout << setw(4) << a[i]; //for debug perpose
  if (i == 11)
   cout << endl << endl;//for debug perpose
 }
}
void collectElements(int a[], int bucket[][SIZE]){
 int subscript = 0;
 for (int i = 0; i < 10; i++)
  for (int j = 1; j <= bucket[i][0]; j++)//j cannot start from 0 why?
   a[subscript++] = bucket[i][j];
 printArray(array);//for debug perpose
}
void zeroBucket(int bucket[][SIZE]){
 for (int i = 0; i < 10; i++)
  for (int j = 0; j < SIZE; j++)
   bucket[i][j] = 0;
}

output:

Array in actual order
  21  43  75  23  12   5   7  28  34  65   3  82
  21  43  75  23  12   5   7  28  34  65   3  82

  21  12  82  43  23   3  34  75   5  65   7  28
  21  12  82  43  23   3  34  75   5  65   7  28

   3   5   7  12  21  23  28  34  43  65  75  82
   3   5   7  12  21  23  28  34  43  65  75  82