org.ddogleg.sorting

Class QuickSelect

java.lang.Object

org.ddogleg.sorting.QuickSelect

public class QuickSelect
extends java.lang.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 and Description
QuickSelect()

Method Summary

Modifier and Type	Method and 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 java.lang.Comparable	select(java.lang.Comparable[] 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 java.lang.Comparable	select(java.lang.Comparable[] 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 double	select(double[] 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 float	select(float[] 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 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 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

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

Constructor Detail

QuickSelect

public QuickSelect()

Method Detail

select

public static java.lang.Comparable select(java.lang.Comparable[] 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 convenience the 'k' element is returned.

Parameters:

data - The unsorted list

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

select

public static java.lang.Comparable select(java.lang.Comparable[] 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 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(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 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(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