Problema della bandiera nazionale olandese 📖 Wikipedia

Il problema della bandiera nazionale olandese (in inglese Dutch national flag problem) è un celebre problema computazionale inerente all'ordinamento, formulato per la prima volta nel 1976 dall'informatico olandese Edsger Dijkstra nel suo libro A Discipline of Programming.^[1]

Il problema prende il nome dalla bandiera dei Paesi Bassi, che è composta da tre bande orizzontali di colori diversi: rosso (in alto), bianco (al centro) e blu (in basso). La formulazione classica richiede di immaginare una fila disordinata di palline di questi tre colori: il compito dell'algoritmo è quello di disporle in modo tale che tutte le palline dello stesso colore siano adiacenti e che i rispettivi gruppi di colori seguano l'ordine corretto (rosso, poi bianco, poi blu).

Dal punto di vista informatico, rappresenta un problema di ordinamento e partizionamento di un array i cui elementi possono assumere solo tre valori distinti (o appartenere a tre categorie prestabilite). La sua soluzione ottima è un algoritmo che opera in-place (senza memoria aggiuntiva) e in un'unica passata (complessità temporale lineare).

In termini formali, il problema consiste nell'ordinare un array in cui ogni elemento appartiene a una di tre categorie (ad esempio: elementi minori, uguali o maggiori rispetto a un dato valore, oppure tre chiavi distinte come ${\displaystyle 0}$, ${\displaystyle 1}$ e ${\displaystyle 2}$). L'obiettivo è riordinare l'array in modo che tutti gli elementi della prima categoria precedano quelli della seconda, che a loro volta precedono quelli della terza.

La soluzione proposta da Dijkstra risolve il problema mantenendo tre puntatori (o indici) che scandiscono l'array, suddividendolo logicamente in quattro sotto-sequenze. Chiamiamo i tre indici ${\displaystyle i}$ (limite superiore del primo gruppo), ${\displaystyle j}$ (elemento corrente in esame) e ${\displaystyle k}$ (limite inferiore del terzo gruppo).

Durante l'esecuzione, l'invariante di ciclo garantisce le seguenti proprietà, assumendo un array con indici da ${\displaystyle 0}$ a ${\displaystyle n-1}$:

• Gli elementi dall'indice ${\displaystyle 0}$ fino a ${\displaystyle i-1}$ appartengono al primo gruppo (es. Rosso / Minori).
• Gli elementi dall'indice ${\displaystyle i}$ fino a ${\displaystyle j-1}$ appartengono al secondo gruppo (es. Bianco / Uguali).
• Gli elementi dall'indice ${\displaystyle j}$ fino a ${\displaystyle k}$ non sono ancora stati esaminati (gruppo misto).
• Gli elementi dall'indice ${\displaystyle k+1}$ fino a ${\displaystyle n-1}$ appartengono al terzo gruppo (es. Blu / Maggiori).

Ad ogni iterazione, l'elemento di indice ${\displaystyle j}$ viene esaminato, il che porta a tre casi possibili:

1. Se appartiene al primo gruppo, viene scambiato con l'elemento di indice ${\displaystyle i}$, ed entrambi gli indici ${\displaystyle i}$ e ${\displaystyle j}$ vengono incrementati.
2. Se appartiene al terzo gruppo, viene scambiato con l'elemento all'indice ${\displaystyle k}$, e solo l'indice ${\displaystyle k}$ viene decrementato (l'indice ${\displaystyle j}$ non viene incrementato perché il nuovo elemento scambiato deve ancora essere valutato).
3. Se appartiene al secondo gruppo (quello centrale), si trova già nella posizione corretta rispetto a quanto esaminato finora, quindi si incrementa semplicemente l'indice ${\displaystyle j}$.

L'algoritmo termina quando ${\displaystyle j>k}$, ovvero quando non ci sono più elementi da esaminare e la funzione di terminazione (la distanza ${\displaystyle k-j}$) raggiunge lo zero o diventa negativa.

Di seguito lo pseudocodice per il partizionamento a tre vie di un array A. Si suppone di voler ordinare gli elementi rispetto a un valore di riferimento (il "perno" o mid_value):

procedura bandiera_olandese(A : array di valori, mid_value : valore):
    i ← 0
    j ← 0
    k ← dimensione(A) - 1

    mentre j <= k:
        se A[j] < mid_value:
            scambia(A[i], A[j])
            i ← i + 1
            j ← j + 1
        altrimenti se A[j] > mid_value:
            scambia(A[j], A[k])
            k ← k - 1
        altrimenti:
            j ← j + 1

• Complessità temporale: ${\displaystyle \Theta (n)}$. L'algoritmo compie esattamente un'ispezione per ogni elemento dell'array (una singola passata). Ad ogni iterazione del ciclo mentre, o ${\displaystyle j}$ aumenta o ${\displaystyle k}$ diminuisce, riducendo strettamente il numero di elementi non esaminati.
• Complessità spaziale: ${\displaystyle \Theta (1)}$ (o ${\displaystyle O(1)}$). L'algoritmo opera rigorosamente in-place, utilizzando solo memoria costante per i tre indici e per le operazioni di scambio, senza richiedere array ausiliari.

La soluzione alla bandiera nazionale olandese riveste un'importanza fondamentale nell'ottimizzazione dell'algoritmo Quicksort. Le implementazioni standard del Quicksort utilizzano un partizionamento a due vie (minori e maggiori del pivot) che risulta inefficiente e degrada a una complessità di ${\displaystyle O(n^{2})}$ se l'array contiene molti elementi ripetuti o tutti uguali. L'introduzione del partizionamento a tre vie (minori, uguali e maggiori del pivot), basato esattamente sull'algoritmo della bandiera olandese, rende il Quicksort altamente robusto agli elementi duplicati. Una variante famosa che sfrutta questa tecnica è il Multi-key Quicksort, utilizzato per l'ordinamento rapido di stringhe.^[2]

Se il numero totale di categorie (colori) è superiore a 3, ma pur sempre limitato a una costante ${\displaystyle c}$, è possibile utilizzare un algoritmo di Counting sort. Quest'ultimo scorre prima l'array per contare le occorrenze di ogni colore, e in una seconda fase sovrascrive l'array con le quantità esatte per ciascun colore in ordine. Sebbene anche il Counting Sort garantisca un tempo lineare ${\displaystyle O(n)}$, la soluzione di Dijkstra (Bandiera Olandese) per il caso a 3 colori è spesso preferibile perché:

1. Effettua una sola passata sui dati (contro le due richieste dal Counting Sort).
2. Esegue solo scambi sui dati reali, risultando l'ideale nei casi in cui l'array non contiene semplici chiavi, ma oggetti complessi in cui la sostituzione distruttiva (o la copia) risulterebbe onerosa o pericolosa.

Va notato, tuttavia, che man mano che il numero di categorie cresce diventando nell'ordine di grandezza di ${\displaystyle n}$, il problema generalizzato non è più risolvibile con questo approccio lineare ma ricade nella normale complessità teorica del sorting comparativo, pari a ${\displaystyle O(n\log n)}$.

• Edsger Dijkstra
• Algoritmo di ordinamento
• Quicksort

• Dutch national flag nel Dictionary of Algorithms and Data Structures del NIST.
• Spiegazione ed esecuzione interattiva dell'algoritmo, a cura della Monash University (in inglese).

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica