DATA STRUCTURES • ALGORITHMS

Sort Colors

Also known as the Dutch National Flag problem. Sorting an array of three distinct values (e.g., 0s, 1s, and 2s) in linear time using constant space.

Time

O(N)

Space

O(1)

Key Principle 1

Three-pointer technique

Key Principle 2

Single pass requirement

Key Principle 3

Low, Mid, and High pointers

Key Principle 4

Optimal in-place partition

SORT_COLORS_LAB
ARRAY (0,1,2):
Current Step
Dutch National Flag Algorithm: Sorting 0s, 1s, and 2s.
Playback
Pointer Tracking ⠿
LOW0
MID0
HIGH5
STATUSInit
DNF Algorithm ⠿
1int low = 0, mid = 0, high = n - 1;
2while (mid <= high) {
3    if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
4    else if (arr[mid] == 1) mid++;
5    else swap(arr[mid], arr[high--]);
6}
2
LOW
MID
0
[1]
2
[2]
1
[3]
1
[4]
0
HIGH

Loading Lab...