de.caff.generics.algorithm

Class DualPivotQuicksort

java.lang.Object

de.caff.generics.algorithm.DualPivotQuicksort

public final class DualPivotQuicksort
extends java.lang.Object

This class implements the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Changes by Rammi: make this class public and allow user-defined order. Because standard order tests for primitive types are fast operations having a user-defined order makes sorting some 50% slower for these types. For test purposes this also allows sorting generic indexables like TimSort, but tests show that TimSort is faster in most cases.

Like standard quicksort this sorting algorithm is not stable.

Since:

1.7

Version:

2011.02.11 m765.827.12i:5\7pm

Author:

Vladimir Yaroslavskiy, Jon Bentley, Josh Bloch, Rammi

Method Summary

Modifier and Type	Method and Description
static void	sort(byte[] a, ByteOrdering order) Sorts the specified array in the specified order.
static void	sort(byte[] a, int left, int right, ByteOrdering order) Sorts the specified range of the array in the specified order.
static void	sort(char[] a, CharOrdering order) Sorts the specified array.
static void	sort(char[] a, int left, int right, CharOrdering order) Sorts the specified range of the array.
static void	sort(double[] a, DoubleOrdering order) Sorts the specified array according to the specified order.
static void	sort(double[] a, int left, int right, DoubleOrdering order) Sorts the specified range of the array according to the specified order.
static void	sort(float[] a, FloatOrdering order) Sorts the specified array using the specified order.
static void	sort(float[] a, int left, int right, FloatOrdering order) Sorts the specified range of the array.
static void	sort(int[] a, int left, int right, IntOrdering order) Sorts the specified range of the array.
static void	sort(int[] a, IntOrdering order) Sorts the specified array.
static void	sort(long[] a, int left, int right, LongOrdering order) Sorts the specified range of the array.
static void	sort(long[] a, LongOrdering order) Sorts the specified array.
(package private) static <T> void	sort(MutableIndexable<T> a, Ordering<? super T> order) Sorts the specified mutable int indexable by the given order.
static void	sort(MutableIntIndexable a) Sorts the specified mutable int indexable by the natural order of the elements.
static void	sort(MutableIntIndexable a, IntOrdering order) Sorts the specified mutable int indexable by the given order.
static void	sort(short[] a, int left, int right, ShortOrdering order) Sorts the specified range of the array.
static void	sort(short[] a, ShortOrdering order) Sorts the specified array.

Methods inherited from class java.lang.Object

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

Method Detail

sort

public static void sort(int[] a,
                        @NotNull
                        IntOrdering order)

Sorts the specified array.

Parameters:

a - the array to be sorted

order - user-defined order

sort

public static void sort(int[] a,
                        int left,
                        int right,
                        @NotNull
                        IntOrdering order)

Sorts the specified range of the array.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - user-defined order

sort

public static void sort(long[] a,
                        @NotNull
                        LongOrdering order)

Sorts the specified array.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(long[] a,
                        int left,
                        int right,
                        @NotNull
                        LongOrdering order)

Sorts the specified range of the array.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

public static void sort(@NotNull
                        short[] a,
                        @NotNull
                        ShortOrdering order)

Sorts the specified array.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(@NotNull
                        short[] a,
                        int left,
                        int right,
                        @NotNull
                        ShortOrdering order)

Sorts the specified range of the array.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

public static void sort(@NotNull
                        char[] a,
                        @NotNull
                        CharOrdering order)

Sorts the specified array.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(@NotNull
                        char[] a,
                        int left,
                        int right,
                        @NotNull
                        CharOrdering order)

Sorts the specified range of the array.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

public static void sort(@NotNull
                        byte[] a,
                        @NotNull
                        ByteOrdering order)

Sorts the specified array in the specified order.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(@NotNull
                        byte[] a,
                        int left,
                        int right,
                        @NotNull
                        ByteOrdering order)

Sorts the specified range of the array in the specified order.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

public static void sort(@NotNull
                        float[] a,
                        @NotNull
                        FloatOrdering order)

Sorts the specified array using the specified order.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(@NotNull
                        float[] a,
                        int left,
                        int right,
                        @NotNull
                        FloatOrdering order)

Sorts the specified range of the array.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

public static void sort(@NotNull
                        double[] a,
                        @NotNull
                        DoubleOrdering order)

Sorts the specified array according to the specified order.

Parameters:

a - the array to be sorted

order - sort order

sort

public static void sort(double[] a,
                        int left,
                        int right,
                        @NotNull
                        DoubleOrdering order)

Sorts the specified range of the array according to the specified order.

Parameters:

a - the array to be sorted

left - the index of the first element, inclusive, to be sorted

right - the index of the last element, inclusive, to be sorted

order - sort order

sort

static <T> void sort(@NotNull
                     MutableIndexable<T> a,
                     @NotNull
                     Ordering<? super T> order)

Sorts the specified mutable int indexable by the given order. This is some 40% slower than the array method, therefore it's only kept to allow testing.

Type Parameters:

T - element type

Parameters:

a - the indexable to be sorted

order - user-defined order

sort

public static void sort(@NotNull
                        MutableIntIndexable a)

Sorts the specified mutable int indexable by the natural order of the elements.

Parameters:

a - the int indexable to be sorted

sort

public static void sort(@NotNull
                        MutableIntIndexable a,
                        @NotNull
                        IntOrdering order)

Sorts the specified mutable int indexable by the given order.

Parameters:

a - the indexable to be sorted

order - user-defined order