ca.pfv.spmf.algorithms.sort

Class Select

java.lang.Object

ca.pfv.spmf.algorithms.sort.Select

public class Select
extends java.lang.Object

Implementation of a few selection algorithms (randomized select, etc.). based on description from the book "Introduction to Algorithms" from MIT Press. Please refer to that book for details about the algorithms and proofs that they are correct.

Constructor Summary

Constructors

Constructor and Description
Select()

Method Summary

Modifier and Type	Method and Description
static int	randomizedSelect(int[] a, int i) Method to select the ith smallest integer of an array in average linear time.

Methods inherited from class java.lang.Object

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

Constructor Detail

Select

public Select()

Method Detail

randomizedSelect

public static int randomizedSelect(int[] a,
                                   int i)

Method to select the ith smallest integer of an array in average linear time. Based on the Randomized-Select algorithm in "Introduction to algorithms" book by Cormen et al. (2001).

Parameters:

a - array of integers

i - the i value

Returns:

the element of "a" that is larger than i elements.