# Class QuickSelect

java.lang.Object
org.apache.datasketches.common.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 Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Method Details

### 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.