Page 1 of 10
SQL HTML CSS Javascript Python Java C C++ PHP Scala C#
Bucket Sort Algorithm
The Bucket Sort algorithm is similar to the Counting Sort algorithm, as it is just the generalized form
of the counting sort. Bucket sort assumes that the input elements are drawn from a uniform
distribution over the interval [0, 1).
Hence, the bucket sort algorithm divides the interval [0, 1) into n equal parts, and the input elements
are added to indexed buckets where the indices based on the lower bound of the (n element) value.
Since the algorithm assumes the values as the independent numbers evenly distributed over a small
range, not many elements fall into one bucket only.
For example, let us look at an input list of elements, 0.08, 0.01, 0.19, 0.89, 0.34, 0.07, 0.30, 0.82, 0.39,
0.45, 0.36. The bucket sort would look like −
Powered by:
Page 2 of 10
Bucket Sort Algorithm
Let us look at how this algorithm would proceed further below −
Step 1 − Divide the interval in n equal parts, each part being referred to as a bucket. Say if n is 10, then
there are 10 buckets; otherwise more.
Step 2 − Take the input elements from the input array A and add them to these output buckets B
based on the computation formula, B[i]= ⌊n.A[i]⌋
Step 3 − If there are any elements being added to the already occupied buckets, created a linked list
through the corresponding bucket.
Step 4 − Then we apply insertion sort to sort all the elements in each bucket.
Step 5 − These buckets are concatenated together which in turn is obtained as the output.
Pseudocode
BUCKET-SORT(A)
let B[0 n 1] be a new array
n = [Link]
Powered by:
for i = 0 to n 1
make B[i] an empty list
for i = 1 to n
Page 3 of 10
insert A[i] into list B[$\lfloor$.[]$\rfloor$]
for i = 0 to n 1
sort list B[i] with insertion sort
concatenate the lists B[0], B[1]; ; B[n 1] together in order
Analysis
The bucket sort algorithm assumes the identity of the input, therefore, the average case time
complexity of the algorithm is (n)
Example
Consider, an input list of elements, 0.78, 0.17, 0.93, 0.39, 0.26, 0.72, 0.21, 0.12, 0.33, 0.28, to sort these
elements using bucket sort −
Solution
Step 1
Linearly insert all the elements from the index 0 of the input array. That is, we insert 0.78 first followed
by other elements sequentially. The position to insert the element is obtained using the formula − B[i]=
⌊n.A[i]⌋, i.e, ⌊10 0.78⌋=7
Powered by:
Now, we insert 0.17 at index ⌊10 0.17⌋=1
Page 4 of 10
Step 3
Inserting the next element, 0.93 into the output buckets at ⌊10 0.93⌋=9
Powered by:
Step 4
Insert 0.39 at index 3 using the formula ⌊10 0.39⌋=3
Page 5 of 10
Step 5
Inserting the next element in the input array, 0.26, at position ⌊10 0.26⌋=2
Powered by:
Step 6
Here is where it gets tricky. Now, the next element in the input list is 0.72 which needs to be inserted
at index 7 using the formula ⌊10 0.72⌋=7. But theres already a number in the 7th bucket. So, a link is
Page 6 of 10
created from the 7th index to store the new number like a linked list, as shown below −
Step 7
Add the remaining numbers to the buckets in the similar manner by creating linked lists from the
desired buckets. But while inserting these elements as lists, we apply insertion sort, i.e., compare the
two elements and add the minimum value at the front as shown below −
Powered by:
Page 7 of 10
Step 8
Now, to achieve the output, concatenate all the buckets together.
0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93
Implementation
The implementation of the bucket sort algorithm first retrieves the maximum element of the array and
decides the bucket size of the output. The elements are inserted into these buckets based on few
computations.
In this tutorial, we execute bucket sort in four programming languages.
C C++ Java Python
Open Compiler
#include <iostream>
using namespace std;
void bucketsort(int a[], int n){ // function to implement bucket sort
int max = a[0]; // get the maximum element in the array
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
int b[max], i;
for (int i = 0; i <= max; i++) {
b[i] = 0;
}
for (int i = 0; i < n; i++) {
b[a[i]]++;
Powered by:
}
for (int i = 0, j = 0; i <= max; i++) {
while (b[i] > 0) {
a[j++] = i;
Page 8 of 10
b[i]--;
}
}
}
int main(){
int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
int n = sizeof(a) / sizeof(a[0]); // n is the size of array
cout << "Before sorting array elements are: \n";
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
bucketsort(a, n);
cout << "\nAfter sorting array elements are: \n";
for (int i = 0; i < n; ++i)
cout << a[i] << " ";
}
Output
Before sorting array elements are:
12 45 33 87 56 9 11 7 67
After sorting array elements are:
7 9 11 12 33 45 56 67 87
TOP TUTORIALS
Python Tutorial
Java Tutorial
C++ Tutorial
C Programming Tutorial
C# Tutorial
PHP Tutorial
R Tutorial
HTML Tutorial
CSS Tutorial
Powered by:
JavaScript Tutorial
SQL Tutorial
Page 9 of 10
TRENDING TECHNOLOGIES
Cloud Computing Tutorial
Amazon Web Services Tutorial
Microsoft Azure Tutorial
Git Tutorial
Ethical Hacking Tutorial
Docker Tutorial
Kubernetes Tutorial
DSA Tutorial
Spring Boot Tutorial
SDLC Tutorial
Unix Tutorial
CERTIFICATIONS
Business Analytics Certification
Java & Spring Boot Advanced Certification
Data Science Advanced Certification
Cloud Computing And DevOps
Advanced Certification In Business Analytics
Artificial Intelligence And Machine Learning
DevOps Certification
Game Development Certification
Front-End Developer Certification
AWS Certification Training
Python Programming Certification
COMPILERS & EDITORS
Online Java Compiler
Online Python Compiler
Online Go Compiler
Online C Compiler
Online C++ Compiler
Powered by:
Online C# Compiler
Online PHP Compiler
Online MATLAB Compiler
Online Bash Compiler
Page 10 of 10
Online SQL Compiler
Online Html Editor
ABOUT US | OUR TEAM | CAREERS | JOBS | CONTACT US | TERMS OF USE |
PRIVACY POLICY | REFUND POLICY | COOKIES POLICY | FAQ'S
Tutorials Point is a leading Ed Tech company striving to provide the best learning material on technical
and non-technical subjects.
© Copyright 2025. All Rights Reserved.
Powered by: