Un problema molto divertente da risolvere è quello della Bandiera Olandese o in inglese Dutch National Flag Problem.

Il problema e’ stato postulato da Edsger Dijkstra, il famoso informatico per l’algoritmo sui grafi.

Questo problema si formula così: Abbiamo un array non ordinato formato da N valori numerici, che sono o 0 o 1 o 2. Il nostro compito è ordinarlo.
Quindi mi trovo in una situazione del genere:

[0,1,2,0,1,1,2,0,2,1,0,0,1,1,2,2]


Quale è il modo per ordinarli?

La risposta che per prima ci verrebbe in mente è usare un merge sort o un quick sort, per avere una complessita’ computazionale pari a n*log(n).
Addirittura modificando il quicksort si potrebbe ricavare un algoritmo molto molto veloce, in quanto si salterebbe la fase dopo la scelta del pivot (che ricadrebbe sempre su 1).

Tuttavia c’e’ un modo molto piu’ interessante di gestire il problema.

Possiamo pensare all’array come alle tre strisce di una bandiera (da cui il nome del problema), quindi abbiamo 3 tipi di valori che dobbiamo sistemare e sappiamo per certo che ci saranno 2 indici che ne decideranno il limite.
Il primo, che nominerò “basso“, indicherà quando i valori pari a 0 dentro l’array finiranno, Il secondo, che nominerò “alto“, invece si troverà dove i valori pari a 2 inizieranno.
Un terzo indice, che chiamerò “mobile“,  indica i valori pari a 1,  esso si sposterà dalla posizione 0 e man mano arriverà dove inizieranno quelli pari a 2.
Quando l’indice mobile sarà uguale all’indice alto avremo finito.

Iniziamo settando l’indice basso e l’indice mobile alla posizione 0, e l’indice alto alla fine dell’array.
Essi verranno incrementati o decrementati e usati come posizione per scambiare i valori dentro l’array a seconda dell’elemento corrente che viene esaminato.

Questo approccio ha una complessita’ computazionale pari a N, perche’ varia in funziona del numero di valori dentro l’array e la complessità relativa alla memoria occupata è pari a 1

Lascio sotto il codice scritto in python su github per mostrare questo approccio.