Package elki.utilities.datastructures.arrays

Class DoubleIntegerArrayQuickSort

java.lang.Object

elki.utilities.datastructures.arrays.DoubleIntegerArrayQuickSort

public final class DoubleIntegerArrayQuickSort
extends java.lang.Object

Class to sort a double and an integer DBID array, using a quicksort with a best of 5 heuristic.

Since:

0.6.0

Author:

Erich Schubert

Field Summary

Fields

Modifier and Type	Field	Description
private static int	INSERTION_THRESHOLD	Threshold for using insertion sort.

Constructor Summary

Constructors

Modifier	Constructor	Description
private	DoubleIntegerArrayQuickSort()	Private constructor.

Method Summary

Modifier and Type	Method	Description
private static void	insertionSort(double[] keys, int[] vals, int start, int end)	Sort via insertion sort.
private static void	insertionSortReverse(double[] keys, int[] vals, int start, int end)	Sort via insertion sort.
private static void	quickSort(double[] keys, int[] vals, int start, int end)	Actual recursive sort function.
private static void	quickSortReverse(double[] keys, int[] vals, int start, int end)	Actual recursive sort function.
static void	sort(double[] keys, int[] values, int len)	Sort the full array using the given comparator.
static void	sort(double[] keys, int[] values, int start, int end)	Sort the array using the given comparator.
private static void	sort5(double[] keys, int[] vals, int m1, int m2, int m3, int m4, int m5)	An explicit sort, for the five pivot candidates.
static void	sortReverse(double[] keys, int[] values, int len)	Sort the full array using the given comparator.
static void	sortReverse(double[] keys, int[] values, int start, int end)	Sort the array using the given comparator.
private static void	sortReverse5(double[] keys, int[] vals, int m1, int m2, int m3, int m4, int m5)	An explicit sort, for the five pivot candidates.
private static void	swap(double[] keys, int[] vals, int j, int i)	Swap two entries.

Methods inherited from class java.lang.Object

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

Field Detail

INSERTION_THRESHOLD

private static final int INSERTION_THRESHOLD

Threshold for using insertion sort.

See Also:

Constant Field Values

Constructor Detail

DoubleIntegerArrayQuickSort

private DoubleIntegerArrayQuickSort()

Private constructor. Static methods only.

Method Detail

sort

public static void sort(double[] keys,
                        int[] values,
                        int len)

Sort the full array using the given comparator.

Parameters:

keys - Keys for sorting

values - Values for sorting

len - Length to sort.

sort

public static void sort(double[] keys,
                        int[] values,
                        int start,
                        int end)

Sort the array using the given comparator.

Parameters:

keys - Keys for sorting

values - Values for sorting

start - First index

end - Last index (exclusive)

quickSort

private static void quickSort(double[] keys,
                              int[] vals,
                              int start,
                              int end)

Actual recursive sort function.

Parameters:

keys - Keys for sorting

vals - Values for sorting

start - First index

end - Last index (exclusive!)

sort5

private static void sort5(double[] keys,
                          int[] vals,
                          int m1,
                          int m2,
                          int m3,
                          int m4,
                          int m5)

An explicit sort, for the five pivot candidates.

Note that this must only be used with m1 < m2 < m3 < m4 < m5.

Parameters:

keys - Keys

vals - Values

m1 - Pivot candidate position

m2 - Pivot candidate position

m3 - Pivot candidate position

m4 - Pivot candidate position

m5 - Pivot candidate position

insertionSort

private static void insertionSort(double[] keys,
                                  int[] vals,
                                  int start,
                                  int end)

Sort via insertion sort.

Parameters:

keys - Keys

vals - Values

start - Interval start

end - Interval end

sortReverse

public static void sortReverse(double[] keys,
                               int[] values,
                               int len)

Sort the full array using the given comparator.

Parameters:

keys - Keys for sorting

values - Values for sorting

len - Length to sort.

sortReverse

public static void sortReverse(double[] keys,
                               int[] values,
                               int start,
                               int end)

Sort the array using the given comparator.

Parameters:

keys - Keys for sorting

values - Values for sorting

start - First index

end - Last index (exclusive)

quickSortReverse

private static void quickSortReverse(double[] keys,
                                     int[] vals,
                                     int start,
                                     int end)

Actual recursive sort function.

Parameters:

keys - Keys for sorting

vals - Values for sorting

start - First index

end - Last index (exclusive!)

sortReverse5

private static void sortReverse5(double[] keys,
                                 int[] vals,
                                 int m1,
                                 int m2,
                                 int m3,
                                 int m4,
                                 int m5)

An explicit sort, for the five pivot candidates.

Note that this must only be used with m1 < m2 < m3 < m4 < m5.

Parameters:

keys - Keys

vals - Values

m1 - Pivot candidate position

m2 - Pivot candidate position

m3 - Pivot candidate position

m4 - Pivot candidate position

m5 - Pivot candidate position

insertionSortReverse

private static void insertionSortReverse(double[] keys,
                                         int[] vals,
                                         int start,
                                         int end)

Sort via insertion sort.

Parameters:

keys - Keys

vals - Values

start - Interval start

end - Interval end

swap

private static void swap(double[] keys,
                         int[] vals,
                         int j,
                         int i)

Swap two entries.

Parameters:

keys - Keys

vals - Values

j - First index

i - Second index