edu.stanford.math.plex4.utility

Class Quicksort.GenericList<T>

java.lang.Object

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

Enclosing class:

Quicksort

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

Constructor Summary

Constructors

Constructor and Description
Quicksort.GenericList()

Method Summary

Methods

Modifier and Type	Method and Description
static <T> int	partition(java.util.List<T> array, int startIndex, int endIndex, java.util.Comparator<T> comparator)
static <T> void	quicksort(java.util.List<T> array, java.util.Comparator<T> comparator)
static <T> void	quicksort(java.util.List<T> array, int startIndex, int endIndex, java.util.Comparator<T> comparator)
static <T> int	randomizedPartition(java.util.List<T> array, int startIndex, int endIndex, java.util.Comparator<T> comparator)
static <T> void	randomizedQuicksort(java.util.List<T> array, java.util.Comparator<T> comparator) This performs the randomized quicksort algorithm in place on the supplied array.
static <T> void	randomizedQuicksort(java.util.List<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(java.util.List<T> array, int i, java.util.Comparator<T> comparator)
static <T> T	randomizedSelect(java.util.List<T> array, int startIndex, int endIndex, int i, java.util.Comparator<T> comparator)

Methods inherited from class java.lang.Object

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

Constructor Detail

Quicksort.GenericList

public Quicksort.GenericList()

Method Detail

quicksort

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

quicksort

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

randomizedQuicksort

public static <T> void randomizedQuicksort(java.util.List<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(java.util.List<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(java.util.List<T> array,
                int startIndex,
                int endIndex,
                java.util.Comparator<T> comparator)

randomizedPartition

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

randomizedSelect

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

randomizedSelect

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