APIdia Launch Partner
Top Description Fields Constructors Methods
com.badlogic.gdx.utils

public Class QuickSelect<T>

extends Object
Class Inheritance
Imports
java.util.Comparator
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. http://en.wikipedia.org/wiki/Quickselect
Author
Jon Renner

Field Summary

Modifier and TypeField and Description
private T[]
array

private Comparator<? super T>
comp

Constructor Summary

AccessConstructor and Description
public
QuickSelect()

Method Summary

Modifier and TypeMethod and Description
private int
medianOfThreePivot(int leftIdx, int rightIdx)

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

private int
partition(int left, int right, int pivot)

private int
recursiveSelect(int left, int right, int k)

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

private void
swap(int left, int right)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

arrayback to summary
private T[] array
compback to summary
private Comparator<? super T> comp

Constructor Detail

QuickSelectback to summary
public QuickSelect()

Method Detail

medianOfThreePivotback to summary
private int medianOfThreePivot(int leftIdx, int rightIdx)

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

partitionback to summary
private int partition(int left, int right, int pivot)
recursiveSelectback to summary
private int recursiveSelect(int left, int right, int k)
selectback to summary
public int select(T[] items, Comparator<T> comp, int n, int size)
swapback to summary
private void swap(int left, int right)