Package com.aoindustries.util.sort

Class IntegerRadixSort

java.lang.Object

com.aoindustries.util.sort.IntegerRadixSort

All Implemented Interfaces:

IntegerSortAlgorithm, SortAlgorithm<Number>

public final class IntegerRadixSort
extends Object

A radix sort implementation for numeric data, sorting by its integer representation. Although a very different implementation, this topic is discussed at http://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html with source provided at https://github.com/gorset/radix/blob/master/Radix.java. TODO: For concurrent implementation: Might get better performance (due to cache locality of reference) by flattening the two-dimensional fixed dimensions of the arrays into a single dimension. TODO: For concurrent implementation: Might also consider changing the row/column order of the multi-dimensional arrays to help cache interaction. Might get better throughput when hit the cache wall where performance drops considerably.

Author:

AO Industries, Inc.

Method Summary

Modifier and Type	Method	Description
protected static int	get(int[] array, int i, SortStatistics stats)
protected static int	get(IntList list, int i, SortStatistics stats)
protected static <T> T	get(List<T> list, int i, SortStatistics stats)
protected static <T> T	get(T[] array, int i, SortStatistics stats)
static IntegerRadixSort	getInstance()	Gets the default IntegerRadixSort using the default executor service.
static IntegerRadixSort	getInstance(ExecutorService executor)	Gets a IntegerRadixSort that uses the provided ExecutorService.
static IntegerRadixSort	getSingleThreadedInstance()	Gets a single-threaded instance of IntegerRadixSort, that will not ever sort concurrently.
boolean	isStable()	Checks if this is a stable sort.
protected static void	set(int[] array, int i, int value, SortStatistics stats)
protected static void	set(IntList list, int i, int value, SortStatistics stats)
protected static <T> void	set(List<T> list, int i, T O, SortStatistics stats)
protected static <T> void	set(T[] array, int i, T O, SortStatistics stats)
void	sort(int[] array)
void	sort(int[] array, SortStatistics stats)
void	sort(IntList list)
void	sort(IntList list, SortStatistics stats)
<N extends Number> void	sort(List<N> list, SortStatistics stats)
<T extends E> void	sort(List<T> list)
<N extends Number> void	sort(N[] array, SortStatistics stats)
<T extends E> void	sort(T[] array)
protected static void	swap(int[] array, int i, int j, SortStatistics stats)
protected static void	swap(IntList list, int i, int j, SortStatistics stats)
protected static <T> void	swap(List<T> list, int i, int j, SortStatistics stats)
protected static <T> void	swap(T[] array, int i, int j, SortStatistics stats)

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.aoindustries.util.sort.SortAlgorithm

sort, sort

Method Detail

getInstance

public static IntegerRadixSort getInstance()

Gets the default IntegerRadixSort using the default executor service. This will use concurrency where appropriate (long lists/arrays on multi-core systems).

getSingleThreadedInstance

public static IntegerRadixSort getSingleThreadedInstance()

Gets a single-threaded instance of IntegerRadixSort, that will not ever sort concurrently. As the determination of when to use concurrency should avoid any potential downfalls, it is recommended to use the default instance from getInstance for most scenarios.

See Also:

getInstance()

getInstance

public static IntegerRadixSort getInstance(ExecutorService executor)

Gets a IntegerRadixSort that uses the provided ExecutorService. If the executor service is null, concurrency is disabled.

isStable

public boolean isStable()

Description copied from interface: SortAlgorithm

Checks if this is a stable sort. A stable sort will keep elements with equal values in their same relative order.

sort

public <N extends Number> void sort(List<N> list,
                                    SortStatistics stats)

Specified by:

sort in interface SortAlgorithm<Number>

sort

public <N extends Number> void sort(N[] array,
                                    SortStatistics stats)

Specified by:

sort in interface SortAlgorithm<Number>

sort

public void sort(IntList list,
                 SortStatistics stats)

Specified by:

sort in interface IntegerSortAlgorithm

sort

public void sort(int[] array,
                 SortStatistics stats)

Specified by:

sort in interface IntegerSortAlgorithm

sort

public void sort(IntList list)

Specified by:

sort in interface IntegerSortAlgorithm

sort

public void sort(int[] array)

Specified by:

sort in interface IntegerSortAlgorithm

get

protected static int get(IntList list,
                         int i,
                         SortStatistics stats)

get

protected static int get(int[] array,
                         int i,
                         SortStatistics stats)

set

protected static void set(IntList list,
                          int i,
                          int value,
                          SortStatistics stats)

set

protected static void set(int[] array,
                          int i,
                          int value,
                          SortStatistics stats)

swap

protected static void swap(IntList list,
                           int i,
                           int j,
                           SortStatistics stats)

swap

protected static void swap(int[] array,
                           int i,
                           int j,
                           SortStatistics stats)

sort

public <T extends E> void sort(List<T> list)

Specified by:

sort in interface SortAlgorithm<E>

sort

public <T extends E> void sort(T[] array)

Specified by:

sort in interface SortAlgorithm<E>

get

protected static <T> T get(List<T> list,
                           int i,
                           SortStatistics stats)

get

protected static <T> T get(T[] array,
                           int i,
                           SortStatistics stats)

set

protected static <T> void set(List<T> list,
                              int i,
                              T O,
                              SortStatistics stats)

set

protected static <T> void set(T[] array,
                              int i,
                              T O,
                              SortStatistics stats)

swap

protected static <T> void swap(List<T> list,
                               int i,
                               int j,
                               SortStatistics stats)

swap

protected static <T> void swap(T[] array,
                               int i,
                               int j,
                               SortStatistics stats)