@Reference(authors="Vladimir Yaroslavskiy", title="Dual-Pivot Quicksort", booktitle="http://iaroslavski.narod.ru/quicksort/", url="http://iaroslavski.narod.ru/quicksort/") class IntegerDBIDArrayQuickSort 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 |
---|
IntegerDBIDArrayQuickSort() |
Modifier and Type | Method and Description |
---|---|
private static int |
compare(IntegerDBIDVar i1,
int p1,
IntegerDBIDVar i2,
int p2,
Comparator<? super DBIDRef> comp)
Compare two elements.
|
private static void |
quickSort(int[] data,
int start,
int end,
Comparator<? super DBIDRef> comp,
IntegerDBIDVar vl,
IntegerDBIDVar vk,
IntegerDBIDVar vr)
Actual recursive sort function.
|
static void |
sort(int[] data,
Comparator<? super DBIDRef> comp)
Sort the full array using the given comparator.
|
static void |
sort(int[] data,
int start,
int end,
Comparator<? super DBIDRef> comp)
Sort the array using the given comparator.
|
private static final int INSERTION_THRESHOLD
public static void sort(int[] data, Comparator<? super DBIDRef> comp)
data
- Data to sortcomp
- Comparatorpublic static void sort(int[] data, int start, int end, Comparator<? super DBIDRef> comp)
data
- Data to sortstart
- First indexend
- Last index (exclusive)comp
- Comparatorprivate static void quickSort(int[] data, int start, int end, Comparator<? super DBIDRef> comp, IntegerDBIDVar vl, IntegerDBIDVar vk, IntegerDBIDVar vr)
data
- Data to sortstart
- First indexend
- Last index (inclusive!)comp
- Comparatorvl
- First seeking iteratorvk
- Second seeking iteratorvr
- Third seeking iteratorprivate static int compare(IntegerDBIDVar i1, int p1, IntegerDBIDVar i2, int p2, Comparator<? super DBIDRef> comp)
i1
- First scratch variablep1
- Value for firsti2
- Second scratch variablep2
- Value for secondcomp
- Comparator