com.mhhe.clrs2e
Class RandomizedSelect

java.lang.Object
  |
  +--com.mhhe.clrs2e.RandomizedSelect

All Implemented Interfaces:

OrderStatistics

public class RandomizedSelect

extends java.lang.Object

implements OrderStatistics

Implements the OrderStatistics interface via the Randomized-Select procedure (which runs in linear expected time) from page 186 of Introduction to Algorithms, Second edition.

Field Summary

private com.mhhe.clrs2e.RandomizedPartitioner

part For partitioning.

Constructor Summary

RandomizedSelect()
Sets the partitioner to be a randomized one.

Method Summary

private java.lang.Comparable	randomizedSelect(java.lang.Comparable[] array, int p, int r, int i) Returns the ith smallest element in a subarray array[p..r].
java.lang.Comparable	select(java.lang.Comparable[] array, int i) Returns the ith smallest element in an array.

Methods inherited from class java.lang.Object

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

Field Detail

part

private com.mhhe.clrs2e.RandomizedPartitioner part

For partitioning.

Constructor Detail

RandomizedSelect

public RandomizedSelect()

Sets the partitioner to be a randomized one.

Method Detail

randomizedSelect

private java.lang.Comparable randomizedSelect(java.lang.Comparable[] array,
                                              int p,
                                              int r,
                                              int i)

Returns the ith smallest element in a subarray array[p..r].

Parameters:

array - The array containing the subarray to be sorted.

p - Index of the beginning of the subarray.

r - Index of the end of the subarray.

i - Which order statistic we want.

select

public java.lang.Comparable select(java.lang.Comparable[] array,
                                   int i)

Returns the ith smallest element in an array.

Specified by:

select in interface OrderStatistics

Parameters:

array - The array.

i - Which order statistic we want.