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

java.lang.Object
  extended by com.metsci.glimpse.util.primitives.algorithms.GenericSorting

public class GenericSorting
extends java.lang.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
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

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


Copyright © 2012 Metron, Inc.. All Rights Reserved.