Home Arrays Bucket sort.

# Bucket sort.

0 comment

As similar to Counting Sort, Bucket sort also imposes restrictions on the input to improve the performance. In other words, Bucket sort works well if the input is drawn from fixed set. Bucket sort is the generalization of counting sort. For example, suppose that all the input elements from [0, 1, ……, K-1] , i.e. the set of integers in the interval [0, K-1]. That means, K is the number of elements in the input. Bucket sort uses K counters. The ith counter keeps track of the number of the ith element. Bucket sort with two buckets is effectively a version of Quick sort with two buckets.

Here is a partial code for the bucket sort algorithm

#define BUCKETS 10
void bucketSort(int arr[], int size)
{
int i,j,k;

int buckets[BUCKETS];

for(j = 0;j < BUCKETS;j++)
buckets[j] = 0;

for(i = 0;i < size;i++)
++buckets[arr[i]];

for(i = 0, j = 0;j < BUCKETS; j++)
for(k = buckets[j];k > 0; --k)
arr[i++] = j;
}


Time Complexity:- O(n)
Space Complexity:- O(n)

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More