DeeptiBucketSortDemo, C++ (clang)

Language: Layout:

#include<iostream>
#include<string>
#include<vector>
#include<cmath>

using namespace std;

void printArrayToConsole(const int arr[], const char* phase, const size_t& size)
{
	cout << phase << endl;
	for(unsigned int i=0; i<size-1; ++i)
		cout << arr[i] << ", ";
	cout << arr[size-1] << endl;
}

void doRadixSort(int arr[], const size_t& size)
{
	int maxItem=arr[0];
	for(unsigned int i=0; i<size; ++i)
	{
		if(arr[i]>maxItem)
			maxItem=arr[i];
	}
	unsigned int numPasses = to_string(maxItem).length();
	vector<vector<int>> buckets;
	buckets.reserve(10);

for(unsigned int i=0; i<=9; ++i)
		buckets[i].reserve(size);
	for(unsigned int i=0; i<=9; ++i)
		buckets[i] = { };

int denominator=1, whichBucket, iter;
	for(unsigned int i=0; i<numPasses; ++i)
	{
		for(unsigned int j=0; j<size; ++j)
		{
			whichBucket = (arr[j]/denominator)%10;
			buckets[whichBucket].push_back(arr[j]);
		}

iter=0;
		for(unsigned int k=0; k<=9; ++k)
		{
			const vector<int>& bucketRef = buckets[k];
			if(bucketRef.size())
			{
				for(unsigned int l=0; l<bucketRef.size(); ++l)
				{
					arr[iter]=bucketRef[l];
					++iter;
				}
			}
		}

for(unsigned int j=0; j<=9; ++j)
			buckets[j].clear();

// Enable the below line to see intermediate passes.
		//printArrayToConsole(arr, "intermediate:", size);
		denominator*=10;
	}

for(unsigned int i=0; i<=9; ++i)
	{
		buckets[i].clear();
		buckets[i].shrink_to_fit();
	}
	buckets.clear();
}

void doInsertionSort(vector<int>& arr, const size_t& size)
{
	for(unsigned int i=0; i<size; ++i)
	{
		int pivot = arr[i];
		int j = i-1;

while(j>=0 && arr[j]>=pivot)
		{
			arr[j+1]=arr[j];
			--j;
		}
		arr[j+1]=pivot;
	}
}

void doBucketSort(int arr[], const size_t& size)
{
	// First identify the min and max of the array. 0(n).
	int minItem = arr[0], maxItem = arr[0];
	size_t bucketSize = 10;

for(unsigned int i=0; i<size; ++i)
	{
		if(arr[i]>maxItem)
			maxItem=arr[i];
		if(arr[i]<minItem)
			minItem=arr[i];
	}

// Identify the divisor element. ceil(max+1)/size.
	int divisor = ceil(static_cast<float>(maxItem+1)/static_cast<float>(bucketSize));

// Create the 10 buckets as indicated below.
	vector<vector<int>> buckets;
	buckets.reserve(10);
	for(unsigned int i=0; i<=9; ++i)
		buckets[i].reserve(size);
	for(unsigned int i=0; i<=9; ++i)
		buckets[i] = { };

int whichBucket;
	for(unsigned int i=0; i<size; ++i)
	{
		whichBucket=floor(arr[i]/divisor);
		buckets[whichBucket].push_back(arr[i]);
	}

// We just need to sort the items in each bucket via insertion sort.
	for(unsigned int i=0; i<=9; ++i)
		doInsertionSort(buckets[i], buckets[i].size());

// We need to iterate over each bucket and collect the items. They are sorted.
	int iter=0;
	for(unsigned int i=0; i<=9; ++i)
	{
		const vector<int>& bucketRef = buckets[i];
		if(bucketRef.size())
		{
			for(unsigned int j=0; j<bucketRef.size(); ++j)
			{
				arr[iter]=bucketRef[j];
				++iter;
			}
		}
	}

for(unsigned int i=0; i<=9; ++i)
	{
		buckets[i].clear();
		buckets[i].shrink_to_fit();
	}
	buckets.clear();
}

int main(int argc, char* argv[])
{
	int arr[] = {22, 45, 12, 8, 10, 6, 72, 81, 33, 18, 50, 14 };
	size_t size = sizeof(arr)/sizeof(arr[0]);
	printArrayToConsole(arr, "before :", size);
	doRadixSort(arr, size);
	printArrayToConsole(arr, "after :", size);
	doBucketSort(arr, size);
	printArrayToConsole(arr, "after :", size);
	return(0);
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.73 sec, absolute running time: 0.2 sec, cpu time: 0.13 sec, memory peak: 3 Mb, absolute service time: 0,94 sec