Bucket sort (bin sort) is categorized into linear time sorting algorithms. In bucket sort, no comparisons needed between elements. But it depends on assumption about the numbers being sorted. 

Bucket sort takes input as n real numbers in the range of 0 and 1. Basic idea of bucket sort is that it create n linked lists (buckets) to divide interval [0,1) into subintervals of size 1/n. Then it adds each input element to appropriate bucket and sort buckets with insertion sort. Uniform input distribution is O(1) bucket size. Therefore the expected total time is O(n).

Bucket Sort Algorithm

BucketSort( array A, int n, int M) {
  // Pre-condition: for 1 <= i <= n, 0 <= A[i] < M
  // Mark all the bins empty
  for i = 1 to M {
    bin[i]  = Empty
  for i  = 1 to n {
    bin[A[i]] = A[i]

Example of Bucket Sort

Step 1

Step 2

and Finally,

Tagged with: C/C++ language

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.