Package org.drip.graph.selection

Class MedianOfMediansSelector<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.MedianOfMediansSelector<K>

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

MedianOfMediansSelector implements the QuickSelect Algorithm using the Median-of-Medians Pivot Generation Strategy. The References are:

• Blum, M., R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan (1973): Time Bounds for Selection Journal of Computer and System Sciences 7 (4) 448-461
• Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3^rd Edition MIT Press
• Hoare, C. A. R. (1961): Algorithm 65: Find Communications of the ACM 4 (1) 321-322
• Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect
• Wikipedia (2020): Median Of Medians https://en.wikipedia.org/wiki/Median_of_medians

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

Method Summary

Modifier and Type	Method	Description
int	groupElementCount()	Retrieve the Group Element Count

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

introselectControl, partition, select, 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

MedianOfMediansSelector

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

MedianOfMediansSelector Constructor

Parameters:

elementArray - Array of Elements

tailCallOptimizationOn - TRUE - Tail Call Optimization is Turned On

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