org.ddogleg.sorting

Class CountingSort

java.lang.Object

org.ddogleg.sorting.CountingSort

public class CountingSort
extends java.lang.Object

A O(N) sorting routine for integer valued elements with a known upper and lower bound. This performance can be obtained since it does not compare elements and instead create a histogram.

Constructor Summary

Constructors

Constructor and Description
CountingSort()
CountingSort(int minValue, int maxValue)

Method Summary

Modifier and Type	Method and Description
void	setRange(int minValue, int maxValue) Specify the data range
void	sort(int[] data, int begin, int end) Sorts the data in the array.
void	sort(int[] input, int startIndex, int[] output, int startOutput, int length) Sort routine which does not modify the input array.
void	sortIndex(int[] input, int start, int length, int[] indexes) Sort routine which does not modify the input array and instead maintains a list of indexes.

Methods inherited from class java.lang.Object

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

Constructor Detail

CountingSort

public CountingSort()

CountingSort

public CountingSort(int minValue,
                    int maxValue)

Method Detail

setRange

public void setRange(int minValue,
                     int maxValue)

Specify the data range

Parameters:

minValue - Minimum allowed value. (inclusive)

maxValue - Maximum allowed value. (inclusive)

sort

public void sort(int[] data,
                 int begin,
                 int end)

Sorts the data in the array.

Parameters:

data - Data which is to be sorted. Sorted data is written back into this same array

begin - First element to be sorted (inclusive)

end - Last element to be sorted (exclusive)

sort

public void sort(int[] input,
                 int startIndex,
                 int[] output,
                 int startOutput,
                 int length)

Sort routine which does not modify the input array. Input and output arrays can be the same instance.

Parameters:

input - (Input) Data which is to be sorted. Not modified.

startIndex - First element in input list

output - (Output) Sorted data. Modified.

length - Number of elements

sortIndex

public void sortIndex(int[] input,
                      int start,
                      int length,
                      int[] indexes)

Sort routine which does not modify the input array and instead maintains a list of indexes.

Parameters:

input - (Input) Data which is to be sorted. Not modified.

start - First element in input list

length - Length of the input list

indexes - Number of elements