net.sf.jsort.sort
Class QuickSort

java.lang.Object
  net.sf.jsort.sort.AbstractSort
      net.sf.jsort.sort.QuickSort

All Implemented Interfaces:

CompareSort, SortAlgorithm

Direct Known Subclasses:

RandomizedQuickSort

public class QuickSort
extends AbstractSort

This is a implementation of QuickSort algorithm.

The algorithm follows the idea of divide and conquer, so it has a recursive approach. The recursion is over the quicksort method, which call the partition method. The method partition starts with a pivot and reorganize the original array such that 2 others arrays appers: the first one contains elements less that pivot, and the second one contains elements greater than pivot.

This reorganization is done recursively for the first and second piece. Check method partion about the influence of the input over the complexity.

Author:

Domingos Creado

See Also:

http://en.wikipedia.org/wiki/Quicksort

Constructor Summary

QuickSort()

Method Summary

protected int	partition(java.lang.Object[] list, java.util.Comparator comparator, int start, int end) It method is the main part of the algorithm.
void	sort(java.lang.Object[] list, java.util.Comparator comparator, int start, int end) Sort a specific range of the list, using the specified comparator.

Methods inherited from class net.sf.jsort.sort.AbstractSort

sort, sort, sort, sort, sort, sort, sort

Methods inherited from class java.lang.Object

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

Constructor Detail

QuickSort

public QuickSort()

Method Detail

sort

public void sort(java.lang.Object[] list,
                 java.util.Comparator comparator,
                 int start,
                 int end)

Description copied from interface: CompareSort

Sort a specific range of the list, using the specified comparator.

Specified by:

sort in interface CompareSort

Specified by:

sort in class AbstractSort

Parameters:

list - to be sort

partition

protected int partition(java.lang.Object[] list,
                        java.util.Comparator comparator,
                        int start,
                        int end)

It method is the main part of the algorithm. It starts with the definition of the pivot (the last element of the list) and comparing all elements with the pivot, it creates 2 segments, those elements less than and greater than. The counter i keep track of the position of the last position of a less than pivot element.

The overal complexity of the algorithm depends on the split of the original array in 2. But this depend on the "selectivity" of the pivot been used, if the pivot splits the array in some proportion (in fact any proportion) the average complexity O(n * ln(n)) is garanteed.

For the sake of the stability, this implementation select the pivot at the end of the list. Using this approach the worst case is when the array is already selected, this will lead the pivot to split the original array in an array with n-1 elements and 1 element (itself), which will make n comparison with n elements, or O(n ^ 2).

Parameters:

list - the elements to be ordered

comparator - the element that define what is "greater than" semantics

start - first position of the list to be included in sorting

end - last position of the list to be included in sorting

Returns:

the position of the pivot