Package com.metsci.glimpse.util.primitives.algorithms

Class GenericSorting

java.lang.Object

com.metsci.glimpse.util.primitives.algorithms.GenericSorting

public class GenericSorting
extends Object

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.

Author:

osborn

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	GenericSorting.Comparator
static class	GenericSorting.Swapper

Method Summary

Modifier and Type	Method	Description
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

mergesort

public 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. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(a, b) must not throw an exception for any indexes a and b in the range).

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.

Parameters:

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).

See Also:

GenericSorting.Comparator, GenericSorting.Swapper

quicksort

public 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. All elements in the range must be mutually comparable by the specified comparator (that is, c.compare(a, b) must not throw an exception for any indexes a and b in the range).

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.

Parameters:

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).

See Also:

GenericSorting.Comparator, GenericSorting.Swapper