Algorithms in Go: Dutch National Flag

[Dorval]

We also can count three counters on the first pass and fill the right values on the second pass.

[aydu]

Let me check if I got the idea.

Let's say we have [1, 2, 1, 0]
In the first pass, we count the number of occurrences for zeroes, ones and twos:

0:0, 1:2, 2:1

And in the second run, we restore the array. Did I get the idea?

If I understood you correctly, then the described algorithm does not work in-place, right?

EDIT: I noted that my post doesn't emphasize that the provided solution works in-place. Thanks for the remark, updated the article.

[Dorval]

Counters will be 0:1, 1:2, 2:1.
And then we just overwrite our existing array so this algorithm will work in place too.

[aydu]

Thanks, got it.