Class SelectionIP

java.lang.Object
  |
  +--SelectionIP

public class SelectionIP

extends java.lang.Object

This class contains methods for implementing the in-place algorithm for selecting the k-th element from an unsorted array.

Field Summary

static int

SEC_SIZE

Constructor Summary

SelectionIP()

Method Summary

static int	findKthInt(int[] els, int left, int right, int k) Finds the value of the element with index 'k' in the sorted subarray (without sorting the array), The method finds the correct value when left <= k <= right.
static int	median5(int[] els, int sInx) Computes the median value of the subarray of fife elements starting from the element with index sInx, performing at most 6 comparisions.
static int	partition(int[] els, int left, int right, int medInx) Partition the subarray starting from left to right, using els[medInx] for pivot: the elements to the left are smaller and the elements to the right are greater or equal to the pivot.
static void	swap(int[] els, int i, int j) Swaps the elemets els[i] and els[j] of the array els.

Methods inherited from class java.lang.Object

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

Field Detail

SEC_SIZE

public static final int SEC_SIZE

Constructor Detail

SelectionIP

public SelectionIP()

Method Detail

findKthInt

public static int findKthInt(int[] els,
                             int left,
                             int right,
                             int k)

Finds the value of the element with index 'k' in the sorted subarray (without sorting the array), The method finds the correct value when left <= k <= right. Destructive; uses an in-place algorithm.

Parameters:

els - the array of int elements

left - the left begin index

right - the right end index

k - the index of the required element in the sorted subarray

Returns:

the absolute index of the element with index 'k' in the sorted subarray[left .. right], which value is els[findKtInPlace(left, right, k).

partition

public static int partition(int[] els,
                            int left,
                            int right,
                            int medInx)

Partition the subarray starting from left to right, using els[medInx] for pivot: the elements to the left are smaller and the elements to the right are greater or equal to the pivot.

Parameters:

left - the begin index

right - the end index

medInx - the index of the pivot

Returns:

the new index of the pivot

swap

public static void swap(int[] els,
                        int i,
                        int j)

Swaps the elemets els[i] and els[j] of the array els.

Parameters:

els - the array

i - the index of the first element

j - the index of the second element

median5

public static int median5(int[] els,
                          int sInx)

Computes the median value of the subarray of fife elements starting from the element with index sInx, performing at most 6 comparisions. After the exectution the median value is stored in els[sInx + 4]. Destructive; uses an in-place algorithm.

Parameters:

sInx - the starting index of the subbaray

Returns:

the median value