edu.stanford.math.plex4.utility

Class Quicksort.GenericArray<T>

java.lang.Object

edu.stanford.math.plex4.utility.Quicksort.GenericArray<T>

Enclosing class:

Quicksort

public static class Quicksort.GenericArray<T>
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
Quicksort.GenericArray()

Method Summary

Methods

Modifier and Type	Method and Description
static <T> int	partition(T[] array, int startIndex, int endIndex, java.util.Comparator<T> comparator) The fundamental partition operation for quicksort.
static <T> void	quicksort(T[] array, java.util.Comparator<T> comparator) Performs the quicksort algorithm in place on the supplied array.
static <T> void	quicksort(T[] array, int startIndex, int endIndex, java.util.Comparator<T> comparator) Performs the quicksort algorithm in place on a subarray of the supplied array.
static <T> int	randomizedPartition(T[] array, int startIndex, int endIndex, java.util.Comparator<T> comparator) This function performs the same function as the partition function, except that it uses a randomly chosen pivot.
static <T> void	randomizedQuicksort(T[] array, java.util.Comparator<T> comparator) This performs the randomized quicksort algorithm in place on the supplied array.
static <T> void	randomizedQuicksort(T[] array, int startIndex, int endIndex, java.util.Comparator<T> comparator) This performs the randomized quicksort algorithm in place on a subarray of the supplied array.
static <T> T	randomizedSelect(T[] array, int i, java.util.Comparator<T> comparator) This function returns the i-th order statistic of the data in the supplied array.
static <T> T	randomizedSelect(T[] array, int startIndex, int endIndex, int i, java.util.Comparator<T> comparator) This function performs the randomizedSelect on a subarray of the supplied array.

Methods inherited from class java.lang.Object

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

Constructor Detail

Quicksort.GenericArray

public Quicksort.GenericArray()

Method Detail

quicksort

public static <T> void quicksort(T[] array,
                 java.util.Comparator<T> comparator)

Performs the quicksort algorithm in place on the supplied array.

Parameters:

array - the array to sort

quicksort

public static <T> void quicksort(T[] array,
                 int startIndex,
                 int endIndex,
                 java.util.Comparator<T> comparator)

Performs the quicksort algorithm in place on a subarray of the supplied array.

Parameters:

array - the array to sort

startIndex - the first index of the subarray

endIndex - the last index of the subarray

randomizedQuicksort

public static <T> void randomizedQuicksort(T[] array,
                           java.util.Comparator<T> comparator)

This performs the randomized quicksort algorithm in place on the supplied array. The randomized quicksort algorithm has the advantage that no particular input can force the algorithm to deliver its worst case performance.

Parameters:

array -

randomizedQuicksort

public static <T> void randomizedQuicksort(T[] array,
                           int startIndex,
                           int endIndex,
                           java.util.Comparator<T> comparator)

This performs the randomized quicksort algorithm in place on a subarray of the supplied array. The randomized quicksort algorithm has the advantage that no particular input can force the algorithm to deliver its worst case performance.

Parameters:

array - the array to sort

startIndex - the first index of the subarray

endIndex - the last index of the subarray

partition

public static <T> int partition(T[] array,
                int startIndex,
                int endIndex,
                java.util.Comparator<T> comparator)

The fundamental partition operation for quicksort. This function partitions the array into two parts determined by the pivot element array[startIndex]. It arranges the array so that the first section contains elements less than or equal to each element of the second section. The last index of the first section is returned.

Parameters:

array - the array to arrange

startIndex - the first index of the subarray

endIndex - the last index of the subarray

Returns:

the last index of the first partition

randomizedPartition

public static <T> int randomizedPartition(T[] array,
                          int startIndex,
                          int endIndex,
                          java.util.Comparator<T> comparator)

This function performs the same function as the partition function, except that it uses a randomly chosen pivot.

Parameters:

array - the array to arrange

startIndex - the first index of the subarray

endIndex - the last index of the subarray

Returns:

the last index of the first partition

randomizedSelect

public static <T> T randomizedSelect(T[] array,
                     int i,
                     java.util.Comparator<T> comparator)

This function returns the i-th order statistic of the data in the supplied array. It also modifies the array so that the i-th order statistic is in the i-th position of the array, for j < i array[j] <= array[i], and for j > i array[j] >= array[i]. In other words it partially sorts the array so that it is partitioned into the subset of elements less or equal to the i-th order statistic, and greater than or equal it. If one wanted to find the median of a list of numbers, then one could call randomizedSelect(array, array.length / 2).

Parameters:

array - the array to search

i - the rank of the order statistic to find

Returns:

the i-th order statistic

randomizedSelect

public static <T> T randomizedSelect(T[] array,
                     int startIndex,
                     int endIndex,
                     int i,
                     java.util.Comparator<T> comparator)

This function performs the randomizedSelect on a subarray of the supplied array. It operates on the subarray array[startIndex, ..., endIndex].

Parameters:

array - the array to search

startIndex - the first index of the subarray

endIndex - the last index of the subarray

i - he rank of the order statistic to find

Returns:

the i-th order statistic