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
All Methods Static Methods Concrete Methods 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.
-
-
-
Field Detail
-
INSERTION_THRESHOLD
private static final int INSERTION_THRESHOLD
Threshold for using insertion sort.- See Also:
- Constant Field Values
-
-
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 sortingvalues
- Values for sortinglen
- 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 sortingvalues
- Values for sortingstart
- First indexend
- Last index (exclusive)
-
quickSort
private static void quickSort(double[] keys, int[] vals, int start, int end)
Actual recursive sort function.- Parameters:
keys
- Keys for sortingvals
- Values for sortingstart
- First indexend
- 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
- Keysvals
- Valuesm1
- Pivot candidate positionm2
- Pivot candidate positionm3
- Pivot candidate positionm4
- Pivot candidate positionm5
- Pivot candidate position
-
insertionSort
private static void insertionSort(double[] keys, int[] vals, int start, int end)
Sort via insertion sort.- Parameters:
keys
- Keysvals
- Valuesstart
- Interval startend
- 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 sortingvalues
- Values for sortinglen
- 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 sortingvalues
- Values for sortingstart
- First indexend
- Last index (exclusive)
-
quickSortReverse
private static void quickSortReverse(double[] keys, int[] vals, int start, int end)
Actual recursive sort function.- Parameters:
keys
- Keys for sortingvals
- Values for sortingstart
- First indexend
- 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
- Keysvals
- Valuesm1
- Pivot candidate positionm2
- Pivot candidate positionm3
- Pivot candidate positionm4
- Pivot candidate positionm5
- Pivot candidate position
-
insertionSortReverse
private static void insertionSortReverse(double[] keys, int[] vals, int start, int end)
Sort via insertion sort.- Parameters:
keys
- Keysvals
- Valuesstart
- Interval startend
- Interval end
-
swap
private static void swap(double[] keys, int[] vals, int j, int i)
Swap two entries.- Parameters:
keys
- Keysvals
- Valuesj
- First indexi
- Second index
-
-