C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Implement Bucket Sort C++ Program to Implement Bucket Sort This is a C++ program to sort the given data using Bucket Sort. - We should implement Bucket Sort on uniformly distributed data over a range by splitting the range into equal parts. - Assign those parts as buckets and each bucket 'i' will be having 'Ni' number of the elements. - Selecting these Bucket for inserting will cost time complexity of O(N) where N is a total number of elements. - Sort them separately. We have used insertion sort which has a time complexity of summation of O(Ni^2). - Complexity for bucket sort is O(N + summation of(Ni^2)). - It is better than the other sorting algorithms (insertion sort, bubble sort, etc) with complexities O(N^2). - Divide the range into equal parts and assign a bucket to each part. - Split the data and insert them into the corresponding bucket using insertion sort. - Merge all the buckets into one. - Display the result. - Exit. #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; }