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

All Methods Static Methods Concrete Methods
`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.