O problema da bandeira holandesa

O seu trabalho é ordenar todas as cores da bandeira holandesa e a única primitiva fornecida é trocar duas linhas dadas. Adicionalmente, não deve criar quaisquer variáveis adicionais (exceto alguns índices).

Se pensar bem, pode ser feito em tempo linear, ondeordena uma linha a cada iteração do loop. Pode dar mais uma olhada no insertion sort, do qual o Dutch Flag sort é uma variação. A principal diferença é que tem 3 pontos de inserção e não apenas um...

Atravesse os seus dados, a guardar 3 índices: Observe que as células não-ordenadas ficam sempre entre afterBlue e beforeWhite.
Em cada passo da sua travessia, verifique a cor da célula em afterBlue e faça as mudanças necessárias. A condição de fim de loop é quando afterBlue se torna maior que beforeWhite.