jdsl.core.algo.sorts
Class ListQuickSort

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

All Implemented Interfaces:

SortObject

public class ListQuickSort

extends java.lang.Object

implements SortObject

Performs an in-place quicksort in expected O(n log n) time, provided that the first(), last(), after(), and before() methods of the Sequence work in O(1) time. The worst-case running time is O(n-squared). While this sort operates in-place, it requires O(n) extra storage space to cache the rank of each Position. The partition element is deterministically chosen to be the first element of the subsequence being sorted.

Version:

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

Author:

Mark Handy, Benoit Hudson, Keith Schmidt

Constructor Summary

ListQuickSort()

Method Summary

void	sort(Sequence S, Comparator c) Partition the sequence, and recursively sort the two subsequences on either side of the partition element.

Methods inherited from class java.lang.Object

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

Constructor Detail

ListQuickSort

public ListQuickSort()

Method Detail

sort

public void sort(Sequence S,
                 Comparator c)

Partition the sequence, and recursively sort the two subsequences on either side of the partition element.

Specified by:

sort in interface SortObject

Parameters:

S - the (sub)sequence to sort

c - the comparator to use