stresstests.algorithms
Class AListSortQuickSort<T>

java.lang.Object
  extended by stresstests.algorithms.ASortAlgo<T>
      extended by stresstests.algorithms.AListSortQuickSort<T>

public class AListSortQuickSort<T>
extends ASortAlgo<T>

AListSortQuickSort 22 March 2007 A class to implement quicksort in a functional style with input and the result stored as recursively defined list

Author:
Viera K. Proulx

Field Summary
 Traversal<T> tr
          the Traversal that supplies the data to sort
 
Fields inherited from class stresstests.algorithms.ASortAlgo
algoName, comp
 
Constructor Summary
AListSortQuickSort(java.util.Comparator<T> comp)
           
AListSortQuickSort(java.util.Comparator<T> comp, Traversal<T> tr)
           
 
Method Summary
private  AList<T> append(Traversal<T> lowerTr, T pivot, AList<T> upper)
          Append two lists with the pivot in the middle
private  AList<T> appendLists(AList<T> lower, T pivot, AList<T> upper)
          Wrapper to append two lists with the pivot in the middle: invokes the real method by converting the first AList to a Traversal
 void initData(Traversal<T> tr)
          Initialize the internal data set with the data generated by the Traversal
private  AList<T> lower(Traversal<T> source, T pivot)
          Produce the lower partition - where all data <= pivot
static void main(java.lang.String[] argv)
           
 AList<T> quickSort(AList<T> source)
          A wrapper for a quicksort for a recursively defined list: it invokes the actual algorithm with the input converted to a Traversal
 AList<T> quickSort(Traversal<T> tr)
          Quicksort for a recursively defined list
 Traversal<T> sort()
          wrapper for the sort method
 void testAListSortQuick()
          The tests for AListSortQuick
private  AList<T> upper(Traversal<T> source, T pivot)
          Produce the upper partition - where all data > pivot
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

tr

public Traversal<T> tr
the Traversal that supplies the data to sort

Constructor Detail

AListSortQuickSort

public AListSortQuickSort(java.util.Comparator<T> comp,
                          Traversal<T> tr)

AListSortQuickSort

public AListSortQuickSort(java.util.Comparator<T> comp)
Method Detail

initData

public void initData(Traversal<T> tr)
Initialize the internal data set with the data generated by the Traversal

Specified by:
initData in class ASortAlgo<T>
Parameters:
tr - the Traversal that provides the data to sort

sort

public Traversal<T> sort()
wrapper for the sort method

Specified by:
sort in class ASortAlgo<T>
Returns:
a Traversal for the sorted data

quickSort

public AList<T> quickSort(AList<T> source)

A wrapper for a quicksort for a recursively defined list: it invokes the actual algorithm with the input converted to a Traversal

Parameters:
source - the AList to be sorted return the sorted AList

quickSort

public AList<T> quickSort(Traversal<T> tr)

Quicksort for a recursively defined list

Parameters:
tr - the Traversal that generates the data to be sorted return the sorted AList

lower

private AList<T> lower(Traversal<T> source,
                       T pivot)
Produce the lower partition - where all data <= pivot

Parameters:
source - the Traversal that generates the data to be partitioned
pivot - the pivot that determines which data items to choose return an AList that contains all data <= pivot

upper

private AList<T> upper(Traversal<T> source,
                       T pivot)
Produce the upper partition - where all data > pivot

Parameters:
source - the Traversal that generates the data to be partitioned
pivot - the pivot that determines which data items to choose return an AList that contains all data > pivot

appendLists

private AList<T> appendLists(AList<T> lower,
                             T pivot,
                             AList<T> upper)
Wrapper to append two lists with the pivot in the middle: invokes the real method by converting the first AList to a Traversal

Parameters:
lower - the AList for the lower partition
pivot - the pivot to insert in the middle
upper - the AList for the upper partition return the sorted list

append

private AList<T> append(Traversal<T> lowerTr,
                        T pivot,
                        AList<T> upper)
Append two lists with the pivot in the middle

Parameters:
lowerTr - the traversal for the lower partition
pivot - the pivot to insert in the middle
upper - the AList for the upper partition return the sorted list

testAListSortQuick

public void testAListSortQuick()
The tests for AListSortQuick


main

public static void main(java.lang.String[] argv)