Problema de la bandera nacional holandesa - Dutch national flag problem

Para el artículo sobre la bandera nacional holandesa, consulte Bandera de los Países Bajos .
La bandera nacional holandesa

El problema de la bandera nacional holandesa es un problema de programación informática propuesto por Edsger Dijkstra . La bandera de los Países Bajos consta de tres colores: rojo, blanco y azul. Dadas las bolas de estos tres colores dispuestas al azar 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 diseñar algoritmos de clasificación ; en particular, las variantes del algoritmo de ordenación rápida que deben ser robustas a elementos repetidos pueden usar una función de partición de tres vías que agrupa elementos menores que una clave dada (rojo), igual a la clave (blanco) y mayor que la clave (azul) . Existen varias soluciones que tienen características de rendimiento variables, diseñadas para ordenar matrices con cantidades pequeñas o grandes de elementos repetidos.

El caso de la matriz

Este problema también se puede ver en términos de reorganización de elementos de una matriz . Suponga que cada uno de los elementos posibles podría clasificarse exactamente en una de tres categorías (inferior, medio y superior). Por ejemplo, si todos los elementos están en 0 ... 1, la parte inferior podría definirse como elementos en 0 ... 0.25 (sin incluir 0.25), la mitad como 0.25 ... 0.5 (sin incluir 0.5) y la parte 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 es hacer que el grupo superior crezca hacia abajo desde la parte superior de la matriz, el grupo inferior crezca desde la parte inferior y mantenga el grupo del medio justo 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 intermedio. Los elementos que aún no se han clasificado se encuentran entre el grupo medio y el superior. En cada paso, examine el elemento que se encuentra justo encima del medio. Si pertenece al grupo superior, cámbielo por el elemento que está justo debajo de la parte superior. Si pertenece a la parte inferior, cámbielo por el elemento que está 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.

Pseudocódigo

El siguiente pseudocódigo para la partición de tres vías que asume la indexación de matrices de base cero fue propuesto por el propio Dijkstra. Utiliza tres índices i , j y k , manteniendo el invariante que i ≤ j ≤ k .

  • Las entradas desde 0 hasta (pero sin incluir) i son valores menores que mid ,
  • las entradas de i hasta (pero sin incluir) j son valores iguales a mid ,
  • las entradas de j hasta (inclusive) k son valores que aún no se han ordenado, y
  • las entradas desde k + 1 hasta el final de la matriz son valores mayores 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

Ver también

Referencias

enlaces externos