Package com.irurueta.sorting

Class QuicksortSorter<T>

java.lang.Object

com.irurueta.sorting.Sorter<T>

com.irurueta.sorting.QuicksortSorter<T>

Type Parameters:

T - Type of instances being sorted.

This class is based on algorithm found at Numerical Recipes. 3rd Edition. Cambridge Press. Chapter 8. p. 424 Sedgewick, R. 1978. "Implementing Quicksort Programs", Communications of the ACM, vol. 21, pp. 847-857.

Direct Known Subclasses:

SystemSorter

public class QuicksortSorter<T>
extends Sorter<T>

Sorts instances of type T in provided arrays using Quicksort method.

Field Summary

Fields

Modifier and Type	Field	Description
private static final int	M	Constant defining size of smallest subarrays to be ordered using straight insertion.
private static final int	NSTACK	Constant defining size of stack.

Fields inherited from class com.irurueta.sorting.Sorter

DEFAULT_SORTING_METHOD

Constructor Summary

Constructors

Constructor	Description
QuicksortSorter()

Method Summary

Modifier and Type	Method	Description
SortingMethod	getMethod()	Returns sorting method of this class.
void	sort(double[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(float[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(int[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(long[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(double[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(float[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(int[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(long[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
private void	swapIndices(int[] indices, int posA, int posB)	Swaps values in array of indices at locations posA and posB.

Methods inherited from class com.irurueta.sorting.Sorter

create, create, getInitialIndicesVector, median, median, median, median, median, median, median, median, median, median, median, median, select, select, select, select, select, select, select, select, select, select, select, select, sort, sort, sort, sort, sort, sort, sort, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, swap, swap, swap, swap, swap

Methods inherited from class java.lang.Object

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

Field Details

M

private static final int M

Constant defining size of smallest subarrays to be ordered using straight insertion.

See Also:

• Constant Field Values

NSTACK

private static final int NSTACK

Constant defining size of stack.

See Also:

• Constant Field Values

Constructor Details

QuicksortSorter

public QuicksortSorter()

Method Details

sort

public void sort(T[] array,
 int fromIndex,
 int toIndex,
 Comparator<T> comparator)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Specified by:

sort in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

comparator - Determines whether an element is greater or lower than another one.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(T[] array,
 int fromIndex,
 int toIndex,
 Comparator<T> comparator)
                      throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Specified by:

sortWithIndices in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

comparator - Determines whether an element is greater or lower than another one.

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

getMethod

public SortingMethod getMethod()

Returns sorting method of this class.

Specified by:

getMethod in class Sorter<T>

Returns:

Sorting method.

sort

public void sort(double[] array,
 int fromIndex,
 int toIndex)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Specified by:

sort in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(double[] array,
 int fromIndex,
 int toIndex)
                      throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Specified by:

sortWithIndices in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(float[] array,
 int fromIndex,
 int toIndex)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Specified by:

sort in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(float[] array,
 int fromIndex,
 int toIndex)
                      throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Specified by:

sortWithIndices in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(int[] array,
 int fromIndex,
 int toIndex)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Specified by:

sort in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(int[] array,
 int fromIndex,
 int toIndex)
                      throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Specified by:

sortWithIndices in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(long[] array,
 int fromIndex,
 int toIndex)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Specified by:

sort in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(long[] array,
 int fromIndex,
 int toIndex)
                      throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Specified by:

sortWithIndices in class Sorter<T>

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

swapIndices

private void swapIndices(int[] indices,
 int posA,
 int posB)

Swaps values in array of indices at locations posA and posB.

Parameters:

indices - array containing indices to be swapped.

posA - Location to be swapped.

posB - Location to be swapped.