de.lmu.ifi.dbs.elki.utilities.datastructures.arrays

Class IntegerArrayQuickSort

java.lang.Object

de.lmu.ifi.dbs.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 Quicksort

and 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 and Description
private static int	INSERTION_THRESHOLD Threshold for using insertion sort.

Constructor Summary

Constructors

Modifier	Constructor and Description
private	IntegerArrayQuickSort() Private constructor.

Method Summary

Modifier and Type	Method and 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, it.unimi.dsi.fastutil.ints.IntComparator comp) Sort the full array using the given comparator.
static void	sort(int[] data, int start, int end, it.unimi.dsi.fastutil.ints.IntComparator comp) Sort the 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.

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. Value taken from Javas QuickSort, assuming that it will be similar for our data sets.

See Also:

Constant Field Values

Constructor Detail

IntegerArrayQuickSort

private IntegerArrayQuickSort()

Private constructor. Static methods only.

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 sort

comp - 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 sort

start - First index

end - 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 sort

start - First index

end - 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 sort

start - First index

end - 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 - Data

m1 - Pivot candidate position

m2 - Pivot candidate position

m3 - Pivot candidate position

m4 - Pivot candidate position

m5 - Pivot candidate position

comp - Comparator