Scribd
Upload
7 views2 pages

Bucket Sort Algorithm Overview

Uploaded by

shadabmalikmedia
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views2 pages

Bucket Sort Algorithm Overview

Uploaded by

shadabmalikmedia
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Bucket Sort

Bucket sort is a comparison sort algorithm that operates on elements by dividing them into
different buckets and then sorting these buckets individually. Each bucket is sorted individually
using a separate sorting algorithm or by applying the bucket sort algorithm recursively. Bucket
sort is mainly useful when the input is uniformly distributed over a range.

bucketSort(a[], n)
1. Create 'n' empty buckets
2. Do for each array element a[i]
2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]]
3. Sort the elements of individual buckets by using the insertion sort.
4. At last, gather or concatenate the sorted buckets.
End bucketSort

Bucket Sort Time Complexity

Case Time Complexity

Best Case O(n + k)

Average Case O(n + k)

Worst Case O(n^2)

• n: Number of elements in the input array.

• k: Number of bucket

Example:-

Step-1
Step-2

Example-2

Performing soring operation in each bucket

You might also like