Solution Review: Partitioning of 0s, 1s and 2s
Explore the partitioning technique to sort arrays containing 0s, 1s, and 2s by using three indices for in-place swaps. Learn how the algorithm efficiently traverses the array with O(n) time complexity and why this sorting approach is effective.
We'll cover the following...
We'll cover the following...
Solution
The basic approach is to use three indices. The first is left, the second is right, and the third is i that is used to traverse the array. The index on the left begins at 0, while the index on the right begins at n-1. When we discover a 0 in the array, we swap it with the start and increment start. And anytime we come across a ...