C++ Program to Implement Bucket Sort

This is a C++ program to sort the given data using Bucket Sort.

Problem Description

1. We should implement Bucket Sort on uniformly distributed data over a range by splitting the range into equal parts.
2. Assign those parts as buckets and each bucket ‘i’ will be having ‘Ni’ number of the elements.
3. Selecting these Bucket for inserting will cost time complexity of O(N) where N is a total number of elements.
4. Sort them separately. We have used insertion sort which has a time complexity of summation of O(Ni^2).
5. Complexity for bucket sort is O(N + summation of(Ni^2)).
6. It is better than the other sorting algorithms (insertion sort, bubble sort, etc) with complexities O(N^2).

Problem Solution

1. Divide the range into equal parts and assign a bucket to each part.
2. Split the data and insert them into the corresponding bucket using insertion sort.
3. Merge all the buckets into one.
4. Display the result.
5. Exit.

Program/Source Code

A C++ Program to demonstrate Bucket Sort using adjacency list.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

#include <iostream>
 
using namespace std;
 
// A structure to represent a node.
struct Node
{
	int value;
	struct Node* next;
};
 
// A structure to represent a Head Bucket Node of the bucket list.
struct Bucket
{
	// Pointer to head node of Bucket.
	struct Node *head;  
};
 
struct BucketList
{
	int V;
	struct Bucket * array;
};
 
 
// A utility function to create a new node for a particular entry in a bucket.
struct Node* newNode(int value)
{
	struct Node* newnode = new Node;
	newnode->value = value;
	newnode->next = NULL;
	return newnode;
}
 
// A utility function that creates a list of the bucket over the range of input data.
struct BucketList* createBucket(int V)
{
	int i;
	struct BucketList* bl = new BucketList;
 
	bl->V = V;
	bl->array = new Bucket[V];   
 
 
	// Initialize each Bucket list as empty by making head as NULL.
	for(i = 0; i < V; i++)
		bl->array[i].head = NULL;
 
	return bl;
}
 
// A function to Insert the nodes to corresponding Buckets.
void addNode(struct BucketList* bl, int bckt, int value)
{
	// Creating new data node.
	struct Node *newnode = newNode(value);
	struct Node *temp = new Node;
 
	if(bl->array[bckt].head != NULL)
	{
		temp = bl->array[bckt].head;
 
		// Sorting.
		// If the head node value is lesser than the newnode value, then add node at beginning.
		if(temp->value > newnode->value)
		{
			newnode->next = bl->array[bckt].head;
			bl->array[bckt].head = newnode;
		}
		else
		{
			// Search for the node whose value is more than the newnode value.
			while(temp->next != NULL)
			{
				if((temp->next)->value > newnode->value)
					break;
 
				temp = temp->next;
			}
 
			// Insert newnode after temp node.
			newnode->next = temp->next;
			temp->next = newnode;
		}
	}
	else
	{
		// Assign head of the Bucket as newnode since bucket head is NULL.
		bl->array[bckt].head = newnode;
	}
}
 
// A function to print the result as sorted Data.
void printBuckets(struct BucketList *bl)
{
	int v;
	struct Node* pCrawl = new Node;
 
	for(v = 0; v < bl->V; v++)
	{
		// To view the data in individual bucket remove next line from comment.
		// cout<<"\n\t bucket "<<v+1;
 
		pCrawl = bl->array[v].head;
		while (pCrawl != NULL)
		{
			cout<<"->"<< pCrawl->value;
			pCrawl = pCrawl->next;
		}
	}
}
 
 
int main()
{
	// Create the BucketLists for the data and set 10 as default number of Buckets.
	int V = 10, range, NOE, i;
	struct BucketList* mybucket = createBucket(V);
 
 
	cout<<"\n\nEnter the upper limit in the power of 10 (10 or 100 or 1000 ..) to create Bucket: ";
	cin>>range;
 
	// Dividing range into 10 parts so it will have 10 buckets as default.
	range = range/10;
 
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>NOE;
	int arr[NOE];
 
	for(i = 0; i < NOE; i++)
	{
		cout<<"Enter element "<<i+1<<" : ";
		cin>>arr[i];
		addNode(mybucket, arr[i]/range, arr[i]);
	}
 
	// Print the adjacency list representation of the BucketList i.e the sorted Output.
	cout<<"\nSorted Data ";
	printBuckets(mybucket);
 
	return 0;
}
Program Explanation

1. Create Node, Bucket and BucketList structures.
2. Take range and data, which should be uniformly distributed over the range.
3. Allocate memory to their objects accordingly.
4. Insert the data into the list according to their value which comes out to dividing data into the bucket.
5. Sort data using insertion sort in the linked lists.
6. Display the result.
7. Exit.

advertisement
advertisement
Runtime Test Cases
Case 1:(average case)
 
Enter the upper limit in the power of 10 (10 or 100 or 1000 ..) to create Bucket: 100
 
Enter the number of data element to be sorted: 5
Enter element 1: 1
Enter element 2: 99
Enter element 3: 83
Enter element 4: 94
Enter element 5: 33
 
Sorted Data ->1->33->83->94->99
 
 
Case 2:(best case)
 
Enter the upper limit in the power of 10 (10 or 100 or 1000 ..) to create Bucket: 1000
 
Enter the number of data element to be sorted: 5
Enter element 1: 1
Enter element 2: 444
Enter element 3: 631
Enter element 4: 483
Enter element 5: 989
 
Sorted Data ->1->444->483->631->989
 
 
case 3: (worst case)
 
Enter the upper limit in the power of 10 (10 or 100 or 1000 ..) to create Bucket: 100
 
Enter the number of data element to be sorted: 5
Enter element 1: 99
Enter element 2: 85
Enter element 3: 43
Enter element 4: 21
Enter element 5: 11
 
Sorted Data ->11->21->43->85->99

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.