com.carrotsearch.hppcrt.sorting

Class IndirectSort

java.lang.Object

com.carrotsearch.hppcrt.sorting.IndirectSort

public final class IndirectSort
extends java.lang.Object

Sorting routines that return an array of sorted indices implied by a given comparator rather than move elements of whatever the comparator is using for comparisons.

A practical use case for this class is when the index of an array is meaningful and one wants to acquire the order of values in that array. None of the methods in Java Collections would provide such functionality directly and creating a collection of boxed Integer objects for indices seems to be too costly.

Method Summary

Modifier and Type	Method and Description
static int[]	mergesort(int start, int length, IndirectComparator comparator) Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator.
static void	mergesort(int start, int length, IndirectComparator comparator, int[] tmpArray, int[] sorted) Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator.
static <T> int[]	mergesort(T[] input, int start, int length, java.util.Comparator<? super T> comparator) Returns the order of elements between indices start and length + start excluded, as indicated by the given comparator.
static void	quicksort(int start, int length, IndirectComparator comparator, int[] sorted) Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

mergesort

public static int[] mergesort(int start,
                              int length,
                              IndirectComparator comparator)

Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator.

This routine uses merge sort. It is guaranteed to be stable. Take note this method generate temporaries.

mergesort

public static void mergesort(int start,
                             int length,
                             IndirectComparator comparator,
                             int[] tmpArray,
                             int[] sorted)

Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator. This method entirely work by using pre-existing arrays, so is fitting for realtime.

This routine uses merge sort. It is guaranteed to be stable.

Parameters:

tmpArray - : a temporary array for usage in intermediate computation, its size must be >= length

sorted - : the sorted indices result. The array must be at least of size length, and the real validity range is [0; length[

quicksort

public static void quicksort(int start,
                             int length,
                             IndirectComparator comparator,
                             int[] sorted)

Returns the order of elements between indices start and start + length excluded, as indicated by the given comparator. This method entirely work in-place, so is fitting for realtime.

This routine uses Dual-pivot Quicksort, from [Yaroslavskiy 2009], so is NOT stable.

Parameters:

sorted - : the sorted indices result. The array must be at least of size length, and the real validity range is [0; length[

mergesort

public static <T> int[] mergesort(T[] input,
                                  int start,
                                  int length,
                                  java.util.Comparator<? super T> comparator)

Returns the order of elements between indices start and length + start excluded, as indicated by the given comparator. This method is equivalent to calling mergesort(int, int, IndirectComparator) with IndirectComparator.DelegatingComparator.

This routine uses merge sort. It is guaranteed to be stable.

Take note this method generate temporaries.