LabASD - Problema della bandiera nazionale

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-03-20

Il problema della bandiera nazionale olandese è stato proposto per la prima volta da Edsger W. Dijkstra nel 1976 (E. W. Dijkstra, A discipline of programming, Prentice-Hall, 1976). Lo riproponiamo qui in chiave italiana.

Edsger W. Dijkstra By Hamilton Richards - manuscripts of Edsger W. Dijkstra, University Texas at Austin, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=4204157
Edsger W. Dijkstra By Hamilton Richards - manuscripts of Edsger W. Dijkstra, University Texas at Austin, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=4204157

Sia a[] un array di lunghezza \(n \geq 0\), i cui elementi possono assumere solo uno di tre possibili 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'algoritmo deve soddisfare i seguenti requisiti:

L'ordinamento non deve necessariamente essere stabile, quindi è possibile cambiare l'ordine relativo degli elementi dello stesso colore.

L'algoritmo non può usare contatori per tenere traccia del numero di elementi di un certo colore presenti (non si può usare l'algoritmo counting sort).

Suggerimento

Supponiamo che durante l'esecuzione dell'algoritmo l'array a[] venga progressivamente ordinato. In particolare, durante la sua esecuzione, l'algoritmo mantiene tre variabili v, i, r che soddisfano le seguenti invarianti (ricordiamo che una invariante è una proprietà che rimane vera durante l'intera esecuzione dell'algoritmo; si faccia riferimento alla Figura 2):

Figura 2: Invariante per l'algoritmo della bandiera
Figura 2: Invariante per l'algoritmo della bandiera
  1. Gli elementi a[0..v-1] sono verdi (se v==0, non ci sono elementi verdi);

  2. Gli elementi a[v..i-1] sono bianchi (se i==v, non ci sono elementi bianchi);

  3. Gli elementi a[r+1..n-1] sono rossi (se r==n-1, non ci sono elementi rossi);

  4. Gli elementi a[i..r] devono essere ancora esaminati, e possono essere di qualsiasi colore.

Ad ogni iterazione, l'algoritmo esamina a[i], effettuando opportuni scambi per spostare l'elemento nella posizione corretta in base al proprio colore.

Quella sopra non è l'unica invariante possibile per questo esercizio, ma è quella che consente di ridurre il numero di scambi che occorre fare per riordinare l'array.

File