Algorithm
Development Kit 1.0

algs.model.array
Class QuickSort

java.lang.Object
  extended by algs.model.array.QuickSort

public class QuickSort
extends java.lang.Object

Provide class to experiment with 'selectPivotIndex' and different minimum size problems for which InsertionSort is used instead.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
QuickSort(java.lang.Comparable[] ar)
           
 
Method Summary
 int partition(int left, int right, int pivotIndex)
          In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).
 void qsort(int left, int right)
          Sort using quicksort method.
 void setMinimumSize(int ms)
          Set the minimum problem size at and below which InsertionSort is used.
 void setPivotMethod(IPivotIndex ipi)
          Determine the method used to select a pivot index.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

QuickSort

public QuickSort(java.lang.Comparable[] ar)
Method Detail

setMinimumSize

public void setMinimumSize(int ms)
Set the minimum problem size at and below which InsertionSort is used.


setPivotMethod

public void setPivotMethod(IPivotIndex ipi)
Determine the method used to select a pivot index.


partition

public int partition(int left,
                     int right,
                     int pivotIndex)
In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).

Parameters:
left - lower bound index position
right - upper bound index position
pivotIndex - index around which the partition is being made.
Returns:
location of the pivot index properly positioned.

qsort

public void qsort(int left,
                  int right)
Sort using quicksort method.

If subarrays to be sorted are smaller in size than 'minSize' then use Insertion Sort as coded in insertion(int, int).

Parameters:
left - The left-bounds within which to sort (0 <= left < ar.length)
right - The right-bounds within which to sort (0 <= right < ar.length)

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.