com.sl.algorithms.sort.finitegroups.integersorting

Class CountingSort<T extends java.lang.Integer>

java.lang.Object

com.sl.algorithms.sort.finitegroups.integersorting.CountingSort<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, SortingEngine<T>

Direct Known Subclasses:

RadixSort

public class CountingSort<T extends java.lang.Integer>
extends java.lang.Object
implements SortingEngine<T>

A stable special-purpose integer-sort algorithm with linear time and space complexity = O(N+kMax), the range of legit values in the array i.e. (0..kMax-1).

Inventor: Harold H Seward

Note: kMax is not significantly more than n (only then this algo is advantageous). While I have implemented for integers, counting-sort can be used for any elements as long as their key is an integer.

Reference Reading 0
Reference Reading 1
Reference Reading 2 (how stability is achieved)
Animation

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
CountingSort()

Method Summary

Modifier and Type	Method and Description
void	sort(T[] nums)
ListNode<T>	sortList(ListNode<T> list)

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

CountingSort

public CountingSort()

Method Detail

sort

public void sort(T[] nums)

Specified by:

sort in interface SortingEngine<T extends java.lang.Integer>

sortList

public ListNode<T> sortList(ListNode<T> list)

Specified by:

sortList in interface SortingEngine<T extends java.lang.Integer>