Package org.drip.graph.selection

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

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

FloydRivestSelector implements the Floyd-Rivest Selection Algorithm. The References are:

• Floyd, R. W., and R. L. Rivest (1975): Expected Time Bounds for Selection Communications of the ACM 18 (3) 165-172
• Floyd, R. W., and R. L. Rivest (1975): The Algorithm SELECT – for finding the i^th smallest of n Elements Communications of the ACM 18 (3) 173
• Hoare, C. A. R. (1961): Algorithm 65: Find Communications of the ACM 4 (1) 321-322
• Wikipedia (2019): Floyd-Rivest Algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
• Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect

• 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
FloydRivestSelector(K[] elementArray, FloydRivestPartitionControl partitionControl)	FloydRivestSelector Constructor

Method Summary

Modifier and Type	Method	Description
FloydRivestPartitionControl	partitionControl()	Retrieve the Floyd-Rivest Partition Control
int	selectIndex(int leftIndex, int rightIndex, int k)	Select the Index corresponding the kth Order Statistic on the Array

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

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

FloydRivestSelector

public FloydRivestSelector(K[] elementArray,
FloydRivestPartitionControl partitionControl)
                    throws java.lang.Exception

FloydRivestSelector Constructor

Parameters:

elementArray - Array of Elements

partitionControl - Floyd-Rivest Partition Control

Throws:

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

Method Details

partitionControl

public FloydRivestPartitionControl partitionControl()

Retrieve the Floyd-Rivest Partition Control

Returns:

The Floyd-Rivest Partition Control

selectIndex

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

Description copied from class: QuickSelector

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

Overrides:

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

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