Bucket Sort in Data Structure

• Bucket Sort runs in linear time on the average.
• Like counting sort , bucket sort is fast because it assume something about the input where as counting sort assumes that the input consists of integers in a small range , bucket sort assume that the input is generated by a random process that distributes elements uniformly over the interval u = {0,1}.

Bucket Sort Algorithm

1. n $\gets$ length [A]
2. for i $\gets$ 1 to n
3. do insert A[i] into list B[$\lfloor$ n A [i] $\rfloor$]
4. for i $\gets$ 0 to n-1
5. do sort list B[i] with insertion sort
6. concatenate the lists B[0], B[1] ………………. B[n-1] together in order.

To sort n input numbers, Bucket Sort

• It partition u into n non-overlapping intervals called bucket.
• Put each input number into its bucket.
• Sort each bucket into a single algorithm like insertion sort.
• Concatenates the sorted lists.

Bucket Sort Example Step By Step

Question: Illustrate the operation of Bucket Sort on the Array

A={0.36,0.15,0.20,0.89,0.53,0.71,0.32}

Now, Sorted Array is