Loading [MathJax]/jax/output/CommonHTML/jax.js

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 length [A]
  2. for i 1 to n
  3. do insert A[i] into list B[ n A [i] ]
  4. for i 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


Discover more from easytechnotes

Subscribe to get the latest posts sent to your email.

Subscribe
Notify of
guest


0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments