com.devexperts.util

Class QuickSort

java.lang.Object

com.devexperts.util.QuickSort

public class QuickSort
extends Object

This class implements modified version of Quick Sort algorithm. This implementation offers O(n*log(n)) performance on many data sets that cause other quick sort algorithms to degrade to quadratic performance.

The notable differences of this Quick Sort from other sorting algorithms are:

• it is unstable - it can re-arrange equal elements in any order;
• it is robust - it can withstand unstable ordering of elements, for example if ordering changes during sorting;
• it is garbage-free - it does not allocate any temporary objects.

In the case of unstable ordering the result of this algorithm is not necessarily fully sorted, but it is guaranteed to complete in a finite amount of time and without exceptions. The result in this case would be partially sorted to the best of algorithm's ability.

Method Summary

Modifier and Type	Method and Description
static void	sort(int[] a, IntComparator c) Sorts the specified array of ints according to the order induced by the specified comparator.
static void	sort(int[] a, int fromIndex, int toIndex, IntComparator c) Sorts the specified range of the specified array of ints according to the order induced by the specified comparator.
static <T extends Comparable<? super T>> void	sort(List<T> list) Sorts the specified list into ascending order according to the natural ordering of its elements.
static <T> void	sort(List<T> list, Comparator<? super T> c) Sorts the specified list according to the order induced by the specified comparator.
static <T extends Comparable<? super T>> void	sort(List<T> list, int fromIndex, int toIndex) Sorts the specified range of the specified list into ascending order according to the natural ordering of its elements.
static <T> void	sort(List<T> list, int fromIndex, int toIndex, Comparator<? super T> c) Sorts the specified range of the specified list according to the order induced by the specified comparator.
static void	sort(long[] a, int fromIndex, int toIndex, LongComparator c) Sorts the specified range of the specified array of longs according to the order induced by the specified comparator.
static void	sort(long[] a, LongComparator c) Sorts the specified array of longs according to the order induced by the specified comparator.
static void	sort(Object[] a) Sorts the specified array of objects into ascending order according to the natural ordering of its elements.
static void	sort(Object[] a, int fromIndex, int toIndex) Sorts the specified range of the specified array of objects into ascending order according to the natural ordering of its elements.
static <T> void	sort(T[] a, Comparator<? super T> c) Sorts the specified array of objects according to the order induced by the specified comparator.
static <T> void	sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) Sorts the specified range of the specified array of objects according to the order induced by the specified comparator.

Methods inherited from class java.lang.Object

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

Method Detail

sort

public static <T extends Comparable<? super T>> void sort(List<T> list)

Sorts the specified list into ascending order according to the natural ordering of its elements. All elements in the list must implement the Comparable interface. Furthermore, all elements in the list must be mutually comparable.

Type Parameters:

T - the class of the objects in the list.

Parameters:

list - the list to be sorted.

Throws:

ClassCastException - if the list contains elements that are not mutually comparable.

sort

public static <T extends Comparable<? super T>> void sort(List<T> list,
                                                          int fromIndex,
                                                          int toIndex)

Sorts the specified range of the specified list into ascending order according to the natural ordering of its elements. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in this range must implement the Comparable interface. Furthermore, all elements in this range must be mutually comparable.

Type Parameters:

T - the class of the objects in the list.

Parameters:

list - the list to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.

ClassCastException - if the list contains elements that are not mutually comparable.

sort

public static <T> void sort(List<T> list,
                            Comparator<? super T> c)

Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator.

Type Parameters:

T - the class of the objects in the list.

Parameters:

list - the list to be sorted.

c - the comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used.

Throws:

ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator.

sort

public static <T> void sort(List<T> list,
                            int fromIndex,
                            int toIndex,
                            Comparator<? super T> c)

Sorts the specified range of the specified list according to the order induced by the specified comparator. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in the range must be mutually comparable by the specified comparator.

Type Parameters:

T - the class of the objects in the list.

Parameters:

list - the list to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

c - the comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.

ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator.

sort

public static void sort(Object[] a)

Sorts the specified array of objects into ascending order according to the natural ordering of its elements. All elements in the array must implement the Comparable interface. Furthermore, all elements in the array must be mutually comparable.

Parameters:

a - the array to be sorted.

Throws:

ClassCastException - if the array contains elements that are not mutually comparable.

sort

public static void sort(Object[] a,
                        int fromIndex,
                        int toIndex)

Sorts the specified range of the specified array of objects into ascending order according to the natural ordering of its elements. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in this range must implement the Comparable interface. Furthermore, all elements in this range must be mutually comparable.

Parameters:

a - the array to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.

ClassCastException - if the array contains elements that are not mutually comparable.

sort

public static <T> void sort(T[] a,
                            Comparator<? super T> c)

Sorts the specified array of objects according to the order induced by the specified comparator. All elements in the array must be mutually comparable by the specified comparator.

Type Parameters:

T - the class of the objects to be sorted.

Parameters:

a - the array to be sorted.

c - the comparator to determine the order of the array. A null value indicates that the elements' natural ordering should be used.

Throws:

ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.

sort

public static <T> void sort(T[] a,
                            int fromIndex,
                            int toIndex,
                            Comparator<? super T> c)

Sorts the specified range of the specified array of objects according to the order induced by the specified comparator. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in the range must be mutually comparable by the specified comparator.

Type Parameters:

T - the class of the objects to be sorted.

Parameters:

a - the array to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

c - the comparator to determine the order of the array. A null value indicates that the elements' natural ordering should be used.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.

ClassCastException - if the array contains elements that are not mutually comparable using the specified comparator.

sort

public static void sort(int[] a,
                        IntComparator c)

Sorts the specified array of ints according to the order induced by the specified comparator. All elements in the array must be mutually comparable by the specified comparator.

Parameters:

a - the array to be sorted.

c - the comparator to determine the order of the array.

sort

public static void sort(int[] a,
                        int fromIndex,
                        int toIndex,
                        IntComparator c)

Sorts the specified range of the specified array of ints according to the order induced by the specified comparator. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in the range must be mutually comparable by the specified comparator.

Parameters:

a - the array to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

c - the comparator to determine the order of the array.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.

sort

public static void sort(long[] a,
                        LongComparator c)

Sorts the specified array of longs according to the order induced by the specified comparator. All elements in the array must be mutually comparable by the specified comparator.

Parameters:

a - the array to be sorted.

c - the comparator to determine the order of the array.

sort

public static void sort(long[] a,
                        int fromIndex,
                        int toIndex,
                        LongComparator c)

Sorts the specified range of the specified array of longs according to the order induced by the specified comparator. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive. All elements in the range must be mutually comparable by the specified comparator.

Parameters:

a - the array to be sorted.

fromIndex - the index of the first element (inclusive) to be sorted.

toIndex - the index of the last element (exclusive) to be sorted.

c - the comparator to determine the order of the array.

Throws:

IllegalArgumentException - if fromIndex > toIndex.

IndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length.