Algorithm
Development Kit 1.0

algs.model.array
Class Selection

java.lang.Object
  extended by algs.model.array.Selection

public class Selection
extends java.lang.Object

Helper class to locate selected values from an Array of Comparable.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
Selection()
           
 
Method Summary
static java.lang.Comparable max(java.lang.Comparable[] ar)
          Locate the maximum value from an array of Comparables.
static java.lang.Comparable min(java.lang.Comparable[] ar)
          Locate the minimum value from an array of Comparable objects.
static int partition(java.lang.Comparable[] ar, int left, int right, int pivotIndex)
          In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).
static int partition(java.lang.Object[] ar, int left, int right, int pivotIndex, java.util.Comparator comparator)
          In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).
static boolean qsort(java.lang.Comparable[] ar, int left, int right)
          Sort using Quicksort method.
static boolean qsort(java.lang.Object[] ar, int left, int right, java.util.Comparator comparator)
          Sort using Quicksort method.
static java.lang.Comparable select(java.lang.Comparable[] ar, int k, int left, int right)
          Select the kth value in an array (1 ≤ k ≤ right-left+1) through recursive partitioning.
static java.lang.Object select(java.lang.Object[] ar, int k, int left, int right, java.util.Comparator comparator)
          Select the kth value in an array (1 ≤ k ≤ right-left+1) through recursive partitioning.
static int selectPivotIndex(java.lang.Comparable[] ar, int left, int right)
          Select an appropriate pivot within the [left, right] range.
static int selectPivotIndex(java.lang.Object[] ar, int left, int right, java.util.Comparator comparator)
          Select an appropriate pivot within the [left, right] range.
static void swap(java.lang.Object[] ar, int pos1, int pos2)
          Swap the two locations.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Selection

public Selection()
Method Detail

swap

public static void swap(java.lang.Object[] ar,
                        int pos1,
                        int pos2)
Swap the two locations.

Does nothing if pos1 == pos2

Parameters:
ar - An array of objects
pos1 - position of first element to swap
pos2 - position of second element to swap
Throws:
java.lang.NullPointerException - if ar is null
java.lang.ArrayIndexOutOfBoundsException - if either pos1 or pos2 is invalid

min

public static java.lang.Comparable min(java.lang.Comparable[] ar)
Locate the minimum value from an array of Comparable objects.

Parameters:
ar - An array of Comparable objects
Returns:
The minimum element from the array
Throws:
java.lang.NullPointerException - if ar is null
java.lang.ArrayIndexOutOfBoundsException - if ar is an empty array

max

public static java.lang.Comparable max(java.lang.Comparable[] ar)
Locate the maximum value from an array of Comparables.

Parameters:
ar - An array of Comparable objects
Returns:
The maximum element from the array
Throws:
java.lang.NullPointerException - if ar is null or references an empty array.

partition

public static int partition(java.lang.Comparable[] ar,
                            int left,
                            int right,
                            int pivotIndex)
In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).

Parameters:
ar - An array of Comparable objects
left - lower bound index position
right - upper bound index position
pivotIndex - index around which the partition is being made.
Returns:
location of the pivot index properly positioned.

partition

public static int partition(java.lang.Object[] ar,
                            int left,
                            int right,
                            int pivotIndex,
                            java.util.Comparator comparator)
In linear time, group an array into two parts, those less than a certain value (left), and those greater than or equal to a certain value (right).

Parameters:
ar - An array of Comparable objects
left - lower bound index position (0 ≤ left < ar.length)
right - upper bound index position (0 ≤ left < ar.length)
pivotIndex - index around which the partition is being made.
comparator - Externalize the comparison of two objects into this method.
Returns:
location of the pivot index properly positioned.

selectPivotIndex

public static int selectPivotIndex(java.lang.Comparable[] ar,
                                   int left,
                                   int right)
Select an appropriate pivot within the [left, right] range. For now, pick 'middle' of three values [left, mid, right]

Parameters:
ar - Array of Comparable objects
left - The left-bounds within which to search (0 ≤ left < ar.length)
right - The right-bounds within which to search (0 ≤ right < ar.length)
Returns:
index of the pivot within the ar[] array (0 ≤ index < ar.length)

selectPivotIndex

public static int selectPivotIndex(java.lang.Object[] ar,
                                   int left,
                                   int right,
                                   java.util.Comparator comparator)
Select an appropriate pivot within the [left, right] range. For now, pick 'middle' of three values [left, mid, right]

Parameters:
ar - Array of Comparable objects
left - The left-bounds within which to search (0 ≤ left < ar.length)
right - The right-bounds within which to search (0 ≤ right < ar.length)
comparator - Externalize the comparison of two objects into this method.
Returns:
index of the pivot within the ar[] array (0 ≤ index < ar.length)

select

public static java.lang.Comparable select(java.lang.Comparable[] ar,
                                          int k,
                                          int left,
                                          int right)
Select the kth value in an array (1 ≤ k ≤ right-left+1) through recursive partitioning. Note that ar[] is altered during the execution of this method. left must be ≤ right. Built in comparator is used.

Parameters:
ar - Array of Comparable objects
k - The position in sorted order of the desired location (1 ≤ k ≤ right-left+1)
left - The left-bounds within which to search (0 ≤ left < ar.length)
right - The right-bounds within which to search (0 ≤ right < ar.length)
Returns:
The Comparable object which is the kth in sorted order.

select

public static java.lang.Object select(java.lang.Object[] ar,
                                      int k,
                                      int left,
                                      int right,
                                      java.util.Comparator comparator)
Select the kth value in an array (1 ≤ k ≤ right-left+1) through recursive partitioning. Note that ar[] is altered during the execution of this method. left must be ≤ right. Externally provided comparator is used.

Parameters:
ar - Array of objects
k - The position in sorted order of the desired location (1 ≤ k ≤ right-left+1)
left - The left-bounds within which to search (0 ≤ left < ar.length)
right - The right-bounds within which to search (0 ≤ right < ar.length)
comparator - Externalize the comparison of two objects into this method.
Returns:
The Comparable object which is the kth in sorted order.

qsort

public static boolean qsort(java.lang.Comparable[] ar,
                            int left,
                            int right)
Sort using Quicksort method. left must be strictly less than right.

Parameters:
ar - Array of Comparable objects
left - The left-bounds within which to sort (0 ≤ left < ar.length)
right - The right-bounds within which to sort (0 ≤ right < ar.length)
Returns:
false if invalid arguments passed in; true otherwise on success.

qsort

public static boolean qsort(java.lang.Object[] ar,
                            int left,
                            int right,
                            java.util.Comparator comparator)
Sort using Quicksort method. left must be strictly less than right.

Parameters:
ar - Array of Comparable objects
left - The left-bounds within which to sort (0 ≤ left < ar.length)
right - The right-bounds within which to sort (0 ≤ right < ar.length)
comparator - Externalize the comparison of two objects into this method.
Returns:
false if invalid arguments passed in; true otherwise on success.

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.