Saturday, April 12, 2014

Linear sort for range of numbers in Java

import java.util.BitSet;

/* Sorting numbers on disk
 * Linear sort
 * Inspired from Programming Pearls: Jon Bently
 * Java's ready availability of BitSet's makes
 * all the gory details of bit operations go away,
 * though essential.
 */
public class LinearPerfSort
{
  /* Printing routine */
  public void spill(int a[])
  {
    int indx;
    for (indx = 0 ; indx < a.length; indx++)
    {
      System.out.print(a[indx] + " ");
    }
    System.out.println();
  }
 
  public void doSort(int a[])
  {
    int indx= 0;
    BitSet bs = new BitSet(0);
   
    for (int i = 0; i < a.length; i++)
      bs.set(a[i]);
   
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1))
    {
      // guard on indx i here, just to guard from additional phony bits
      //if (indx < a.length) -- not required.
        a[indx++] = i;
    }
  }
 
  public static void main(String args[])
  {
    int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
   
    LinearPerfSort lps = new LinearPerfSort();
    lps.doSort(arr);
    lps.spill(arr);
  } 
}

No comments:

Post a Comment