Class QuickSort

java.lang.Object
  QuickSort

public class QuickSort
extends java.lang.Object

Nested Class Summary

static class

QuickSort.PivotType This enum specifies the pivot type that QuickSort will use.

Constructor Summary

QuickSort()

Method Summary

static <T extends java.lang.Comparable<? super T>> void	choosePivot(java.util.Vector<T> theVector, int first, int last, QuickSort.PivotType pivotType) This method selects the pivot according to the type of pivot specified.
static <T extends java.lang.Comparable<? super T>> int	partition(java.util.Vector<T> theVector, int first, int last, QuickSort.PivotType pivotType) This method first finds the pivot p by calling choosePivot and then partitions and rearranges the elements of the Vector in the following manner:
static <T extends java.lang.Comparable<? super T>> void	quickSort(java.util.Vector<T> theVector, int first, int last, QuickSort.PivotType pivotType) This is the recursive method that implements the QuickSort algorithm.
static <T extends java.lang.Comparable<? super T>> void	sort(java.util.Vector<T> theVector, QuickSort.PivotType pivotType) This is the method that users will call to sort the specified Vector of Objects of type T using QuickSort.

Methods inherited from class java.lang.Object

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

Constructor Detail

QuickSort

public QuickSort()

Method Detail

sort

public static <T extends java.lang.Comparable<? super T>> void sort(java.util.Vector<T> theVector,
                                                                    QuickSort.PivotType pivotType)

This is the method that users will call to sort the specified Vector of Objects of type T using QuickSort. The method of choosing the pivot is also specified by the user.

This method will call the quickSort method to perform the recursive sort.

The Comparable interface must either be implemented by T or a superclass of T.

When this method is done, the specified Vector is sorted.

Parameters:

theVector - The Vector of Objects of type T to be sorted.

pivotType - The method of choosing the pivot during the QuickSort.

quickSort

public static <T extends java.lang.Comparable<? super T>> void quickSort(java.util.Vector<T> theVector,
                                                                         int first,
                                                                         int last,
                                                                         QuickSort.PivotType pivotType)

This is the recursive method that implements the QuickSort algorithm.

Parameters:

theVector - The Vector of Objects of type T to be sorted.

first - Index of the first entry of the Vector

last - Index of the last entry of the Vector

pivotType - The method of choosing the pivot during the QuickSort.

choosePivot

public static <T extends java.lang.Comparable<? super T>> void choosePivot(java.util.Vector<T> theVector,
                                                                           int first,
                                                                           int last,
                                                                           QuickSort.PivotType pivotType)

This method selects the pivot according to the type of pivot specified.

The chosen pivot will end up as the first element in the specified Vector.

Parameters:

theVector - The Vector of Objects of type T to be sorted.

first - Index of the first entry of the Vector

last - Index of the last entry of the Vector

pivotType - The method of choosing the pivot during the QuickSort.

partition

public static <T extends java.lang.Comparable<? super T>> int partition(java.util.Vector<T> theVector,
                                                                        int first,
                                                                        int last,
                                                                        QuickSort.PivotType pivotType)

This method first finds the pivot p by calling choosePivot and then partitions and rearranges the elements of the Vector in the following manner:

 
                { [ elements < p ] p [ elements >= p] }.
 

Parameters:

theVector - The Vector of Objects of type T to be sorted.

first - Index of the first entry of the Vector

last - Index of the last entry of the Vector

pivotType - The method of choosing the pivot during the QuickSort.

Returns:

The index of the location of the pivot p after the partition.