com.sas.util
Class Sort

java.lang.Object
  |
  +--com.sas.util.Sort

public class Sort

extends java.lang.Object

Sort algorithms for an Array. There are three implementations; a quick sort, a heap sort, and a merge sort. The quick sort is not stable, can have very good performance, is normally O(n log n), but can be worse than O(n log n). Heap sort is always O(n log n) and can be much better than quick sort on "mostly" sorted data. Heap sort is also a unstable sort. Merge sort is stable and is always O(n log n), but with a higher constant than quick sort or heap sort.

Field Summary

static int	HEAP_SORT Identifier for heap sort.
static int	MERGE_SORT Identifier for a merge sort.
static int	QUICK_SORT Identifier for quick sort.

Constructor Summary

Sort(IndexedSetInterface collection, Comparator comparator)
Create an array sorting object which will sort the array a or regions of that array, based on a comparator.

Sort(IndexedSetInterface collection, Comparator comparator)
Create an array sorting object which will sort the array a or regions of that array, based on a comparator.

Sort(IndexedSetInterface collection, Comparator comparator, int algorithm)
Create an array sorting object which will sort the array a or regions of that array, based on a comparator and a specific sort algorithm.

Sort(IndexedSetInterface collection, Comparator comparator, int algorithm)
Create an array sorting object which will sort the array a or regions of that array, based on a comparator and a specific sort algorithm.

Method Summary

void	sort() Sort all the items in the array using the comparator.
void	sort(int start, int end) Perform a sort of the items from start to end, using the comparator.
void	sort(int start, int end, int[] permutation) Perform a sort of the items from start to end, using the comparator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MERGE_SORT

public static final int MERGE_SORT

Identifier for a merge sort. Merge sort is stable.

QUICK_SORT

public static final int QUICK_SORT

Identifier for quick sort. Quick sort is not stable but usually faster than merge sort.

HEAP_SORT

public static final int HEAP_SORT

Identifier for heap sort. Heap sort is not stable but usually faster than merge sort and better than quicksort when the data is mostly sorted.

Constructor Detail

Sort

public Sort(IndexedSetInterface collection,
            Comparator comparator,
            int algorithm)

Create an array sorting object which will sort the array a or regions of that array, based on a comparator and a specific sort algorithm.

Parameters:

collection - a collection to sort

comparator - the comparator to use to compare items.

algorithm - one of Sort.QUICK_SORT, Sort.MERGE_SORT, or Sort.HEAP_SORT

Throws:

IllegalArgumentException - if algorithm is not recognized.

Sort

public Sort(IndexedSetInterface collection,
            Comparator comparator,
            int algorithm)

Create an array sorting object which will sort the array a or regions of that array, based on a comparator and a specific sort algorithm.

Parameters:

collection - a collection to sort

comparator - the comparator to use to compare items.

algorithm - one of Sort.QUICK_SORT, Sort.MERGE_SORT, or Sort.HEAP_SORT

Throws:

IllegalArgumentException - if algorithm is not recognized.

Sort

public Sort(IndexedSetInterface collection,
            Comparator comparator)

Create an array sorting object which will sort the array a or regions of that array, based on a comparator. The merge sort is used by default because it is a stable sort. Use this as the super constructor from subclasses which define new sort algorithms.

Parameters:

collection - a collection to sort.

comparator - the comparator to use to compare items.

Sort

public Sort(IndexedSetInterface collection,
            Comparator comparator)

Create an array sorting object which will sort the array a or regions of that array, based on a comparator. The merge sort is used by default because it is a stable sort. Use this as the super constructor from subclasses which define new sort algorithms.

Parameters:

collection - a collection to sort.

comparator - the comparator to use to compare items.

Method Detail

sort

public void sort(int start,
                 int end)

Perform a sort of the items from start to end, using the comparator.

Parameters:

start - the index of the first item in the range to sort

end - one past the last item in the range to sort (normally this is a.count()).

sort

public void sort(int start,
                 int end,
                 int[] permutation)

Perform a sort of the items from start to end, using the comparator.

Parameters:

start - the index of the first item in the range to sort

end - one past the last item in the range to sort (normally this is a.length).

permutation - a permutation that lists where each item was moved to in the sorted array. For example, permutation[0] is the index in the result where a.get(0) appears. The caller should initialize permutation array; this sort method only permutes the integers. The permutation array length must be at least (end - 1)

sort

public void sort()

Sort all the items in the array using the comparator. This will sort items [0, count()-1]