Package net.algart.arrays

Class ArraySorter

java.lang.Object

net.algart.arrays.ArraySorter

public abstract class ArraySorter
extends Object

Sorting algorithms. This class provides several implementations for Insertion, Shell and QuickSort algorithm. (The QuickSort variant is the best choice almost always, it is better than Shell algorithm in 1.5-2.5 times.)

Standard Java sorting methods allows sorting only primitive arrays or collections of objects, represented as usual instances of Java classes (every object is a pointer and requires ~10-20 additional bytes of service memory). Unlike that, ArraySorter class allows to sort any data arrays, represented in any way. To do this, ArraySorter uses ArrayComparator and ArrayExchanger interfaces to access all sorted elements.

For example, this class can sort an array of points by x-coordinate stored in a single Java array, as shown in the following example:

 int n = 10;
 final float[] xy = new float[2 * n];
 for (int k = 0; k < n; k++) {
     xy[2 * k] = (float)Math.random();     // x-coordinate of the point #k
     xy[2 * k + 1] = (float)Math.random(); // y-coordinate of the point #k
 }
 Sorter.getQuickSortInstance().sort(0, n,
     new ArrayComparator() {
     public boolean less(long i, long j) {
         return xy[2 * (int)i] < xy[2 * (int)j];
     }
 },
     new ArrayExchanger() {
     public void swap(long i, long j) {
         float temp = xy[2 * (int)i];
         xy[2 * (int)i] = xy[2 * (int)j];
         xy[2 * (int)j] = temp;
         temp = xy[2 * (int)i + 1];
         xy[2 * (int)i + 1] = xy[2 * (int)j + 1];
         xy[2 * (int)j + 1] = temp;
     }
 });

Any updatable AlgART array already implements ArrayExchanger interface. So, AlgART arrays can be sorted by implementing ArrayComparator interface only, alike standard Java collections. There is Arrays.sort method performing such sorting by QuickSort instance of this class.

Also this class allows to sort int[] array of indexes of elements and not move data at all. It is often useful for large sorted elements.

Please note that the sorting algorithms, provided by this class, excepting the slow Insertion algorithm, are not stable: equal elements may be reordered as a result of the sort. If you need stable sorting some objects, please use java.util package.

Unlike standard Java sorting algorithms, this class has no restriction 2³¹-1 for the length of sorted arrays. This class allows to sort up to 2⁶³−1 elements.

Author:

Daniel Alievsky

Method Summary

Modifier and Type	Method	Description
static boolean	areIndexesSorted(int[] indexes, int from, int to, ArrayComparator comparator)	Returns true if the from..to-1 range of indexes in some array is sorted.
static boolean	areSorted(long from, long to, ArrayComparator comparator)	Returns true if the from..to-1 range of some array is sorted.
static ArraySorter	getInsertionSorter()	Returns an instance of this class that implements insertion sorting algorithm.
static ArraySorter	getQuickSorter()	Returns an instance of this class that implements QuickSort sorting algorithm.
static ArraySorter	getShellSorter()	Returns an instance of this class that implements Shell sorting algorithm.
boolean	isExchangingSorter()	Returns true, if it is enough to implement the pure ArrayExchanger interface by the exchanger argument of sort(long, long, ArrayComparator, ArrayExchanger) method, or false, if that method requires exchanger to implement something else.
void	sort(int from, int to, ArrayComparator32 comparator, ArrayExchanger32 exchanger)	Calls the previous sort(long, long, ArrayComparator, ArrayExchanger) method with the same arguments.
abstract void	sort(long from, long to, ArrayComparator comparator, ArrayExchanger exchanger)	Sorts from..to-1 fragment of some array in increasing order.
abstract void	sortIndexes(int[] indexes, int from, int to, ArrayComparator comparator)	Sorts indexes[from..to-1] in increasing order.
void	sortIndexes(int[] indexes, int from, int to, ArrayComparator32 comparator)	Calls the previous sortIndexes(int[], int, int, ArrayComparator comparator) method with the same arguments.

Methods inherited from class java.lang.Object

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

Method Details

getInsertionSorter

public static ArraySorter getInsertionSorter()

Returns an instance of this class that implements insertion sorting algorithm. Do not use this algorithm for sorting large arrays - it will be very slow.

Returns:

implementation of insertion sorting algorithm.

getShellSorter

public static ArraySorter getShellSorter()

Returns an instance of this class that implements Shell sorting algorithm.

Returns:

implementation of Shell sorting algorithm.

getQuickSorter

public static ArraySorter getQuickSorter()

Returns an instance of this class that implements QuickSort sorting algorithm.

Returns:

implementation of Quick-Sort sorting algorithm.

areIndexesSorted

public static boolean areIndexesSorted(int[] indexes,
 int from,
 int to,
 ArrayComparator comparator)

Returns true if the from..to-1 range of indexes in some array is sorted. It means that for any k, from <= k < to, the following check returns false:

     comparator.less(indexes[k + 1], indexes[k])
 

Parameters:

indexes - indexes of elements in some data array.

from - index of the first checked element of indexes array, inclusive.

to - index of the last checked element of indexes array, exclusive.

comparator - comparator for checking order.

Returns:

true if the specified range of indexes is sorted.

areSorted

public static boolean areSorted(long from,
 long to,
 ArrayComparator comparator)

Returns true if the from..to-1 range of some array is sorted. It means that for any k, from <= k < to, the following check returns false:

     comparator.less(k + 1, k)
 

