Bin Sort

Assume that

1. the keys of the items that we wish to sort lie in a small fixed range and
2. that there is only one item with each value of the key.

Then we can sort with the following procedure:

1. Set up an array of "bins" - one for each value of the key - in order,
2. Examine each item and use the value of the key to place it in the appropriate bin.

Now our collection is sorted and it only took n operations, so this is an O(n) operation. However, note that it will only work under very restricted conditions.

Constraints on bin sort

To understand these restrictions, let's be a little more precise about the specification of the problem and assume that there are m values of the key. To recover our sorted collection, we need to examine each bin. This adds a third step to the algorithm above,

3. Examine each bin to see whether there's an item in it.

which requires m operations. So the algorithm's time becomes:
T(n) = c₁n + c₂m and it is strictly O(n + m). Now if m <= n, this is clearly O(n). However if m >> n, then it is O(m).

Procedure  Bin_Sort(int a[], int bin[], int n)

1.  for i=0 to M do     where M is  0<= a[i]  < M

2.  bin[i] = -1;

3.end for

4.for i=0 to n do

5.bin[a[i]]=a[i];

6.end for 

If there are duplicates, then each bin can be replaced by a linked list. The third step then becomes:

3. Link all the lists into one list.

Having highlighted this constraint, there is a version of bin sort which can sort in place:

Procedure  Bin_Sort(int a[], int n)

1.for i=0 to n do

2.      if ( a[i] != i )

3.        SWAP( a[i], a[a[i]] );

4. end if

5. end for

However, this assumes that there are n distinct keys in the range 0 .. n-1. In addition to this restriction, the SWAP operation is relatively expensive, so that this version trades space for time.

Implementation 

Browse More Articles

Tweet

Written by sutha

We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.