Three Way Partioning
- AKA Dutch National Flag algorithm
- Classing Two Pointer problem
The algorithm works by maintaining three pointers:
high. The low pointer points to the beginning of the array, the high pointer points to the end of the array, and the mid pointer starts at the beginning of the array and moves through it.
The idea behind the algorithm is to keep all the 0s before the low pointer, all the 2s after the high pointer, and all the 1s between the low and high pointers. The algorithm moves the mid pointer through the array, comparing the value at each position.
- If the value is 0, the element is swapped with the element at the low pointer, and the low and mid pointers are incremented.
- If the value is 2, the element is swapped with the element at the high pointer, and the high pointer is decremented.
- If the value is 1, the mid pointer is simply incremented.
The algorithm terminates when the mid pointer crosses the high pointer, indicating that all the elements have been processed and the array is sorted.