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);
}
}
/* 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