Sort an array of 0s, 1s and 2s
Problem
The array contains only 0, 1 and 2. Sort it in place in a single pass, without a library sort and without counting then rewriting (the Dutch National Flag problem).
Example 1
Input: [0, 2, 1, 2, 0] Output: [0, 0, 1, 2, 2]
Also asked as: Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo
Test cases
Case 1
Input: [0,2,1,2,0] Expected: [0,0,1,2,2]
Case 2
Input: [2,0,1] Expected: [0,1,2]
Case 3
Input: [1,1,1] Expected: [1,1,1]
Case 4
Input: [] Expected: []
View solutionHide solution2 approaches
1. Dutch National Flag (one pass)
Time O(n)Space O(1)
Three pointers: everything before `low` is 0, after `high` is 2, `mid` scans the unknown middle.
function sort012(a) { let low = 0, mid = 0, high = a.length - 1; while (mid <= high) { if (a[mid] === 0) { [a[low], a[mid]] = [a[mid], a[low]]; low++; mid++; } else if (a[mid] === 1) mid++; else { [a[mid], a[high]] = [a[high], a[mid]]; high--; } } return a;}2. Counting sort
Time O(n)Space O(1)
Count 0s/1s/2s, then overwrite. Two passes, trivial to reason about.
function sort012(a) { const c = [0, 0, 0]; for (const x of a) c[x]++; let i = 0; for (let v = 0; v < 3; v++) while (c[v]-- > 0) a[i++] = v; return a;}