This is a C++ program to sort the given data using Bucket Sort.
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).
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.
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; }
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.
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.
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Programming Books
- Practice Programming MCQs
- Check C++ Books