Package org.drip.graph.selection

Class QuickSelector<K extends java.lang.Comparable<K>>

java.lang.Object

org.drip.graph.selection.OrderStatisticSelector<K>

org.drip.graph.selection.QuickSelector<K>

Direct Known Subclasses:

FloydRivestSelector, Introselector, MedianOfMediansSelector

public class QuickSelector<K extends java.lang.Comparable<K>>
extends OrderStatisticSelector<K>

QuickSelector implements the Hoare's QuickSelect Algorithm. The References are:

• Eppstein, D. (2007): Blum-style Analysis of Quickselect https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html
• Hoare, C. A. R. (1961): Algorithm 65: Find Communications of the ACM 4 (1) 321-322
• Knuth, D. (1997): The Art of Computer Programming 3^rd Edition Addison-Wesley
• Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect
• Wikipedia (2019): Selection Algorithm https://en.wikipedia.org/wiki/Selection_algorithm

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = k^th Order Statistics Selection Scheme

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
QuickSelector(K[] elementArray, boolean tailCallOptimizationOn, IntroselectControl introselectControl)	QuickSelector Constructor

Method Summary

Modifier and Type	Method	Description
IntroselectControl	introselectControl()	Retrieve the Introselect Control
int	partition(int leftIndex, int rightIndex, int pivotIndex)	Partition the Array into Elements Lower and Higher than the Pivot Value inside of the Index Range
K	select(int k)	Perform a Selection for the kth Order Statistic on the Array
K	select(int leftIndex, int rightIndex, int k)	Perform a Selection for the kth Order Statistic on the Array
int	selectIndex(int leftIndex, int rightIndex, int k)	Select the Index corresponding the kth Order Statistic on the Array
boolean	tailCallOptimizationOn()	Retrieve the Tail Call Optimization Status

Methods inherited from class org.drip.graph.selection.OrderStatisticSelector

elementArray, inPlace, sort

Methods inherited from class java.lang.Object

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

Constructor Details

QuickSelector

public QuickSelector(K[] elementArray,
boolean tailCallOptimizationOn,
IntroselectControl introselectControl)
              throws java.lang.Exception

QuickSelector Constructor

Parameters:

elementArray - Array of Elements

tailCallOptimizationOn - TRUE - Tail Call Optimization is Turned On

introselectControl - The Introselect Control

Throws:

java.lang.Exception - Thrown if the Input is Invalid

Method Details

tailCallOptimizationOn

public boolean tailCallOptimizationOn()

Retrieve the Tail Call Optimization Status

Returns:

TRUE - Tail Call Optimization is Turned On

introselectControl

public IntroselectControl introselectControl()

Retrieve the Introselect Control

Returns:

The Introselect Control

partition

public int partition(int leftIndex,
int rightIndex,
int pivotIndex)
              throws java.lang.Exception

Partition the Array into Elements Lower and Higher than the Pivot Value inside of the Index Range

Parameters:

leftIndex - Range Left Index

rightIndex - Range Right Index

pivotIndex - Pivot Index

Returns:

The Index corresponding to the Partitioned Array

Throws:

java.lang.Exception - Thrown if the Partition cannot be computed

selectIndex

public int selectIndex(int leftIndex,
int rightIndex,
int k)
                throws java.lang.Exception

Select the Index corresponding the k^th Order Statistic on the Array

Parameters:

leftIndex - Range Left Index

rightIndex - Range Right Index

k - The Order Statistic

Returns:

Index corresponding the k^th Order Statistic

Throws:

java.lang.Exception - Thrown if the Index cannot be Selected

select

public K select(int leftIndex,
int rightIndex,
int k)
         throws java.lang.Exception

Perform a Selection for the k^th Order Statistic on the Array

Parameters:

leftIndex - Range Left Index

rightIndex - Range Right Index

k - The Order Statistic

Returns:

The k^th Order Statistic

Throws:

java.lang.Exception - Thrown if the Selection cannot be performed

select

public K select(int k)

Description copied from class: OrderStatisticSelector

Perform a Selection for the k^th Order Statistic on the Array

Specified by:

select in class OrderStatisticSelector<K extends java.lang.Comparable<K>>

Parameters:

k - The Order Statistic

Returns:

The k^th Order Statistic