## org.apache.hadoop.util
Class QuickSort

    java.lang.Object
      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