com.mhhe.clrs2e
Class DeterministicSelect

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

All Implemented Interfaces:

OrderStatistics

public class DeterministicSelect

extends java.lang.Object

implements OrderStatistics

Implements the OrderStatistics interface via the deterministic Select procedure (which runs in linear time in the worst case) from pages 189-190 of Introduction to Algorithms, Second edition.

Field Summary

private com.mhhe.clrs2e.Partitioner

part For partitioning.

Constructor Summary

DeterministicSelect()
Creates a Partitioner.

Method Summary

private void	insertionSortSubarray(java.lang.Comparable[] array, int start, int size) Sorts a small subarray.
java.lang.Comparable	select(java.lang.Comparable[] array, int i) Returns the ith smallest element in an array.
private java.lang.Comparable	select(java.lang.Comparable[] array, int p, int r, int i) Returns the ith smallest element in a subarray array[p..r].

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.Partitioner part

For partitioning.

Constructor Detail

DeterministicSelect

public DeterministicSelect()

Creates a Partitioner.

Method Detail

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.

select

private java.lang.Comparable select(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.

insertionSortSubarray

private void insertionSortSubarray(java.lang.Comparable[] array,
                                   int start,
                                   int size)

Sorts a small subarray.

Parameters:

array - The array containing the subarray to be sorted.

start - Index of the start of the subarray.

size - Number of elements in the subarray.