Dutch National Flag Problem
An algorithm for sorting an array of 0s, 1s, and 2s in a single pass.
Visualization
Details
Analogy
The name comes from the task of sorting the red, white, and blue stripes of the Dutch flag. Imagine you have a random sequence of red, white, and blue balls. You want to arrange them in the correct flag order. You can do this in one pass by maintaining three pointers: one for the 'red' section, one for the 'blue' section, and one for the current ball you are looking at. Based on the current ball's color, you swap it into the correct section.
Purpose
To partition an array into three sections based on a pivot value (0s, 1s, and 2s). It's a classic example of a three-way partitioning problem.
Use Cases
A key subroutine in some sorting algorithms, like a variant of Quick Sort that handles duplicate keys efficiently.
Algorithm Steps
low = 0, mid = 0, high = n-1
while mid <= high:
if arr[mid] == 0:
swap arr[low] and arr[mid]
low++, mid++
else if arr[mid] == 1:
mid++
else: // arr[mid] == 2
swap arr[mid] and arr[high]
high--
Explanation
What's Happening?
Initial array. Pointers: low=0, mid=0, high=5. Current element is arr[mid]=2.
Code Implementation
def sort_012(arr):
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == 1:
mid += 1
else: # arr[mid] == 2
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
return arr