Class 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:
See QuickSelectTest for examples and testNG tests.
Author:
Lee Rhodes
• Method Summary

All Methods
Modifier and Type Method and 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.
• 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.