Package org.ddogleg.sorting

Class QuickSelect

java.lang.Object
org.ddogleg.sorting.QuickSelect
public class QuickSelect extends Object

QuickSelect searches for the k-th largest item in the list. While doing this search it will sort the list partially. all the items below k will have a value less than it and all the items more than k will have a value greater than it. However the values above and below can be unsorted. QuickSelect is faster than QuickSort of you don't need a fully sorted list.

An implementation of the quick select algorithm from Numerical Recipes Third Edition that is specified for arrays of doubles. See page 433.

DO NOT MODIFY. AUTOGENERATED CODE. GenerateQuickSelect

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuickSelect()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static byte
    select(byte[] data, int k, int maxIndex)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static double
    select(double[] data, int k, int size)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static double
    select(double[] data, int k, int idx0, int idx1)
     
    static float
    select(float[] data, int k, int size)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static float
    select(float[] data, int k, int idx0, int idx1)
     
    static int
    select(int[] data, int k, int maxIndex)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static long
    select(long[] data, int k, int maxIndex)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static short
    select(short[] data, int k, int maxIndex)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static <T extends Comparable<T>>
    T
    select(T[] data, int k, int idx1)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static <T extends Comparable<T>>
    T
    select(T[] data, int k, int idx0, int idx1)
     
    static <T extends Comparable<T>>
    T
    select(T[] data, int k, int maxIndex, int[] indexes)
    Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest.
    static int
    selectIndex(byte[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.
    static int
    selectIndex(double[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.
    static int
    selectIndex(float[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.
    static int
    selectIndex(int[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.
    static int
    selectIndex(long[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.
    static int
    selectIndex(short[] data, int k, int maxIndex, int[] indexes)
    Returns the original index of the 'k' largest element in the list.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • QuickSelect

      public QuickSelect()

  • Method Details

    • select

      public static <T extends Comparable<T>> T select(T[] data, int k, int idx1)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convenience the 'k' element is returned.
      Parameters:
      data - The unsorted list
      k - The element of the sorted list that is to be found
      idx1 - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • select

      public static <T extends Comparable<T>> T select(T[] data, int k, int idx0, int idx1)
      Parameters:
      k - All elements i data[idx0+i] <= data[idx0+k]
      idx0 - Lower extent of the array considered. Inclusive.
      idx1 - Upper extent of the array considered. Exclusive.
      Returns:
      value at 'k'

    • select

      public static <T extends Comparable<T>> T select(T[] data, int k, int maxIndex, int[] indexes)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convenience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Not modified.
      k - The element of the sorted list that is to be found
      maxIndex - Only element up to this value are considered
      indexes - (output) Sorted list of indexes.
      Returns:
      the 'k'th largest element

    • select

      public static float select(float[] data, int k, int size)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      size - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • select

      public static float select(float[] data, int k, int idx0, int idx1)
      Parameters:
      k - All elements i data[idx0+i] <= data[idx0+k]
      idx0 - Lower extent of the array considered. Inclusive.
      idx1 - Upper extent of the array considered. Exclusive.
      Returns:
      value at 'k'

    • selectIndex

      public static int selectIndex(float[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten

    • select

      public static double select(double[] data, int k, int size)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      size - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • select

      public static double select(double[] data, int k, int idx0, int idx1)
      Parameters:
      k - All elements i data[idx0+i] <= data[idx0+k]
      idx0 - Lower extent of the array considered. Inclusive.
      idx1 - Upper extent of the array considered. Exclusive.
      Returns:
      value at 'k'

    • selectIndex

      public static int selectIndex(double[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten

    • select

      public static long select(long[] data, int k, int maxIndex)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      maxIndex - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • selectIndex

      public static int selectIndex(long[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten

    • select

      public static int select(int[] data, int k, int maxIndex)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      maxIndex - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • selectIndex

      public static int selectIndex(int[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten

    • select

      public static short select(short[] data, int k, int maxIndex)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      maxIndex - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • selectIndex

      public static int selectIndex(short[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten

    • select

      public static byte select(byte[] data, int k, int maxIndex)
      Sorts the array such that the values in the array up to and including 'k' are sorted the least to greatest. This implies that the array itself is modified. For convinience the 'k' element is returned.
      Parameters:
      data - The unsorted list. Is modified.
      k - The element of the sorted list that is to be found
      maxIndex - Only element up to this value are considered
      Returns:
      the 'k'th largest element

    • selectIndex

      public static int selectIndex(byte[] data, int k, int maxIndex, int[] indexes)

      Returns the original index of the 'k' largest element in the list.

      Note: There is additional overhead since the values of indexes needs to be set

      Parameters:
      indexes - Temporary storage and is overwritten