LabASD - Problema della bandiera nazionale

Moreno Marzolla

Ultimo aggiornamento: 2023-03-12

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

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:

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

Suggerimento

L’algoritmo ordina progressivamente l’array a[] mantenendo tre variabili v, i, r che soddisfano le seguenti proprietà (Figura 1):

Figura 1: Invariante per l’algoritmo della bandiera
Figura 1: 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, quindi possono essere di qualsiasi colore;

  5. \(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).

Figura 2: Conservazione dell’invariante
Figura 2: Conservazione dell’invariante

File