Class IntegerArrayQuickSort
- java.lang.Object
-
- elki.utilities.datastructures.arrays.IntegerArrayQuickSort
-
@Reference(authors="V. Yaroslavskiy", title="Dual-Pivot Quicksort", booktitle="", url="http://iaroslavski.narod.ru/quicksort/", bibkey="web/Yaroslavskiy09") public class IntegerArrayQuickSort extends java.lang.Object
Class to sort an int array, using a modified quicksort.Reference:
The implementation is closely based on:
Vladimir Yaroslavskiy
Dual-Pivot Quicksortand differs mostly in that we sort different kinds of arrays, and allow the use of comparators - useful in particular when the array references external objects.
- Since:
- 0.5.5
- 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
IntegerArrayQuickSort()
Private constructor.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description private static void
insertionSort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Insertion sort, for short arrays.private static void
quickSort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Actual recursive sort function.static void
sort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Sort the array using the given comparator.static void
sort(int[] data, it.unimi.dsi.fastutil.ints.IntComparator comp)
Sort the full array using the given comparator.private static void
sort5(int[] data, int m1, int m2, int m3, int m4, int m5, it.unimi.dsi.fastutil.ints.IntComparator comp)
An explicit sort, for the five pivot candidates.
-
-
-
Field Detail
-
INSERTION_THRESHOLD
private static final int INSERTION_THRESHOLD
Threshold for using insertion sort. Value taken from Javas QuickSort, assuming that it will be similar for our data sets.- See Also:
- Constant Field Values
-
-
Method Detail
-
sort
public static void sort(int[] data, it.unimi.dsi.fastutil.ints.IntComparator comp)
Sort the full array using the given comparator.- Parameters:
data
- Data to sortcomp
- Comparator
-
sort
public static void sort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Sort the array using the given comparator.- Parameters:
data
- Data to sortstart
- First indexend
- Last index (exclusive)comp
- Comparator
-
quickSort
private static void quickSort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Actual recursive sort function.- Parameters:
data
- Data to sortstart
- First indexend
- Last index (exclusive!)comp
- Comparator
-
insertionSort
private static void insertionSort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp)
Insertion sort, for short arrays.- Parameters:
data
- Data to sortstart
- First indexend
- Last index (exclusive!)comp
- Comparator
-
sort5
private static void sort5(int[] data, int m1, int m2, int m3, int m4, int m5, it.unimi.dsi.fastutil.ints.IntComparator comp)
An explicit sort, for the five pivot candidates.Note that this must only be used with
m1 < m2 < m3 < m4 < m5
.- Parameters:
data
- Datam1
- Pivot candidate positionm2
- Pivot candidate positionm3
- Pivot candidate positionm4
- Pivot candidate positionm5
- Pivot candidate positioncomp
- Comparator
-
-