Package org.apache.datasketches.thetacommon

Class QuickSelect

java.lang.Object

org.apache.datasketches.thetacommon.QuickSelect

public final class QuickSelect
extends Object

QuickSelect algorithm improved from Sedgewick. Gets the kth order value (1-based or 0-based) from the array. Warning! This changes the ordering of elements in the given array!
Also see:
blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html
See QuickSelectTest for examples and testNG tests.

Author:

Lee Rhodes

Method Summary

Modifier and Type	Method	Description
static double	select(double[] arr, int lo, int hi, int pivot)	Gets the 0-based kth order statistic from the array.
static long	select(long[] arr, int lo, int hi, int pivot)	Gets the 0-based kth order statistic from the array.
static double	selectExcludingZeros(double[] arr, int nonZeros, int pivot)	Gets the 1-based kth order statistic from the array excluding any zero values in the array.
static long	selectExcludingZeros(long[] arr, int nonZeros, int pivot)	Gets the 1-based kth order statistic from the array excluding any zero values in the array.
static double	selectIncludingZeros(double[] arr, int pivot)	Gets the 1-based kth order statistic from the array including any zero values in the array.
static long	selectIncludingZeros(long[] arr, int pivot)	Gets the 1-based kth order statistic from the array including any zero values in the array.

Methods inherited from class java.lang.Object

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

Method Detail

select

public static long select(long[] arr,
                          int lo,
                          int hi,
                          int pivot)

Gets the 0-based kth order statistic from the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The array to be re-arranged.

lo - The lowest 0-based index to be considered.

hi - The highest 0-based index to be considered.

pivot - The 0-based index of the value to pivot on.

Returns:

The value of the smallest (n)th element where n is 0-based.

selectIncludingZeros

public static long selectIncludingZeros(long[] arr,
                                        int pivot)

Gets the 1-based kth order statistic from the array including any zero values in the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The hash array.

pivot - The 1-based index of the value that is chosen as the pivot for the array. After the operation all values below this 1-based index will be less than this value and all values above this index will be greater. The 0-based index of the pivot will be pivot-1.

Returns:

The value of the smallest (N)th element including zeros, where N is 1-based.

selectExcludingZeros

public static long selectExcludingZeros(long[] arr,
                                        int nonZeros,
                                        int pivot)

Gets the 1-based kth order statistic from the array excluding any zero values in the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The hash array.

nonZeros - The number of non-zero values in the array.

pivot - The 1-based index of the value that is chosen as the pivot for the array. After the operation all values below this 1-based index will be less than this value and all values above this index will be greater. The 0-based index of the pivot will be pivot+arr.length-nonZeros-1.

Returns:

The value of the smallest (N)th element excluding zeros, where N is 1-based.

select

public static double select(double[] arr,
                            int lo,
                            int hi,
                            int pivot)

Gets the 0-based kth order statistic from the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The array to be re-arranged.

lo - The lowest 0-based index to be considered.

hi - The highest 0-based index to be considered.

pivot - The 0-based smallest value to pivot on.

Returns:

The value of the smallest (n)th element where n is 0-based.

selectIncludingZeros

public static double selectIncludingZeros(double[] arr,
                                          int pivot)

Gets the 1-based kth order statistic from the array including any zero values in the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The hash array.

pivot - The 1-based index of the value that is chosen as the pivot for the array. After the operation all values below this 1-based index will be less than this value and all values above this index will be greater. The 0-based index of the pivot will be pivot-1.

Returns:

The value of the smallest (N)th element including zeros, where N is 1-based.

selectExcludingZeros

public static double selectExcludingZeros(double[] arr,
                                          int nonZeros,
                                          int pivot)

Gets the 1-based kth order statistic from the array excluding any zero values in the array. Warning! This changes the ordering of elements in the given array!

Parameters:

arr - The hash array.

nonZeros - The number of non-zero values in the array.

pivot - The 1-based index of the value that is chosen as the pivot for the array. After the operation all values below this 1-based index will be less than this value and all values above this index will be greater. The 0-based index of the pivot will be pivot+arr.length-nonZeros-1.

Returns:

The value of the smallest (N)th element excluding zeros, where N is 1-based.