|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.metsci.glimpse.util.primitives.algorithms.GenericSorting
public class GenericSorting
QuickSort and MergeSort with free-form Comparator and Swapper classes allowing parallel arrays to be sorted simultaneously. The basic algorithms are taken from Parallel Colt. Only a handful of modest modifications and additions have been undertaken on the original.
Nested Class Summary | |
---|---|
static interface |
GenericSorting.Comparator
|
static class |
GenericSorting.Swapper
|
Method Summary | |
---|---|
static void |
mergesort(int fromIndex,
int toIndex,
GenericSorting.Comparator c,
GenericSorting.Swapper s)
Sorts the specified range of elements according to the order induced by the specified comparator. |
static void |
quicksort(int fromIndex,
int toIndex,
GenericSorting.Comparator c,
GenericSorting.Swapper s)
Sorts the specified range of elements according to the order induced by the specified comparator. |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Method Detail |
---|
public static void mergesort(int fromIndex, int toIndex, GenericSorting.Comparator c, GenericSorting.Swapper s)
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.
fromIndex
- the index of the first element (inclusive) to be sorted.toIndex
- the index of the last element (exclusive) to be sorted.c
- the comparator to determine the order of the generic data.s
- an object that knows how to swap the elements at any two
indexes (a,b).GenericSorting.Comparator
,
GenericSorting.Swapper
public static void quicksort(int fromIndex, int toIndex, GenericSorting.Comparator c, GenericSorting.Swapper s)
The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.
fromIndex
- the index of the first element (inclusive) to be sorted.toIndex
- the index of the last element (exclusive) to be sorted.c
- the comparator to determine the order of the generic data.s
- an object that knows how to swap the elements at any two
indexes (a,b).GenericSorting.Comparator
,
GenericSorting.Swapper
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |