Implementation of Bucket sort in C++

In this tutorial, you will learn bucket sort in C++ with its algorithm. Bucket sort is a sorting algorithm in which the elements of an array are stored in buckets, wherein they get sorted. After sorting they elements are gathered from the bucket and we obtain a sorted list.

The complexity of Bucket sort technique

  • Time complexity: Best case/ Average case: O(n+k), Worst case: O(N^2)
  • Space complexity: O(nk) for worst-case

  This sorting algorithm is used when input is uniformly distributed over a range. Bucket sort algorithm can be used when inputs are in between the range of 0 and 1,for example-0.25, 0.22, 0.58, 0.62, 0.73, 0.96, 0.78

Algorithms like Merge Sort, Heap Sort, Quick-Sort have time complexity of Ω(n Log n), i.e., they cannot do better than nLogn.

Using Bucket sort we can sort the array in linear time, hence this sorting algorithm is quite efficient.

Algorithm of Bucket Sort

bucket sort(array,size)

Input: The array containing data, and the total number of elements in the array

Output: The sorted Array

Begin

   for i := 0 to size-1 do

      insert array[i] into the bucket of index (size * array[i])

   done

   for i := 0 to size-1 do

      sort bucket[i]

   done

   for i := 0 to size -1 do

      gather items of bucket[i] and put in array

   done

End

Code in C++: Bucket sort

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

void display(float *array, int size) {

   for(int i = 0; i<size; i++)

      cout << array[i] << " ";

   cout << endl;

}

void bucketSort(float *array, int size) {

   vector<float> bucket[size];

   for(int i = 0; i<size; i++) { //adding elements into different buckets

      bucket[int(size*array[i])].push_back(array[i]);

   }

   for(int i = 0; i<size; i++) {

      sort(bucket[i].begin(), bucket[i].end()); //sort individual buckets

   }

   int index = 0;

   for(int i = 0; i<size; i++) {

      while(!bucket[i].empty()) {

         array[index++] = *(bucket[i].begin());

         bucket[i].erase(bucket[i].begin());

      }

   }

}

int main() {

   int n;

   cout << "Enter the number of elements: ";

   cin >> n;

   float arr[n]; //create an array with given number of elements

   cout << "Enter elements:" << endl;

   for(int i = 0; i<n; i++) {

      cin >> arr[i];

   }

   cout << "Array before Sorting: ";

   display(arr, n);

   bucketSort(arr, n);

   cout << "Array after Sorting: ";

   display(arr, n);

}

  Output:

Enter the number of elements: 6                                                                                                        

Enter elements:                                                                                                                        

0.1                                                                                                                                    

0.5                                                                                                                                    

0.4                                                                                                                                    

0.9                                                                                                                                    

0.8                                                                                                                                    

0.2                                                                                                                                    

Array before Sorting: 0.1 0.5 0.4 0.9 0.8 0.2                                                                                          

Array after Sorting: 0.1 0.2 0.4 0.5 0.8 0.9

 

Working

  • Buckets are created using vectors. The number of buckets is equal to the number of elements that are to be sorted. The elements of the array are placed in buckets. This storing is done by using key values. For example: if an integer array is to be sorted then the base(key) is 10. Whereas if alphabets were to be sorted then the key would be 26. Each element is to be divided by this key and the quotient would define the position of the bucket where the element should be placed. If the key is the same for two elements then the one appearing first should be stored first in the bucket.
  • The elements stored in each bucket is sorted using any sorting algorithm like insertion sort.
  • Then, the elements are collected from the bucket and stored in an array to obtain a sorted array.

Also read: Strand Sort in C++

Leave a Reply

Your email address will not be published. Required fields are marked *