Dutch national flag sorting problem
I recently came upon an interview question called the Dutch national flag problem that required me to sort an array of 1's, 2's, and 3's in order while only traversing the array once. So for example if the array were
a = [1,3,3,2,1]
then after iterating through the array only once I should get
a = [1,1,2,3,3]
How can I write an algorithm to search and sort through the array only once without using any other data structures?