Package org.drip.graph.selection

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

java.lang.Object

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

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

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

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

Introselector implements the Introselect Algorithm. The References are:

• 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
• Musser, D. R. (1997): Introselect Sorting and Selection Algorithms Software: Practice and Experience 27 (8) 983-993
• Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect
• Wikipedia (2020): Introselect https://en.wikipedia.org/wiki/Introselect

• 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
Introselector(K[] elementArray, boolean tailCallOptimizationOn, IntroselectControl introselectControl, int groupElementCount)	Introselector Constructor

Method Summary

Modifier and Type	Method	Description
int	groupElementCount()	Retrieve the Group Element Count
K	select(int k)	Perform a Selection for the kth Order Statistic on the Array

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

introselectControl, partition, select, selectIndex, tailCallOptimizationOn

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

Introselector

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

Introselector Constructor

Parameters:

elementArray - Array of Elements

tailCallOptimizationOn - TRUE - Tail Call Optimization is Turned On

introselectControl - The Introselect Control

groupElementCount - Group Element Count

Throws:

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

Method Details

groupElementCount

public int groupElementCount()

Retrieve the Group Element Count

Returns:

The Group Element Count

select

public K select(int k)

Description copied from class: OrderStatisticSelector

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

Overrides:

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

Parameters:

k - The Order Statistic

Returns:

The k^th Order Statistic