com.mhhe.clrs2e
Class RandomizedPartitioner

java.lang.Object
  |
  +--com.mhhe.clrs2e.Partitioner
        |
        +--com.mhhe.clrs2e.RandomizedPartitioner

public class RandomizedPartitioner

extends Partitioner

Class for doing random partitioning on an array of Comparable objects. Implements the Randomized-Partition procedure from page 154 of Introduction to Algorithms, Second edition.

Field Summary

private java.util.Random

generator A random-number generator.

Constructor Summary

RandomizedPartitioner()
Makes a new generator.

RandomizedPartitioner(java.util.Random generator)
Saves the generator it is given into the instance variable.

Method Summary

int	partition(java.lang.Comparable[] array, int p, int r) Partitions a subarray around a randomly chosen element in the subarray.

Methods inherited from class com.mhhe.clrs2e.Partitioner

exchange

Methods inherited from class java.lang.Object

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

Field Detail

generator

private java.util.Random generator

A random-number generator.

Constructor Detail

RandomizedPartitioner

public RandomizedPartitioner()

Makes a new generator.

RandomizedPartitioner

public RandomizedPartitioner(java.util.Random generator)

Saves the generator it is given into the instance variable.

Method Detail

partition

public int partition(java.lang.Comparable[] array,
                     int p,
                     int r)

Partitions a subarray around a randomly chosen element in the subarray.

Overrides:

partition in class Partitioner

Parameters:

array - The array containing the subarray to be partitioned.

p - Index of the beginning of the subarray.

r - Index of the end of the subarray.

Returns:

An index, say q, such that

• array[q] = the original item in array[r]
• array[p..q-1] <= array[q], and
• array[q+1..r] > array[q].

Works in place.