#include<iostream>
#include <ctime>
#include<iomanip>

int const SIZE = 12;
using namespace std;

void BucketSort(int[]);
void Distribute_Elements(int[], int[][SIZE], int[], int);
void Collect_Elements(int[], int[][SIZE], int[]);
int Number_of_Digits(int [], int);
void Zero_Bucket(int[]);

void ResetBuckte(int[]);

int main()
{
	srand( (unsigned)time( NULL ) );

	int array[SIZE];

	for( int z=0; z<SIZE; z++)
		array[z]=rand()%999;

	// display unsorted
	cout<<"unsorted"<<endl;
	for(int i=0; i< SIZE; i++)
		cout<<array[i]<<"  ";

	cout<<endl<<endl;

	//sort array
	BucketSort(array);

	// display unsorted
	cout<<"sorted"<<endl;
	for(i=0; i< SIZE; i++)
		cout<<array[i]<<"  ";
	
	return 0;
}

void BucketSort(int array[] )
{
	int buckets[10][SIZE];
	// this is the index off all arrays
	int index[10]={0};

	
	Distribute_Elements(array, buckets, index, 1);
	Collect_Elements( array, buckets,  index);
	Zero_Bucket(index);

	Distribute_Elements(array, buckets, index, 2);
	Collect_Elements( array, buckets,  index);
	Zero_Bucket(index);

	Distribute_Elements(array, buckets, index, 3);
	Collect_Elements( array, buckets,  index);
	Zero_Bucket(index);
}
void Zero_Bucket(int index[])
{
	for(int i =0; i<10; i++)
		index[i]=0;
}

void Collect_Elements(int array[], int buckets[][SIZE], int index[])
{
	int bucket_number = 0;
	int index_of_index = 0;

	for( int i=0; i<SIZE;)
	{
		for(int j=0; j<index[index_of_index]; j++)
		{			
			array[i++]=buckets[bucket_number][j];
		}
		index_of_index++;
		bucket_number++;
	}
}


void Distribute_Elements(int array[], int buckets[][SIZE], int index[], int position)
{
	for( int i=0; i< SIZE; i++)
	{		
		// for last digit on right
		if(position ==1)
		{
			for(int j =0; j<10; j++)
			{
				if(array[i]%10 == j)
				{
					buckets[j][index[j]++]=array[i];
				}	
			}
		}
		
		// for second digit from right to left
		else if(position ==2)
		{
			for(int j =0; j<10; j++)
			{
				if( ((array[i]/10)%10) == j)
				{
					buckets[j][index[j]++]=array[i];
				}	
			}
		}

		// for third digit from right to left
		else if(position ==3)
		{
			for(int j =0; j<10; j++)
			{
				if(  ((array[i]/100)%10) == j)
				{
					buckets[j][index[j]++]=array[i];
				}	
			}
		}

	}
}