com.mhhe.clrs2e
Class CountingSort

java.lang.Object
  |
  +--com.mhhe.clrs2e.CountingSort

public class CountingSort

extends java.lang.Object

Sorts an array of NonNegativeInteger via the counting sort algorithm from page 168 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class	CountingSort.CountingSortKeyExtractor Inner class implementing KeyExtractor, in which each extract method just returns its argument.
static interface	CountingSort.KeyExtractor Interface that allows us to pull out the sort key from an object.

Field Summary

private CountingSort.KeyExtractor	extractor Used to generate the actual key.
private int	max Maximum value in the array.
private int	NO_MAX Indicates that no maximum was set.

Constructor Summary

CountingSort()
Initializes max and extractor to defaults.

CountingSort(CountingSort.KeyExtractor extractor)
Initializes max to the default and extractor to its argument.

CountingSort(CountingSort.KeyExtractor extractor, int max)
Initializes max and extractor to its arguments.

CountingSort(int max)
Initializes max to its argument and extractor to the default.

Method Summary

void	countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array) Sorts an array of NonNegativeInteger.
void	countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array, int k) Sorts an array of NonNegativeInteger, given the maximum value in the array.
void	countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array, com.mhhe.clrs2e.NonNegativeInteger[] sorted, int k) Sorts an array of NonNegativeInteger, given the maximum value in the array and array to sort into.
int	findMax(com.mhhe.clrs2e.NonNegativeInteger[] array) Returns the maximum value in an array of NonNegativeInteger.
void	setExtractor(CountingSort.KeyExtractor extractor) Changes the extractor to its argument.
void	setMax(int max) Changes the maximum to its argument.
void	sort(com.mhhe.clrs2e.NonNegativeInteger[] array) Sorts an array of NonNegativeInteger.

Methods inherited from class java.lang.Object

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

Field Detail

NO_MAX

private final int NO_MAX

Indicates that no maximum was set.

See Also:

Constant Field Values

max

private int max

Maximum value in the array.

extractor

private CountingSort.KeyExtractor extractor

Used to generate the actual key.

Constructor Detail

CountingSort

public CountingSort()

Initializes max and extractor to defaults.

CountingSort

public CountingSort(CountingSort.KeyExtractor extractor)

Initializes max to the default and extractor to its argument.

Parameters:

extractor - The KeyExtractor to use.

CountingSort

public CountingSort(int max)

Initializes max to its argument and extractor to the default.

Parameters:

max - Value of max to use.

CountingSort

public CountingSort(CountingSort.KeyExtractor extractor,
                    int max)

Initializes max and extractor to its arguments.

Parameters:

max - Value of max to use.

extractor - The KeyExtractor to use.

Method Detail

setExtractor

public void setExtractor(CountingSort.KeyExtractor extractor)

Changes the extractor to its argument.

Parameters:

extractor - The new KeyExtractor to use.

setMax

public void setMax(int max)

Changes the maximum to its argument.

Parameters:

max - The new value of max to use.

findMax

public int findMax(com.mhhe.clrs2e.NonNegativeInteger[] array)

Returns the maximum value in an array of NonNegativeInteger.

Parameters:

array - The array of NonNegativeInteger.

sort

public void sort(com.mhhe.clrs2e.NonNegativeInteger[] array)

Sorts an array of NonNegativeInteger.

Parameters:

array - The array of NonNegativeInteger to be sorted.

countingSort

public void countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array)

Sorts an array of NonNegativeInteger. If max has not been set, calculates it by finding the maximum value in the array in a preprocessing step.

Parameters:

array - The array of NonNegativeInteger to be sorted.

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array to be sorted contains a negative value or a value greater than the presumed maximum value.

countingSort

public void countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array,
                         int k)

Sorts an array of NonNegativeInteger, given the maximum value in the array.

Parameters:

array - The array of NonNegativeInteger to be sorted.

k - Maximum value in the array.

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array to be sorted contains a negative value or a value greater than the presumed maximum value.

countingSort

public void countingSort(com.mhhe.clrs2e.NonNegativeInteger[] array,
                         com.mhhe.clrs2e.NonNegativeInteger[] sorted,
                         int k)

Sorts an array of NonNegativeInteger, given the maximum value in the array and array to sort into.

Parameters:

array - The array of NonNegativeInteger to be sorted.

sorted - Output array; corresponds to the output array B in the pseudocode on page 168 and contains a sorted version of array.

k - Maximum value in the array.

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array to be sorted contains a negative value or a value greater than the presumed maximum value.