Ultimo aggiornamento: 2023-03-12
Il problema della bandiera nazionale olandese è stato proposto da Edsger W. Dijkstra nel 1976 (E. W. Dijkstra, A discipline of programming, Prentice-Hall, 1976). Lo riproponiamo qui in chiave italiana.
Sia a[]
un array di lunghezza \(n \geq 0\), i cui elementi possono assumere valori VERDE
, BIANCO
, ROSSO
; non è detto che siano presenti elementi di ciascun colore. Vogliamo ordinare l’array in modo che tutti gli elementi verdi precedano quelli bianchi, e gli elementi bianchi precedano quelli rossi. L’ordinamento non deve necessariamente essere stabile, quindi è possibile cambiare l’ordine relativo degli elementi dello stesso colore. L’algoritmo deve soddisfare i seguenti requisiti:
deve richiedere tempo \(O(n)\);
deve usare spazio aggiuntivo \(O(1)\) oltre a quello necessario per memorizzare l’array da ordinare;
deve operare scambiando tra di loro elementi di a[]
.
Dall’ultimo punto deriva che l’algoritmo non può usare contatori per tenere traccia del numero di elementi di ciascun colore (non si può usare l’algoritmo counting sort).
L’algoritmo ordina progressivamente l’array a[]
mantenendo tre variabili v
, i
, r
che soddisfano le seguenti proprietà (Figura 1):
Gli elementi a[0..v-1]
sono verdi (se v==0
, non ci sono elementi verdi);
Gli elementi a[v..i-1]
sono bianchi (se i==v
, non ci sono elementi bianchi);
Gli elementi a[r+1..n-1]
sono rossi (se r==n-1
, non ci sono elementi rossi);
Gli elementi a[i..r]
devono essere ancora esaminati, quindi possono essere di qualsiasi colore;
\(v \leq i \leq r < n\).
Ad ogni iterazione, l’algoritmo esamina a[i]
, effettuando opportuni scambi per spostarlo nella posizione corretta in base al proprio colore (vedi Figura 2).
Quali devono essere i valori iniziali di v
, i
, r
?
Qual è la condizione che determina la terminazione dell’algoritmo?