com.mhhe.clrs2e
Class RadixSort

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

public class RadixSort

extends java.lang.Object

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

Nested Class Summary

private static class

RadixSort.RadixKeyExtractor Interface that allows us to pull out the sort key from an object.

Field Summary

private int	digits How many digits per key.
private int	NO_DIGITS Indicates that the number of digits was not set.
private int	NO_RADIX Indicates that no radix was set.
private int	radix The radix being used.

Constructor Summary

RadixSort()
Initializes the instance variables to default nonsense values.

RadixSort(int radix)
Initializes the radix instance variables to its argument and and digits to a default value.

RadixSort(int radix, int digits)
Initializes the instance variables to its arguments.

Method Summary

private static int	calculateDigits(int radix, int max) Determines how many digits of a given radix are necessary.
void	radixSort(com.mhhe.clrs2e.NonNegativeInteger[] array, int radix) Implements radix sort, calculating the number of digits to sort.
void	radixSort(com.mhhe.clrs2e.NonNegativeInteger[] array, int r, int d) Implements radix sort.
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_RADIX

private final int NO_RADIX

Indicates that no radix was set.

See Also:

Constant Field Values

NO_DIGITS

private final int NO_DIGITS

Indicates that the number of digits was not set.

See Also:

Constant Field Values

radix

private int radix

The radix being used.

digits

private int digits

How many digits per key.

Constructor Detail

RadixSort

public RadixSort()

Initializes the instance variables to default nonsense values.

RadixSort

public RadixSort(int radix)

Initializes the radix instance variables to its argument and and digits to a default value.

Parameters:

radix - Value to use for the radix.

RadixSort

public RadixSort(int radix,
                 int digits)

Initializes the instance variables to its arguments.

Parameters:

radix - Value to use for the radix.

digits - Number of digits to use.

Method Detail

calculateDigits

private static int calculateDigits(int radix,
                                   int max)

Determines how many digits of a given radix are necessary.

Parameters:

radix - The radix.

max - Maximum value of any key.

Returns:

How many digits are necessary.

sort

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

Sorts an array of NonNegativeInteger. Wrapper for radixSort. Calculates the optimal radix if the radix instance variable has not been set.

Parameters:

array - The array of NonNegativeInteger to be sorted.

radixSort

public void radixSort(com.mhhe.clrs2e.NonNegativeInteger[] array,
                      int radix)

Implements radix sort, calculating the number of digits to sort.

Parameters:

array - The array of NonNegativeInteger to be sorted.

radix - The radix to use.

radixSort

public void radixSort(com.mhhe.clrs2e.NonNegativeInteger[] array,
                      int r,
                      int d)

Implements radix sort.

Parameters:

array - The array of NonNegativeInteger to be sorted.

r - The radix to use.

d - The number of digits to use.