Problema com a bandeira nacional holandesa - Dutch national flag problem
O problema da bandeira nacional holandesa é um problema de programação de ciência da computação proposto por Edsger Dijkstra . A bandeira da Holanda consiste em três cores: vermelho, branco e azul. Dadas bolas dessas três cores dispostas aleatoriamente em uma linha (não importa quantas bolas existam), a tarefa é organizá-las de forma que todas as bolas da mesma cor fiquem juntas e seus grupos de cores coletivos estejam na ordem correta.
A solução para este problema é de interesse para o projeto de algoritmos de classificação ; em particular, as variantes do algoritmo de classificação rápida que devem ser robustas a elementos repetidos podem usar uma função de particionamento de três vias que agrupa itens menores que uma determinada chave (vermelho), iguais à chave (branco) e maiores que a chave (azul) . Existem várias soluções com características de desempenho variáveis, adaptadas para classificar matrizes com um número pequeno ou grande de elementos repetidos.
O caso da matriz
Esse problema também pode ser visto em termos de reorganização de elementos de uma matriz . Suponha que cada um dos elementos possíveis pudesse ser classificado em exatamente uma das três categorias (inferior, intermediário e superior). Por exemplo, se todos os elementos estão em 0 ... 1, o fundo pode ser definido como elementos em 0 ... 0,25 (não incluindo 0,25), o meio como 0,25 ... 0,5 (não incluindo 0,5) e o topo como 0,5 e superior. (A escolha desses valores ilustra que as categorias não precisam ser intervalos iguais). O problema é, então, produzir um array de forma que todos os elementos "inferiores" venham antes (tenham um índice menor que o índice de) todos os elementos "intermediários", que venham antes de todos os elementos "superiores".
Um algoritmo é fazer com que o grupo do topo cresça da parte superior da matriz, o grupo da parte inferior cresça da parte inferior e mantenha o grupo do meio logo acima da parte inferior. O algoritmo indexa três locais, a parte inferior do grupo superior, a parte superior do grupo inferior e a parte superior do grupo intermediário. Os elementos que ainda não foram classificados ficam entre o grupo do meio e o grupo superior. Em cada etapa, examine o elemento logo acima do meio. Se ele pertencer ao grupo superior, troque-o pelo elemento logo abaixo do topo. Se ele pertencer à parte inferior, troque-o pelo elemento logo acima da parte inferior. Se estiver no meio, deixe-o. Atualize o índice apropriado. A complexidade é Θ (n) movimentos e exames.
Pseudo-código
O seguinte pseudocódigo para particionamento de três vias, que assume a indexação de matriz baseada em zero, foi proposto pelo próprio Dijkstra. Ele usa três índices i , j e k , mantendo o invariante que i ≤ j ≤ k .
- As entradas de 0 até (mas não incluindo) i são valores inferiores a meio ,
- entradas de i até (mas não incluindo) j são valores iguais a meio ,
- entradas de j até (e incluindo) k são valores ainda não classificados, e
- entradas de k + 1 até o final da matriz são valores maiores que mid .
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A - 1
while j <= k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[k]
k ← k - 1
else:
j ← j + 1
Veja também
Referências
links externos
- Explicação e execução explicativa interativa do algoritmo , classificando duas ou três cores