com.mhhe.clrs2e
Class Partitioner

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

Direct Known Subclasses:

RandomizedPartitioner

public class Partitioner

extends java.lang.Object

Class for partitioning an array of Comparable objects. Implements the Partition procedure from page 146 of Introduction to Algorithms, Second edition.

Constructor Summary

Partitioner()

Method Summary

void	exchange(java.lang.Object[] array, int i, int j) Exchanges the objects at two positions within an array.
int	partition(java.lang.Comparable[] array, int p, int r) Partitions a subarray around its last element.

Methods inherited from class java.lang.Object

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

Constructor Detail

Partitioner

public Partitioner()

Method Detail

partition

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

Partitions a subarray around its last element.

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.

exchange

public void exchange(java.lang.Object[] array,
                     int i,
                     int j)

Exchanges the objects at two positions within an array.

Parameters:

i - The index of one object.

j - The index of the other object.