org.amino.alg.sort
Class QuickSorter

java.lang.Object
  org.amino.alg.sort.AbstractSorter
      org.amino.alg.sort.DefaultSorter
          org.amino.alg.sort.QuickSorter

All Implemented Interfaces:

Sorter

Direct Known Subclasses:

ParallelQuickSorterWorkStealing

public class QuickSorter
extends DefaultSorter

This class implements the basic sequential quicksort algorithm. Provides functions to sort in both ascending and descending order.

Field Summary

protected Sorter	is Insert sorter.
protected static int	IS_THRESHOLD Threshold if used to decide if quick sort is needed.

Constructor Summary

QuickSorter()

Method Summary

protected static int	median(byte[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(char[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(double[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(float[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(int[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(long[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	median(short[] data, int ax, int bx, int cx) Routine to find pivot element.
protected static int	ninther(int[] data, int first, int mid, int last) Routine to find pivot element.
void	reverse(byte[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(char[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(double[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(float[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(int[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(long[] a, int from, int to) Sort array using reverse natural (descending) order.
void	reverse(short[] a, int from, int to) Sort array using reverse natural (descending) order.
protected int	selectPivot(byte[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(char[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(double[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(float[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(int[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(long[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
protected int	selectPivot(short[] a, int fromIndex, int toIndex) Select a pivot element from the given array section.
void	sort(byte[] a, int from, int to)
void	sort(char[] a, int from, int to)
void	sort(double[] a, int from, int to)
void	sort(float[] a, int from, int to)
void	sort(int[] a, int from, int to)
void	sort(long[] a, int from, int to)
void	sort(short[] a, int from, int to)

Methods inherited from class org.amino.alg.sort.DefaultSorter

reverse, reverse, sort, sort, sort, sort, sort, sort, sortp

Methods inherited from class org.amino.alg.sort.AbstractSorter

reverse, reverse, reverse, reverse, reverse, reverse, reverse, reverse, reverse, sort, sort, sort, sort, sort, sort, sort, sort, sort, swap, swap, swap, swap, swap, swap, swap, swap, swapIfGreater, swapIfGreater, swapIfGreater, swapIfGreater, swapIfGreater, swapIfGreater, swapIfGreater, swapIfGreater, swapIfLess, swapIfLess, swapIfLess, swapIfLess, swapIfLess, swapIfLess, swapIfLess, swapIfLess

Methods inherited from class java.lang.Object

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

Field Detail

IS_THRESHOLD

protected static final int IS_THRESHOLD

Threshold if used to decide if quick sort is needed. If the length of the array section is small, use an insertion sort.

See Also:

Constant Field Values

is

protected Sorter is

Insert sorter.

Constructor Detail

QuickSorter

public QuickSorter()

Method Detail

median

protected static int median(byte[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is byte array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(char[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is charater array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(short[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is short array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(int[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is int array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(long[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is long array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(float[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is float array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

median

protected static int median(double[] data,
                            int ax,
                            int bx,
                            int cx)

Routine to find pivot element.

Parameters:

data - is double array to be sorted

ax - is the first index

bx - is the mid index

cx - is the last index

Returns:

the median number

ninther

protected static int ninther(int[] data,
                             int first,
                             int mid,
                             int last)

Routine to find pivot element.

Parameters:

data - is int array to be sorted

first - is the first index

mid - is the mid index

last - is the last index

Returns:

the median number

selectPivot

protected int selectPivot(int[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(byte[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(char[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(short[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(long[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(float[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

selectPivot

protected int selectPivot(double[] a,
                          int fromIndex,
                          int toIndex)

Select a pivot element from the given array section.

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

Returns:

index of a pivot element

sort

public void sort(byte[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the byte array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(byte[], int, int)

sort

public void sort(char[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the character array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(byte[], int, int)

sort

public void sort(short[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the short array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(short[], int, int)

sort

public void sort(int[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the int array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(short[], int, int)

sort

public void sort(long[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the long array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(short[], int, int)

sort

public void sort(float[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the float array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(short[], int, int)

sort

public void sort(double[] a,
                 int from,
                 int to)

Specified by:

sort in interface Sorter

Overrides:

sort in class DefaultSorter

Parameters:

a - is the double array to be sorted in an ascending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

See Also:

Arrays.sort(short[], int, int)

reverse

public void reverse(byte[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the byte array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(char[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the character array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(short[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the short array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(int[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the int array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(long[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the long array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(float[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the float array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted

reverse

public void reverse(double[] a,
                    int from,
                    int to)

Sort array using reverse natural (descending) order.

Specified by:

reverse in interface Sorter

Overrides:

reverse in class DefaultSorter

Parameters:

a - is the double array to be sorted in a descending order

from - is the start index of array to be sorted

to - is the end index of array to be sorted