O problema da bandeira holandesa

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

Se você pensar com carinho, isto pode ser feito em tempo linear, onde você ordena uma linha a cada iteração do loop. Você pode querer dar mais uma olhada no insertion sort, do qual o Dutch Flag sort é uma variação. A principal diferença é que você tem 3 pontos de inserção, e não apenas um...

Atravesse seus dados, guardando 3 índices: Observe que as células não-ordenadas ficam sempre entre afterBlue e beforeWhite.
Em cada passo de 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.