The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. ― Donald E. Knuth

Algorithms

Arrays & Strings

Problem :-
Sort an array of 0s, 1s & 2s, i.e element at each index of the array is either 0, 1 or 2 and we need to place all 0s first, then 1s and finally all 2s.

Solution :-
After implementing an efficient algorithm to sort an array of 0s & 1s, a very common follow up question is to sort the array of 0s, 1s & 2s.
Again, we won't consider the counting approach rather would go for a 1 pass approach in which the sorting would be done by traversing the array only once.
We need to divide the array into 3 parts.
Say 'i' points to index 0 & 'j' points to index n-1.
We will start traversing from the end of array & 'k' is the iterator starting at index n-1.
If arr(k) is 0, then swap arr(i) & arr(k) and increment 'i'.
If arr(k) is 2, then swap arr(j) & arr(k) and decrement 'j'.
If arr(k) is 1, then don't do anything, simple decrement the iterator 'k'.
In this way, the array will be divided into 3 portions.