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.Edsger W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1976.

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).

Il problema e l'approccio algoritmico 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 , e ). 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.

Invariante di ciclo 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 (limite superiore del primo gruppo), (elemento corrente in esame) e (limite inferiore del terzo gruppo).

Durante l'esecuzione, l'invariante di ciclo garantisce le seguenti proprietà, assumendo un array con indici da a : Gli elementi dall'indice fino a appartengono al primo gruppo (es. Rosso / Minori). Gli elementi dall'indice fino a appartengono al secondo gruppo (es. Bianco / Uguali). Gli elementi dall'indice fino a non sono ancora stati esaminati (gruppo misto). Gli elementi dall'indice fino a appartengono al terzo gruppo (es. Blu / Maggiori).

Ad ogni iterazione, l'elemento di indice viene esaminato, il che porta a tre casi possibili:

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

L'algoritmo termina quando , ovvero quando non ci sono più elementi da esaminare e la funzione di terminazione (la distanza ) raggiunge lo zero o diventa negativa.

Pseudocodice 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

Analisi della complessità Complessità temporale: . L'algoritmo compie esattamente un'ispezione per ogni elemento dell'array (una singola passata). Ad ogni iterazione del ciclo mentre, o aumenta o diminuisce, riducendo strettamente il numero di elementi non esaminati. Complessità spaziale: (o ). L'algoritmo opera rigorosamente in-place, utilizzando solo memoria costante per i tre indici e per le operazioni di scambio, senza richiedere array ausiliari.

Confronto con altri algoritmi e applicazioni

Relazione con il Quicksort 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 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.

Confronto con il Counting Sort Se il numero totale di categorie (colori) è superiore a 3, ma pur sempre limitato a una costante , è 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 , la soluzione di Dijkstra (Bandiera Olandese) per il caso a 3 colori è spesso preferibile perché: Effettua una sola passata sui dati (contro le due richieste dal Counting Sort). 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 , il problema generalizzato non è più risolvibile con questo approccio lineare ma ricade nella normale complessità teorica del sorting comparativo, pari a .

Note

Voci correlate Edsger Dijkstra Algoritmo di ordinamento Quicksort

Collegamenti esterni 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).

Categoria:Algoritmi di ordinamento Categoria:Problemi computazionali