jdsl.core.algo.sorts
Class ArrayQuickSort

java.lang.Object
  |
  +--jdsl.core.algo.sorts.ArrayQuickSort

All Implemented Interfaces:

SortObject

public class ArrayQuickSort

extends java.lang.Object

implements SortObject

Performs an in-place quicksort in expected O(n log n) time, provided that the atRank(int) method of the Sequence operates in O(1) time. The worst-case sort time is O(n-squared). The partition element is deterministically chosen to be the first element of the subsequence being sorted.

Version:

$Id: ArrayQuickSort.java,v 1.4 2000/01/12 03:21:21 mdh Exp $

Author:

Mark Handy, Benoit Hudson, Keith Schmidt

Constructor Summary

ArrayQuickSort()

Method Summary

void	sort(Sequence S, Comparator c) Method that actually sorts the sequence, with the first element after the sort being the one that the comparator reported was smallest.

Methods inherited from class java.lang.Object

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

Constructor Detail

ArrayQuickSort

public ArrayQuickSort()

Method Detail

sort

public void sort(Sequence S,
                 Comparator c)

Description copied from interface: SortObject

Method that actually sorts the sequence, with the first element after the sort being the one that the comparator reported was smallest.

Specified by:

sort in interface SortObject

Following copied from interface: jdsl.core.algo.sorts.SortObject

Parameters:

s - sequence to be sorted

c - comparator which defines in which order S is sorted