@Reference(authors="Vladimir Yaroslavskiy", title="Dual-Pivot Quicksort", booktitle="http://iaroslavski.narod.ru/quicksort/", url="http://iaroslavski.narod.ru/quicksort/") public class IntegerArrayQuickSort extends Object
Dual-Pivot Quicksort
Vladimir Yaroslavskiy
Modifier and Type | Field and Description |
---|---|
private static int |
INSERTION_THRESHOLD
Threshold for using insertion sort.
|
Constructor and Description |
---|
IntegerArrayQuickSort() |
Modifier and Type | Method and Description |
---|---|
private static void |
insertionSort(int[] data,
int start,
int end,
IntegerComparator comp)
Insertion sort, for short arrays.
|
private static void |
quickSort(int[] data,
int start,
int end,
IntegerComparator comp)
Actual recursive sort function.
|
static void |
sort(int[] data,
IntegerComparator comp)
Sort the full array using the given comparator.
|
static void |
sort(int[] data,
int start,
int end,
IntegerComparator comp)
Sort the array using the given comparator.
|
private static void |
sort5(int[] data,
int m1,
int m2,
int m3,
int m4,
int m5,
IntegerComparator comp)
An explicit sort, for the five pivot candidates.
|
private static final int INSERTION_THRESHOLD
public static void sort(int[] data, IntegerComparator comp)
data
- Data to sortcomp
- Comparatorpublic static void sort(int[] data, int start, int end, IntegerComparator comp)
data
- Data to sortstart
- First indexend
- Last index (exclusive)comp
- Comparatorprivate static void quickSort(int[] data, int start, int end, IntegerComparator comp)
data
- Data to sortstart
- First indexend
- Last index (exclusive!)comp
- Comparatorprivate static void insertionSort(int[] data, int start, int end, IntegerComparator comp)
data
- Data to sortstart
- First indexend
- Last index (exclusive!)comp
- Comparatorprivate static void sort5(int[] data, int m1, int m2, int m3, int m4, int m5, IntegerComparator comp)
m1 < m2 < m3 < m4 < m5
.data
- Datam1
- Pivot candidate positionm2
- Pivot candidate positionm3
- Pivot candidate positionm4
- Pivot candidate positionm5
- Pivot candidate positioncomp
- ComparatorCopyright © 2015 ELKI Development Team, Lehr- und Forschungseinheit für Datenbanksysteme, Ludwig-Maximilians-Universität München. License information.