public class PolishNationalFlagSort<T extends java.lang.Comparable> extends java.lang.Object implements SortingEngine<T>
ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET
Constructor and Description |
---|
PolishNationalFlagSort(T _white) |
PolishNationalFlagSort(T _white,
T _red)
|
Modifier and Type | Method and Description |
---|---|
void |
sort(T[] A)
Approach: |
ListNode<T> |
sortList(ListNode<T> list) |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
checkArray, checkIntArray, checkList
public PolishNationalFlagSort(T _white, T _red)
_white
- : value of first group_red
- : value of second grouppublic PolishNationalFlagSort(T _white)
_white
- : primary value for sort.public void sort(T[] A)
The two indices 'w' and 'r' keep track of the white and red block
boundaries, respectively.
First, we scan from the left end of the array by incrementing 'w'
until we find a !white element, and we scan from the right end of the array by decrementing 'r'
until we find a white element. We then exchange the two elements. Continue this way until 'w'
and 'r' meet.
Note that the scanning process is the same as that of the partition procedure
of QuickSort
or QuickSelectMedianFinder
.
sort
in interface SortingEngine<T extends java.lang.Comparable>