com.sl.algorithms.sort.finitegroups

Class DutchNationalFlagSort<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.sort.finitegroups.DutchNationalFlagSort<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, SortingEngine<T>

public class DutchNationalFlagSort<T extends java.lang.Comparable>
extends java.lang.Object
implements SortingEngine<T>

A customized quick-sort, this algorithm is specific for cases when the data could be divided into 2-3 finite groups.
Reference 1
Reference 2
Time = O(N) and Space = O(1)

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
DutchNationalFlagSort(T _red, T _blue) (white) is the implicit middle layer; i.e.
DutchNationalFlagSort(T _red, T _white, T _blue) Dutch Flag

Method Summary

Modifier and Type	Method and Description
void	sort(T[] A) Approach:
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

DutchNationalFlagSort

public DutchNationalFlagSort(T _red,
                             T _white,
                             T _blue)

Dutch Flag

Parameters:

_red - (red) : value of first group

_white - (white) : value of middle group

_blue - (blue) : value of third group

DutchNationalFlagSort

public DutchNationalFlagSort(T _red,
                             T _blue)

(white) is the implicit middle layer;
i.e. red and blue values are fixed, everything else is white and can be any value hence will settle in the middle.

Parameters:

_red - value of first group

_blue - value of third (final) group

Method Detail

sort

public void sort(T[] A)

Approach:

There is just one check pointer 'w'. All steps depend on A[w]:
- swap with A[r] if it is red
- swap with A[b] if it is blue
- decrement w if it is white.
The variables r and b indicate red and blue boundaries such that all elements to the left of r are red and all elements to the right of b are blue.
It is clear that A swap occurs when A[w] is red or blue.

Specified by:

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

sortList

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

Specified by:

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