-
Well everyone probably knows that quicksort is quick, and heapsort is even quicker, but did you know radixsort was even quicker than heapsort? Anyway i found this code but it's in java and it's a bit hard to understand. I've just got on my first introduction course on java so i tried but couldn't convert this into vb.
Any Java-gurus that could convert this for me?
Code:
// RadixSort.java version 1.2
// Java Source code for RadixSort
package cmp.RadixSort;
// if using JDK 1.2
// import java.util.Comparator;
/* Copyright (c) 1996-2000
* Roedy Green
* Canadian Mind Products
* #208 - 525 Ninth Street
* New Westminster, BC Canada V3M 5T9
* tel: (604) 777-1804
* mailto:[email protected]
* http://mindprod.com
*/
/*
version 1.1 1998 November 10 - add name and address.
version 1.2 1998 December 28 - use JDK 1.2 style Comparator interface.
version 1.3 2000 September 29 - fix bug. Was not sorting first column
*/
// May be freely distributed for any purpose but military.
// RadixSort beat HeapSort which beat QuickSort.
// RadixSort works in linear time. It is a
// little harder to use than ordinary sorts,
// but it can handle big sorts many times faster.
// Its main weakness is small sorts with long
// keys. The sort is stable. It does not disturb
// pre-existing order of equal keys.
/**
* RadixSort for objects
*/
public class RadixSort
{
private static final String EmbeddedCopyright =
"Copyright 1996-2000 Roedy Green, Canadian Mind Products, http://mindprod.com";
private static final boolean debugging = false;
// callback object we are passed that has
// a getKeyByteAt(Object a, int offset) method.
private RadixComparator delegate;
// pointer to the array of user's objects we are sorting
private Object [] userArray;
// pointer to source work array
private Object [] sourceArray;
// pointer to target work array
private Object [] targetArray;
// how many bytes long the sorting key is.
private int keyLength;
// used to tally how many of each key byte there were.
private int [] counts;
// create a RadixSort object and sort the user's array
public static void sort (
Object [] userArray,
RadixComparator delegate,
int keyLength )
{
RadixSort h = new RadixSort();
h.delegate = delegate;
h.userArray = userArray;
h.keyLength = keyLength;
if ( h.isAlreadySorted() ) return;
h.radixSort();
if ( debugging )
{
// debug ensure sort is working
if ( ! h.isAlreadySorted() ) System.out.println("Sort failed");
}
return;
} // end sort
// radixSort that works like a mechanical card
// sorter, sorting least significant byte of the
// key first. This works in linear time
// proportional to key length and number of items
// sorted.
private void radixSort()
{
counts = new int[256];
sourceArray = userArray;
targetArray = new Object[userArray.length];
// sort least significant column first,
// working back to the most significant.
for ( int col=keyLength-1; col>=0; col-- )
{
sortCol(col);
// swap source and target, very quick, just swapping pointers
Object [] temp = sourceArray;
sourceArray = targetArray;
targetArray = temp;
} // end for
// copy results back to userArray, if necessary
if ( sourceArray != userArray )
{
System.arraycopy(sourceArray,0, userArray,0, sourceArray.length);
}
} // end radixSort
// sort sourceArray by given column. Put results in targetArray
private void sortCol (int col)
{
// pass 1 count how many of each key there are:
for ( int i=0; i<counts.length; i++ )
{
counts[i]=0;
}
for ( int i=0; i<sourceArray.length; i++ )
{
counts[delegate.getKeyByteAt(sourceArray[i],col)]++;
} // end for
// calculate slot number where each item will go.
{
int soFar = 0;
for ( int i=0; i<counts.length; i++ )
{
int temp = counts[i];
counts[i] = soFar;
soFar += temp;
} // end for
} // end block
// pass 2 move each object to its new slot
for ( int from=0; from<sourceArray.length; from++ )
{
int keyByte = delegate.getKeyByteAt(sourceArray[from],col);
int to = counts[keyByte]++;
targetArray[to] = sourceArray[from];
} // end for
} // end sortCol
// check if user's array is already sorted
private boolean isAlreadySorted()
{
for ( int i=1; i<userArray.length; i++ )
{
if ( delegate.compare(userArray[i],userArray[i-1]) < 0 )
return false;
}
return true;
} // end isAlreadySorted
} // end class RadixSort
-
see the sort timer and viewer for VB routines at:
http://pages.about.com/vbmakai/
radix sorts use multi arrays to hold sorted data
as such there is no guarantee it is more stable that a
quick sort
-
Yeah well i thought that I could have use for it anyway, quicksort haven't given me any out of stack spaces yet ;)
Radix wasn't in the list? ALso sorting methods get's effective at certain areas, large keys to sort, or many items or how scrambled the items are.
