Package com.github.tommyettinger.ds

Class QuickSelect

java.lang.Object

com.github.tommyettinger.ds.QuickSelect

public final class QuickSelect
extends Object

Implementation of Tony Hoare's quickselect algorithm. Running time is generally O(n), but worst case is O(n^2). Pivot choice is median of three method, providing better performance than a random pivot for partially sorted data. See Wikipedia's Quickselect article for more.
Everything here is public so that it can be adapted for use in other codebases that may also use a select algorithm. Not everything here is documented, so use at your own risk. Note that the k and n parameters are always 1-based; using 0 for k or n is a bad idea.

Method Summary

Modifier and Type	Method	Description
static <T> int	medianOfThreePivot(Arrangeable.ArrangeableList<T> items, Comparator<? super T> comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(BooleanList items, BooleanComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(ByteList items, ByteComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(CharList items, CharComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(DoubleList items, DoubleComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(FloatList items, FloatComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(IntList items, IntComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(LongList items, LongComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static int	medianOfThreePivot(ShortList items, ShortComparator comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static <T> int	medianOfThreePivot(T[] items, Comparator<? super T> comp, int leftIdx, int rightIdx)	Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays
static <T> void	multiSelect(Arrangeable.ArrangeableList<T> items, Comparator<T> comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static <T> void	multiSelect(Arrangeable.ArrangeableList<T> items, Comparator<T> comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(BooleanList items, BooleanComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(BooleanList items, BooleanComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(ByteList items, ByteComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(ByteList items, ByteComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(CharList items, CharComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(CharList items, CharComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(DoubleList items, DoubleComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(DoubleList items, DoubleComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(FloatList items, FloatComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(FloatList items, FloatComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(IntList items, IntComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(IntList items, IntComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(LongList items, LongComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(LongList items, LongComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(ShortList items, ShortComparator comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static void	multiSelect(ShortList items, ShortComparator comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static <T> void	multiSelect(T[] items, Comparator<T> comp, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static <T> void	multiSelect(T[] items, Comparator<T> comp, int left, int right, int n)	Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other.
static <T> int	partition(Arrangeable.ArrangeableList<T> items, Comparator<? super T> comp, int left, int right, int pivot)
static int	partition(BooleanList items, BooleanComparator comp, int left, int right, int pivot)
static int	partition(ByteList items, ByteComparator comp, int left, int right, int pivot)
static int	partition(CharList items, CharComparator comp, int left, int right, int pivot)
static int	partition(DoubleList items, DoubleComparator comp, int left, int right, int pivot)
static int	partition(FloatList items, FloatComparator comp, int left, int right, int pivot)
static int	partition(IntList items, IntComparator comp, int left, int right, int pivot)
static int	partition(LongList items, LongComparator comp, int left, int right, int pivot)
static int	partition(ShortList items, ShortComparator comp, int left, int right, int pivot)
static <T> int	partition(T[] items, Comparator<? super T> comp, int left, int right, int pivot)
static <T> int	recursiveSelect(Arrangeable.ArrangeableList<T> items, Comparator<? super T> comp, int left, int right, int k)
static int	recursiveSelect(BooleanList items, BooleanComparator comp, int left, int right, int k)
static int	recursiveSelect(ByteList items, ByteComparator comp, int left, int right, int k)
static int	recursiveSelect(CharList items, CharComparator comp, int left, int right, int k)
static int	recursiveSelect(DoubleList items, DoubleComparator comp, int left, int right, int k)
static int	recursiveSelect(FloatList items, FloatComparator comp, int left, int right, int k)
static int	recursiveSelect(IntList items, IntComparator comp, int left, int right, int k)
static int	recursiveSelect(LongList items, LongComparator comp, int left, int right, int k)
static int	recursiveSelect(ShortList items, ShortComparator comp, int left, int right, int k)
static <T> int	recursiveSelect(T[] items, Comparator<? super T> comp, int left, int right, int k)
static <T> int	select(Arrangeable.ArrangeableList<T> items, Comparator<? super T> comp, int n, int size)
static int	select(BooleanList items, BooleanComparator comp, int n, int size)
static int	select(ByteList items, ByteComparator comp, int n, int size)
static int	select(CharList items, CharComparator comp, int n, int size)
static int	select(DoubleList items, DoubleComparator comp, int n, int size)
static int	select(FloatList items, FloatComparator comp, int n, int size)
static int	select(IntList items, IntComparator comp, int n, int size)
static int	select(LongList items, LongComparator comp, int n, int size)
static int	select(ShortList items, ShortComparator comp, int n, int size)
static <T> int	select(T[] items, Comparator<? super T> comp, int n, int size)
static <T> void	swap(T[] items, int left, int right)

Methods inherited from class java.lang.Object

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

Method Details

select

public static <T> int select(T[] items,
 Comparator<? super T> comp,
 int n,
 int size)

partition

public static <T> int partition(T[] items,
 Comparator<? super T> comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static <T> int recursiveSelect(T[] items,
 Comparator<? super T> comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static <T> int medianOfThreePivot(T[] items,
 Comparator<? super T> comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

swap

public static <T> void swap(T[] items,
 int left,
 int right)

multiSelect

public static <T> void multiSelect(T[] items,
 Comparator<T> comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Type Parameters:

T - the type of elements of items

Parameters:

items - the T elements to be partially sorted

comp - a Comparator for the T elements

n - the size of the partially-sorted sections to produce

multiSelect

public static <T> void multiSelect(T[] items,
 Comparator<T> comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Type Parameters:

T - the type of elements of items

Parameters:

items - the T elements to be partially sorted

comp - a Comparator for the T elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static <T> int select(Arrangeable.ArrangeableList<T> items,
 Comparator<? super T> comp,
 int n,
 int size)

partition

public static <T> int partition(Arrangeable.ArrangeableList<T> items,
 Comparator<? super T> comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static <T> int recursiveSelect(Arrangeable.ArrangeableList<T> items,
 Comparator<? super T> comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static <T> int medianOfThreePivot(Arrangeable.ArrangeableList<T> items,
 Comparator<? super T> comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static <T> void multiSelect(Arrangeable.ArrangeableList<T> items,
 Comparator<T> comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Type Parameters:

T - the type of elements of items

Parameters:

items - the T elements to be partially sorted

comp - a Comparator for the T elements

n - the size of the partially-sorted sections to produce

multiSelect

public static <T> void multiSelect(Arrangeable.ArrangeableList<T> items,
 Comparator<T> comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Type Parameters:

T - the type of elements of items

Parameters:

items - the T elements to be partially sorted

comp - a Comparator for the T elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(IntList items,
 IntComparator comp,
 int n,
 int size)

partition

public static int partition(IntList items,
 IntComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(IntList items,
 IntComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(IntList items,
 IntComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(IntList items,
 IntComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the int elements to be partially sorted

comp - an IntComparator for the int elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(IntList items,
 IntComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the int elements to be partially sorted

comp - an IntComparator for the int elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(LongList items,
 LongComparator comp,
 int n,
 int size)

partition

public static int partition(LongList items,
 LongComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(LongList items,
 LongComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(LongList items,
 LongComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(LongList items,
 LongComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the long elements to be partially sorted

comp - a LongComparator for the long elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(LongList items,
 LongComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the long elements to be partially sorted

comp - a LongComparator for the long elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(FloatList items,
 FloatComparator comp,
 int n,
 int size)

partition

public static int partition(FloatList items,
 FloatComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(FloatList items,
 FloatComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(FloatList items,
 FloatComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(FloatList items,
 FloatComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the float elements to be partially sorted

comp - a FloatComparator for the long elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(FloatList items,
 FloatComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the float elements to be partially sorted

comp - a FloatComparator for the long elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(DoubleList items,
 DoubleComparator comp,
 int n,
 int size)

partition

public static int partition(DoubleList items,
 DoubleComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(DoubleList items,
 DoubleComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(DoubleList items,
 DoubleComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(DoubleList items,
 DoubleComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the double elements to be partially sorted

comp - a DoubleComparator for the double elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(DoubleList items,
 DoubleComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the double elements to be partially sorted

comp - a DoubleComparator for the double elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(ShortList items,
 ShortComparator comp,
 int n,
 int size)

partition

public static int partition(ShortList items,
 ShortComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(ShortList items,
 ShortComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(ShortList items,
 ShortComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(ShortList items,
 ShortComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the short elements to be partially sorted

comp - a ShortComparator for the short elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(ShortList items,
 ShortComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the short elements to be partially sorted

comp - a ShortComparator for the short elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(ByteList items,
 ByteComparator comp,
 int n,
 int size)

partition

public static int partition(ByteList items,
 ByteComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(ByteList items,
 ByteComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(ByteList items,
 ByteComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(ByteList items,
 ByteComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the byte elements to be partially sorted

comp - a ByteComparator for the byte elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(ByteList items,
 ByteComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the byte elements to be partially sorted

comp - a ByteComparator for the byte elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(CharList items,
 CharComparator comp,
 int n,
 int size)

partition

public static int partition(CharList items,
 CharComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(CharList items,
 CharComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(CharList items,
 CharComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(CharList items,
 CharComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the char elements to be partially sorted

comp - a CharComparator for the char elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(CharList items,
 CharComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the char elements to be partially sorted

comp - a CharComparator for the char elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce

select

public static int select(BooleanList items,
 BooleanComparator comp,
 int n,
 int size)

partition

public static int partition(BooleanList items,
 BooleanComparator comp,
 int left,
 int right,
 int pivot)

recursiveSelect

public static int recursiveSelect(BooleanList items,
 BooleanComparator comp,
 int left,
 int right,
 int k)

medianOfThreePivot

public static int medianOfThreePivot(BooleanList items,
 BooleanComparator comp,
 int leftIdx,
 int rightIdx)

Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays

multiSelect

public static void multiSelect(BooleanList items,
 BooleanComparator comp,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the boolean elements to be partially sorted

comp - a BooleanComparator for the boolean elements

n - the size of the partially-sorted sections to produce

multiSelect

public static void multiSelect(BooleanList items,
 BooleanComparator comp,
 int left,
 int right,
 int n)

Sorts an array so that items come in groups of n unsorted items, with groups sorted between each other. This combines a selection algorithm with a binary divide and conquer approach.

Parameters:

items - the boolean elements to be partially sorted

comp - a BooleanComparator for the boolean elements

left - the lower index (inclusive)

right - the upper index (inclusive)

n - the size of the partially-sorted sections to produce