Problema con la bandera nacional holandesa

El problema de la bandera nacional holandesa ^{[ 1 ]} es un problema computacional propuesto por Edsger Dijkstra . ^{[ 2 ]} La bandera de los Países Bajos consta de tres colores: rojo, blanco y azul. Dado un conjunto de bolas de estos tres colores dispuestas aleatoriamente en línea (sin importar cuántas bolas haya), la tarea consiste en ordenarlas de manera que todas las bolas del mismo color estén juntas y sus grupos de colores colectivos estén en el orden correcto.

La solución a este problema resulta de interés para el diseño de algoritmos de ordenación ; en particular, las variantes del algoritmo Quicksort que deben ser robustas ante elementos repetidos pueden utilizar una función de partición triple que agrupe los elementos menores que una clave dada (rojo), iguales a la clave (blanco) y mayores que la clave (azul). Existen varias soluciones con características de rendimiento variables, adaptadas a la ordenación de matrices con un número pequeño o grande de elementos repetidos. ^{[ 3 ]}

Este problema también puede verse como una reorganización de los elementos de un arreglo . Supongamos que cada uno de los elementos posibles se puede clasificar en una de tres categorías (inferior, media y superior). Por ejemplo, si todos los elementos están entre 0 y 1, la categoría inferior podría definirse como los elementos entre 0 y 0,25 (sin incluir 0,25), la categoría media como los elementos entre 0,25 y 0,5 (sin incluir 0,5) y la categoría superior como los elementos de 0,5 o mayores. (La elección de estos valores ilustra que las categorías no tienen por qué tener rangos iguales). El problema consiste entonces en crear un arreglo tal que todos los elementos inferiores aparezcan antes (tengan un índice menor que el índice de) todos los elementos medios, que a su vez aparezcan antes que todos los elementos superiores.

Un algoritmo consiste en que el grupo superior crezca hacia abajo desde la parte superior del arreglo, el grupo inferior crezca hacia arriba desde la parte inferior y el grupo medio se mantenga justo encima de la parte inferior. El algoritmo indexa tres posiciones: la parte inferior del grupo superior, la parte superior del grupo inferior y la parte superior del grupo medio. Los elementos que aún no se han ordenado se encuentran entre el grupo medio y el superior. ^{[ 4 ]} En cada paso, se examina el elemento que se encuentra justo encima del medio. Si pertenece al grupo superior, se intercambia con el elemento que se encuentra justo debajo de la parte superior. Si pertenece a la parte inferior, se intercambia con el elemento que se encuentra justo encima de la parte inferior. Si está en el medio, se deja. Se actualiza el índice correspondiente. La complejidad es Θ(n) movimientos y exámenes. ^{[ 1 ]}

procedimiento de partición tridireccional(A: matriz de valores, mid: valor): yo ← 0 j ← 0 k ← tamaño de A - 1 mientras j <= k: si A[j] < medio: intercambiar A[i] y A[j] i ← i + 1 j ← j + 1 else if A[j] > mid: intercambiar A[j] y A[k] k ← k - 1 demás : j ← j + 1

• Bandera estadounidense clasificada
• Bandera de los Países Bajos

• Explicación y ejecución interactiva del algoritmo para ordenar dos o tres colores.