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. Dadas bolas de estos tres colores dispuestas aleatoriamente en una línea (no importa cuántas bolas haya), la tarea es organizarlas 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 es de interés para el diseño de algoritmos de ordenamiento ; en particular, las variantes del algoritmo quicksort que deben ser robustas a los elementos repetidos pueden utilizar una función de partición de tres vías que agrupe los elementos menores que una clave dada (rojo), iguales a la clave (blanco) y mayores que la clave (azul). Existen varias soluciones que tienen características de rendimiento variables, adaptadas para ordenar matrices con cantidades pequeñas o grandes de elementos repetidos. [3]
Este problema también puede verse en términos de reorganización de elementos de una matriz . Supongamos que cada uno de los elementos posibles se puede clasificar exactamente en una de tres categorías (inferior, medio y superior). Por ejemplo, si todos los elementos están en 0 ... 1, el inferior se puede definir como elementos en 0 ... 0,25 (sin incluir 0,25), el medio como 0,25 ... 0,5 (sin incluir 0,5) y el superior como 0,5 y mayor. (La elección de estos valores ilustra que las categorías no necesitan ser rangos iguales). El problema es entonces producir una matriz tal que todos los elementos "inferiores" vengan antes (tengan un índice menor que el índice de) todos los elementos "intermedios", que vienen antes de todos los elementos "superiores".
Un algoritmo consiste en hacer que el grupo superior crezca hacia abajo desde la parte superior de la matriz, el grupo inferior crezca hacia arriba desde la parte inferior y mantener el grupo del medio justo por encima de la parte inferior. El algoritmo indexa tres ubicaciones: la parte inferior del grupo superior, la parte superior del grupo inferior y la parte superior del grupo del medio. Los elementos que aún no se han ordenado se encuentran entre el grupo del medio y el grupo superior. [4] En cada paso, examine el elemento justo por encima del medio. Si pertenece al grupo superior, cámbielo por el elemento justo debajo de la parte superior. Si pertenece al grupo inferior, cámbielo por el elemento justo encima de la parte inferior. Si está en el medio, déjelo. Actualice el índice apropiado. La complejidad es Θ(n) movimientos y exámenes. [1]
El siguiente pseudocódigo para particionamiento de tres vías que supone una indexación de matriz basada en cero fue propuesto por el propio Dijkstra. [2] Utiliza tres índices i , j y k , manteniendo invariante que i ≤ j ≤ k .
procedimiento partición-de-tres-vías(A : matriz de valores, mid : valor): yo ← 0 y ← 0 k ← tamaño de A - 1 mientras j <= k: si A[j] < mid: intercambia A[i] y A[j] yo ← yo + 1 j ← j + 1 De lo contrario, si A[j] > mid: intercambia A[j] y A[k] k ← k-1 demás : j ← j + 1
Este artículo incorpora material de dominio público de Paul E. Black. «Bandera nacional holandesa». Diccionario de algoritmos y estructuras de datos . NIST .