10 - (0-1-2) Sort

Problem¶

Sort an array containing only 0s, 1s, and 2s in a single pass without using any extra space (\(O(1)\) space).

Intuition¶

This problem is a classic application of the three-way partitioning algorithm proposed by Edsger Dijkstra. The idea is to maintain three sections in the array: 1. [0...low-1] containing all 0s. 2. [low...mid-1] containing all 1s. 3. [mid...high] containing unknown elements. 4. [high+1...n-1] containing all 2s.

By iterating through the array and swapping elements, we shrink the "unknown" section until the array is fully sorted.

Algorithm Steps¶

1. Initialize three pointers: low = 0, mid = 0, high = n - 1.
2. While mid <= high:
3. Case A: A[mid] == 0: Swap A[low] and A[mid]. Increment both low and mid.
4. Case B: A[mid] == 1: Simply increment mid.
5. Case C: A[mid] == 2: Swap A[mid] and A[high]. Decrement high. (Do not increment mid yet, as the swapped element needs to be checked).

Pseudocode¶

procedure sort012(A)
    low := 0, mid := 0, high := n - 1
    while mid <= high do
        if A[mid] == 0 then
            swap(A[low], A[mid])
            low++, mid++
        else if A[mid] == 1 then
            mid++
        else
            swap(A[mid], A[high])
            high--
    end while
end procedure

Java Code using JCF¶

Using a competitive programming structure (TCS NQT Style).

import java.util.*;

public class Main {
    /**
     * Dutch National Flag Algorithm Implementation
     */
    public static void sort012(List<Integer> list) {
        int low = 0, mid = 0, high = list.size() - 1;

        while (mid <= high) {
            switch (list.get(mid)) {
                case 0 -> {
                    Collections.swap(list, low, mid);
                    low++;
                    mid++;
                }
                case 1 -> mid++;
                case 2 -> {
                    Collections.swap(list, mid, high);
                    high--;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (sc.hasNextInt()) {
            int t = sc.nextInt();
            while (t-- > 0) {
                if (sc.hasNextInt()) {
                    int n = sc.nextInt();
                    List<Integer> list = new ArrayList<>();
                    for (int i = 0; i < n; i++) {
                        if (sc.hasNextInt()) {
                            list.add(sc.nextInt());
                        }
                    }
                    sort012(list);
                    for (int i = 0; i < list.size(); i++) {
                        System.out.print(list.get(i) + (i == list.size() - 1 ? "" : " "));
                    }
                    System.out.println();
                }
            }
        }
        sc.close();
    }
}

Sample Input and Output¶

Input:

2
6
0 1 2 2 1 0
5
2 0 2 1 1

Output:

0 0 1 1 2 2
0 1 1 2 2

Complexity¶

• Single Pass: Performs exactly one pass over the array.
• In-place: No extra space used besides pointers.
• Stable: Generally No (swapping can change the relative order of equal 0s or 2s).

Example and Dry Run¶

Input: [2, 0, 2, 1, 1]
Pointers: low=0, mid=0, high=4

1. A[0] = 2: Swap A[0], A[4]. high=3. Array: [1, 0, 2, 1, 2]
2. A[0] = 1: mid=1. Array: [1, 0, 2, 1, 2]
3. A[1] = 0: Swap A[0], A[1]. low=1, mid=2. Array: [0, 1, 2, 1, 2]
4. A[2] = 2: Swap A[2], A[3]. high=2. Array: [0, 1, 1, 2, 2]

5. A[2] = 1: mid=3. Loop ends (mid > high).

6. Result: [0, 1, 1, 2, 2]

Variations¶

1. Sort 0-1 (Two Pointers): Simpler version where you only have two distinct elements.
2. Move Negative Numbers to Front: Similar partitioning logic for positive/negative numbers.
3. Partitioning around a Pivot: Used in Quick Sort (though Quick Sort usually partitions into 2 sections, 3-way partitioning is an optimization).