Problema da bandeira dos Países Baixos

O problema da bandeira da Holanda é um desafio de programação proposto por Edsger Dijkstra em 1976 relacionado a algoritmos de ordenamento. Supõe-se que numa urna sejam postas bolas pintadas de azul, vermelho ou branco (cores da bandeira da Holanda) em qualquer quantidade, desde que haja uma de cada cor. O problema propõe que o algoritmo deva ser capaz de agrupar todas as bolas de uma mesma cor em sequência e as sequências de cores estejam ordenadas. Desta maneira, no vetor ordenado das bolas desta urna estariam posicionadas primeiro todas as vermelhas, depois todas as brancas e, por fim, todas as azuis. No entanto, o algoritmo é limitado a acessar a cor de cada bola apenas uma única vez, visando a um menor número de comparações, acessos e, por conseguinte, um crescimento assintótico menos punitivo.

Bandeira da Holanda.

A maioria das respostas deste desafio é bastante familiar com o algoritmo do quicksort. Segue a solução proposta (adaptada) pelo próprio Dijkstra:

vetor urna[N]  // sendo N o tamanho do array
ver = 1, bra = N, azu = N
// ver é o índice do último elemento da sequência de bolas vermelhas
// bra é o índice do último elemento da sequência de bolas brancas
// azu é o índice do primeiro elemento da sequência de bolas azuis 

enquanto b >= v:
    cor = checar cor de urna[bra]
    se cor é vermelha:
        trocar(urna[ver], urna[bra])
        ver = ver + 1
    senao-se cor é branca:
        bra = bra - 1
    senao-se cor é azul:
        trocar(urna[bra], urna[azul])
        bra = bra - 1
        azu = azu - 1