org.apache.hadoop.util
Class QuickSort

java.lang.Object
  extended by org.apache.hadoop.util.QuickSort
All Implemented Interfaces:
IndexedSorter

public final class QuickSort
extends Object
implements IndexedSorter

An implementation of the core algorithm of QuickSort.


Constructor Summary
QuickSort()
           
 
Method Summary
protected static int getMaxDepth(int x)
          Deepest recursion before giving up and doing a heapsort.
 void sort(IndexedSortable s, int p, int r)
          Sort the given range of items using quick sort.
 void sort(IndexedSortable s, int p, int r, Progressable rep)
          Same as IndexedSorter.sort(IndexedSortable,int,int), but indicate progress periodically.
 
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

getMaxDepth

protected static int getMaxDepth(int x)
Deepest recursion before giving up and doing a heapsort. Returns 2 * ceil(log(n)).


sort

public void sort(IndexedSortable s,
                 int p,
                 int r)
Sort the given range of items using quick sort. Sort the items accessed through the given IndexedSortable over the given range of logical indices. From the perspective of the sort algorithm, each index between l (inclusive) and r (exclusive) is an addressable entry. If the recursion depth falls below getMaxDepth(int), then switch to HeapSort.

Specified by:
sort in interface IndexedSorter
See Also:
IndexedSortable.compare(int, int), IndexedSortable.swap(int, int)

sort

public void sort(IndexedSortable s,
                 int p,
                 int r,
                 Progressable rep)
Same as IndexedSorter.sort(IndexedSortable,int,int), but indicate progress periodically.

Specified by:
sort in interface IndexedSorter
See Also:
IndexedSorter.sort(IndexedSortable,int,int)


Copyright © 2009 The Apache Software Foundation