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

Class IntegerArrayQuickSort

java.lang.Object

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

@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

Class to sort an int array, using a modified quicksort. The implementation is closely based on:

Dual-Pivot Quicksort
Vladimir Yaroslavskiy

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.

Field Summary

Fields

Modifier and Type	Field and Description
private static int	INSERTION_THRESHOLD Threshold for using insertion sort.

Constructor Summary

Constructors

Constructor and Description
IntegerArrayQuickSort()

Method Summary

Methods

Modifier and Type	Method and Description
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.

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

public IntegerArrayQuickSort()

Method Detail

sort

public static void sort(int[] data,
        IntegerComparator 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,
        IntegerComparator 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,
             IntegerComparator comp)

Actual recursive sort function.

Parameters:

data - Data to sort

start - First index

end - Last index (inclusive!)

comp - Comparator