Parameters:

from - index of the first checked element of some data array, inclusive.

to - index of the last checked element of some data array, exclusive.

comparator - comparator for checking order.

Returns:

true if the specified range of the data array is sorted.

Throws:

NullPointerException - if comparator argument is null.

sortIndexes

public abstract void sortIndexes(int[] indexes,
 int from,
 int to,
 ArrayComparator comparator)

Sorts indexes[from..to-1] in increasing order. After sorting, for any i, j, from <= i < j < to, the following check will return false:

     comparator.less(indexes[j], indexes[i])
 

Sorting is based on exchanging elements of the passed indexes array.

Note: if some exception occurs while calling comparator.less method, the array stays shuffled ("partially" sorted). (The typical example is ClassCastException when the comparator tries to cast some objects to java.lang.Comparable type.) In other words, this method is non-atomic regarding this failure. Unlike this, sorting methods from java.util package never modify the passed array or collection in a case of some exceptions.

Parameters:

indexes - indexes of elements in some data array: this array will be sorted.

from - index of the first sorted element of indexes array, inclusive.

to - index of the last sorted element of indexes array, exclusive.

comparator - comparator for checking order.

Throws:

NullPointerException - if indexes or comparator argument is null.

IllegalArgumentException - if from > to, from < 0 or to > indexes.length

ClassCastException - may be thrown while calling methods of comparator during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

sortIndexes

public void sortIndexes(int[] indexes,
 int from,
 int to,
 ArrayComparator32 comparator)

Calls the previous sortIndexes(int[], int, int, ArrayComparator comparator) method with the same arguments.

Parameters:

indexes - indexes of elements in some data array: this array will be sorted.

from - index of the first sorted element of indexes array, inclusive.

to - index of the last sorted element of indexes array, exclusive.

comparator - comparator for checking order.

Throws:

NullPointerException - if indexes or comparator argument is null.

IllegalArgumentException - if from > to, from < 0 or to > indexes.length

ClassCastException - may be thrown while calling methods of comparator during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

sort

public abstract void sort(long from,
 long to,
 ArrayComparator comparator,
 ArrayExchanger exchanger)

Sorts from..to-1 fragment of some array in increasing order. After sorting, for any i, j, from <= i < j < to, the following check will return false:

     comparator.less(j, i)
 

Sorting is based on movement of elements of the sorted array with help of exchanger object, which must provide necessary access to the sorted data.

Note: some sorting algorithms, implemented by this class, may require, that exchanger must implement some additional interfaces, maybe a more powerful inheritor of ArrayExchanger interface, for example, allowing not only exchanging, but also copying elements. In such situation, this method throws UnsupportedOperationException, if exchanger argument does not implement necessary interface. The implementations, returned by getInsertionSorter(), getShellSorter(), getQuickSorter() (i.e. all implementation, available in the current version of this package), do not require this: it is enough to implement simple ArrayExchanger interface to use them. But, maybe, such algorithms will appear in future versions. You can verify, does this sorter require implementing additional interfaces by exchanger object, by isExchangingSorter() method: it will return false in this case.

Note: if some exception occurs while calling comparator or exchanger methods, the array stays shuffled ("partially" sorted). (The typical example is ClassCastException when the comparator tries to cast some objects to java.lang.Comparable type.) In other words, this method is non-atomic regarding this failure. Unlike this, sorting methods from java.util package never modify the passed array or collection in a case of some exceptions.

Parameters:

from - index of the first sorted element of some data array, inclusive.

to - index of the last sorted element of some data array, exclusive.

comparator - comparator for checking order of elements.

exchanger - exchanger for exchanging sorted elements.

Throws:

NullPointerException - if comparator or exchanger argument is null.

IllegalArgumentException - if from > to or from < 0

UnsupportedOperationException - if isExchangingSorter() returns false and the exchanger does not implement interfaces, necessary to perform sorting by this algorithm. Never occurs in the current version of this package.

ClassCastException - may be thrown while calling methods of comparator or exchanger during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

sort

public void sort(int from,
 int to,
 ArrayComparator32 comparator,
 ArrayExchanger32 exchanger)

Calls the previous sort(long, long, ArrayComparator, ArrayExchanger) method with the same arguments.

Parameters:

from - index of the first sorted element of some data array, inclusive.

to - index of the last sorted element of some data array, exclusive.

comparator - comparator for checking order of elements.

exchanger - exchanger for exchanging sorted elements.

Throws:

NullPointerException - if comparator or exchanger argument is null.

IllegalArgumentException - if from > to or from < 0

UnsupportedOperationException - if isExchangingSorter() returns false and the exchanger does not implement interfaces, necessary to perform sorting by this algorithm. Never occurs in the current version of this package.

ClassCastException - may be thrown while calling methods of comparator or exchanger during the sorting, if the types of the array elements are not appropriate (it is only a typical example of exception: those methods may throw another run-time exceptions).

isExchangingSorter

public boolean isExchangingSorter()

Returns true, if it is enough to implement the pure ArrayExchanger interface by the exchanger argument of sort(long, long, ArrayComparator, ArrayExchanger) method, or false, if that method requires exchanger to implement something else. If this method returns false, then it is possible that sort method will throw UnsupportedOperationException when its exchanger object does not implement some additional interface, necessary for this sorting algorithm.

In the current version of the package, this method always returns true. But this behaviour may change in future versions.

Returns:

whether sort method works properly if its exchanger implements only the simple ArrayExchanger interface.