Advanced C++ Programming and Algorithms

Bucket Sort Algorithm with C++

Board Infinity
Board Infinity
Bucket Sort Algorithm with C++

    OOPs (Object Oriented Programming) in C++

    A Quick Guide to Encapsulation in C++

    OOPs Abstraction in C++

    OOPS Polymorphism with C++

    Multiple Inheritance in C++

    Virtual Base Class in C++

    How to Perform Insertion Sort in C++?

    Counting Sort Algorithm: Using C++

    Bucket Sort Algorithm with C++

    Implementing Binary Search in C++

    Print all Permutations of given String: using C++

    Sliding Window Problem – C++ Implementation

    Implement Tower of Hanoi using C++

    Rabin Karp Algorithm: C++ Implementation

    Job Sequencing Problem with C++

    Biconnected Graph Algorithm with C++

    Hamiltonian Path Algorithm with C++

Overview

Bucket sort is a sorting algorithm that is used mainly when the input is distributed uniformly over a range. Foran instance, sorting a collection of floating point numbers uniformly distributed within the range [0.0, 1.0].

We may use any of the various sorting algorithms available such as quick sort, counting sort, insert sort, etc, each of which operates with varying space/time complexities. When, why, and how to use bucket sort, is something that we learn in this article.

Scope

  • Pseudo-code of the bucket-sort algorithm.
  • Explanation and Time complexity for the bucket-sort algorithm.
  • Example with Implementation.

Pseudocode

bucketSort(arr){
    sz = arr.size
    create sz empty buckets
    do following for every arr[i]:
        insert arr[i] into the bucket[n * array[i]]
    sort each bucket individually using the insertion sort
    concatenate all the sorted buckets.
}

Explanation and Time Complexity

Suppose that inserting in a bucket consumes O(1) time. Thus the first 2 steps would consume O(n) time. The O(1) becomes possible if using a linked list for representing a bucket. The 3rd step also takes an average O(n) time, provided all the numbers are distributed uniformly. The final step also consumes O(n) time as the number of items in all the buckets will be n.

Implementation

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

void bucketSort(vector<float>&arr){
    int n = arr.size();
    vector<vector<float>> b(n);
 for (int i = 0; i < n; ++i) {
 b[n * arr[i]].push_back(arr[i]);
 }
 for (auto&bucket : b){
 sort(begin(bucket), end(bucket));
    }
 for (int ind=0, i = 0; i < n; ++i){
 for (int j = 0; j < b[i].size(); ++j){
 arr[ind++] = b[i][j];
        }
    }
}

int main(){
    vector<float>v={ 0.3465, 0.632, 0.667, 0.565, 0.1253, 0.667, 0.888 };
 bucketSort(v);
 cout << "The array after sorting is:"<<endl;
    for(const auto&it:v){
        cout<<it<<' ';
    }
    cout<<endl;
 return 0;
}

Output

The array after sorting is :
0.1253 0.3465 0.565 0.632 0.667 0.667 0.888 

write your code here: Coding Playground