de.lmu.ifi.dbs.elki.database.ids.integer

Class IntegerDBIDArrayQuickSort

java.lang.Object

de.lmu.ifi.dbs.elki.database.ids.integer.IntegerDBIDArrayQuickSort

@Reference(authors="Vladimir Yaroslavskiy",
           title="Dual-Pivot Quicksort",
           booktitle="http://iaroslavski.narod.ru/quicksort/",
           url="http://iaroslavski.narod.ru/quicksort/")
 class IntegerDBIDArrayQuickSort
extends Object

Class to sort an integer DBID array, using a modified quicksort. Two array iterators will be used to seek to the elements to compare, while the backing storage is a plain integer array. The implementation is closely based on:

Dual-Pivot Quicksort
Vladimir Yaroslavskiy

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
IntegerDBIDArrayQuickSort()

Method Summary

Methods

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.

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 DBIDs.

See Also:

Constant Field Values

Constructor Detail

IntegerDBIDArrayQuickSort

IntegerDBIDArrayQuickSort()

Method Detail

sort

public static void sort(int[] data,
        Comparator<? super DBIDRef> 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,
        Comparator<? super DBIDRef> 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,
             Comparator<? super DBIDRef> comp,
             IntegerDBIDVar vl,
             IntegerDBIDVar vk,
             IntegerDBIDVar vr)

Actual recursive sort function.

Parameters:

data - Data to sort

start - First index

end - Last index (inclusive!)

comp - Comparator

vl - First seeking iterator

vk - Second seeking iterator

vr - Third seeking iterator

compare

private static int compare(IntegerDBIDVar i1,
          int p1,
          IntegerDBIDVar i2,
          int p2,
          Comparator<? super DBIDRef> comp)

Compare two elements.

Parameters:

i1 - First scratch variable

p1 - Value for first

i2 - Second scratch variable

p2 - Value for second

comp - Comparator

Returns:

Comparison result