Package com.aoindustries.util.sort

Class FastQSort

java.lang.Object

com.aoindustries.util.sort.FastQSort

All Implemented Interfaces:

ComparisonSortAlgorithm<Object>, SortAlgorithm<Object>

public final class FastQSort
extends Object

A quick sort demonstration algorithm SortAlgorithm.java

Version:

\@(#)QSortAlgorithm.java 1.3, 29 Feb 1996 extended with TriMedian and InsertionSort by Denis Ahrens with all the tips from Robert Sedgewick (Algorithms in C++). It uses TriMedian and InsertionSort for lists shorts than 4. <fuhrmann@cs.tu-berlin.de>

Adapted from Denis Ahrens' FastQSortAlgorithm, which was derived from Sun's example QSortAlgorithm.

2003-11-06 - Dan Armstrong - To avoid worst-case scenarios, if the quickSort recursion depth exceeds (int)(10*Math.log(list.size())), the algorithm will quit and a HeapSort will be performed.

Author:

James Gosling, Kevin A. Smith

Method Summary

Modifier and Type	Method	Description
protected static <T> int	compare(List<T> list, int i, int j, Comparator<? super T> comparator, SortStatistics stats)
protected static <T> int	compare(T[] array, int i, int j, Comparator<? super T> comparator, SortStatistics stats)
protected static <T> int	compare(T O1, T O2, Comparator<? super T> comparator, SortStatistics stats)
protected static <T> T	get(List<T> list, int i, SortStatistics stats)
protected static <T> T	get(T[] array, int i, SortStatistics stats)
static FastQSort	getInstance()
boolean	isStable()	Checks if this is a stable sort.
protected static <T> void	set(List<T> list, int i, T O, SortStatistics stats)
protected static <T> void	set(T[] array, int i, T O, SortStatistics stats)
<T extends E> void	sort(List<T> list)
<T extends E> void	sort(List<T> list, SortStatistics stats)
<T extends E> void	sort(List<T> list, Comparator<? super T> comparator)
<T> void	sort(List<T> list, Comparator<? super T> comparator, SortStatistics stats)
<T extends E> void	sort(T[] array)
<T extends E> void	sort(T[] array, SortStatistics stats)
<T extends E> void	sort(T[] array, Comparator<? super T> comparator)
<T> void	sort(T[] array, Comparator<? super T> comparator, SortStatistics stats)
protected static <T> void	swap(List<T> list, int i, int j, SortStatistics stats)
protected static <T> void	swap(T[] array, int i, int j, SortStatistics stats)

Methods inherited from class java.lang.Object

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

Method Detail

getInstance

public static FastQSort getInstance()

isStable

public boolean isStable()

Description copied from interface: SortAlgorithm

Checks if this is a stable sort. A stable sort will keep elements with equal values in their same relative order.

sort

public <T> void sort(List<T> list,
                     Comparator<? super T> comparator,
                     SortStatistics stats)

Specified by:

sort in interface ComparisonSortAlgorithm<Object>

sort

public <T> void sort(T[] array,
                     Comparator<? super T> comparator,
                     SortStatistics stats)

Specified by:

sort in interface ComparisonSortAlgorithm<Object>

sort

public <T extends E> void sort(List<T> list)

Specified by:

sort in interface SortAlgorithm<E>

sort

public <T extends E> void sort(T[] array)

Specified by:

sort in interface SortAlgorithm<E>

sort

public <T extends E> void sort(List<T> list,
                               SortStatistics stats)

Specified by:

sort in interface SortAlgorithm<E>

sort

public <T extends E> void sort(T[] array,
                               SortStatistics stats)

Specified by:

sort in interface SortAlgorithm<E>

sort

public <T extends E> void sort(List<T> list,
                               Comparator<? super T> comparator)

Specified by:

sort in interface ComparisonSortAlgorithm<E>

sort

public <T extends E> void sort(T[] array,
                               Comparator<? super T> comparator)

Specified by:

sort in interface ComparisonSortAlgorithm<E>

compare

protected static <T> int compare(List<T> list,
                                 int i,
                                 int j,
                                 Comparator<? super T> comparator,
                                 SortStatistics stats)

compare

protected static <T> int compare(T[] array,
                                 int i,
                                 int j,
                                 Comparator<? super T> comparator,
                                 SortStatistics stats)

compare

protected static <T> int compare(T O1,
                                 T O2,
                                 Comparator<? super T> comparator,
                                 SortStatistics stats)

get

protected static <T> T get(List<T> list,
                           int i,
                           SortStatistics stats)

get

protected static <T> T get(T[] array,
                           int i,
                           SortStatistics stats)

set

protected static <T> void set(List<T> list,
                              int i,
                              T O,
                              SortStatistics stats)

set

protected static <T> void set(T[] array,
                              int i,
                              T O,
                              SortStatistics stats)

swap

protected static <T> void swap(List<T> list,
                               int i,
                               int j,
                               SortStatistics stats)

swap

protected static <T> void swap(T[] array,
                               int i,
                               int j,
                               SortStatistics stats)