# Bucket Sort Algorithm

In this article, we will learn about **Bucket sort with its algorithm and pseudo code**. **Examples of bucket sort** with its analysis are also prescribed in this article.

Submitted by Abhishek Kataria, on July 18, 2018

## Bucket Sort

**Bucket sort** is a sorting technique in which array is partitioned into the buckets. By this, each bucket will be sorted individually, by using some another sorting algorithm such as insertion sort. This sorting technique assumes that the input is drawn from a uniform distribution by which it has an average case of **O(n)**. **Bucket sort** is a fast technique because bucket sort presumes that the input is generated by a process, which will distribute the element uniformly and independently over the interval.

## Algorithm for Bucket Sort

- Set up an array of initially empty buckets.
- Put the element in the corresponding bucket.
- Sort each non-empty bucket.
- Visit the bucket in order and put all the elements into a sequence and print them.

### Pseudo code for Bucket Sort

void bucketsort (int a[ ], int n, int max) { int i,j=0; //initialize each bucket 0 and then make bucket empty. int* buckets = calloc(max+1, size of (int)); for(int i=0; i<n; i++) buckets[a[i]]++; //now sort each bucket individually. //sequentially empty each bucket in some array. for(i=0; i<max; i++) while (buckets[i]--) b[j++]=i; //display the array b as sorted list of elements. }

**Example:**

Let us sort the elements by using bucket sort. Elements which need to be sort are 56, 12, 84, 28, 0,-13, 47, 94, 31, 12.

**Step 1)** First set up an array which is given below:

**Step 2)** Now consider the range such that:

-20 to -1, 0 to 10 10 to 20, 20 to 30, 30 to 40, 40 to 50, 50 to 60, 60 to 70, 70 to 80, 80 to 90, 90 to 100.

Now we fill up each bucket by given elements,

**Step 3)** Now sort the each bucket and then print the array by visiting each bucket sequentially.

-13, 0, 12, 12, 28, 31, 47, 56, 84, 94

This is the sorted list.

### Drawbacks of Bucket Sort

- For the bucket sort, it’s the necessary part that the maximum value of the element must be known.
- In this type of technique, we have to create enough buckets in the memory for every element, to place in the array.

### Analysis of the bucket Sort

Average case, best case, and worst case time complexity of this algorithm is **O(n)**.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions