Le problème du drapeau hollandais, proposé par Dijkstra, consiste à trier un tableau contenant des boules de couleurs bleues, blanches et rouges de façon à retrouver le drapeau hollandais.
Exercice
On dispose d’un tableau de taille $n$ contenant soit des boules bleues, soit des boules blanches. Nous représentons les boules bleues par l’entier $0$ et les boules blanches par $1$. Les seules opérations autorisés sont la lecture d’une case du tableau et l’échange de deux cases.
$1)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.
$2)$ Combien d’échange au maximum l’algorithme effectue-t-il ?
Le problème du drapeau Hollandais, fonctionne sur le même principe excepté qu’on ajoute cette fois-ci des boules rouges représentées par $2$. Notre but est de trier notre tableau en bleu-blanc-rouge en effectuant le moins de lecture de cases possible.
$3)$ Proposer un algorithme de tri sur place du tableau effectuant au plus $n$ lecture de cases.
$4)$ Combien d’échange au maximum l’algorithme effectue-t-il ?
Correction
$1)$ On propose l’algorithme suivant.
La quantité $y-x$ est entière et décroît de 1 à chaque itération. De plus, on sort de la boucle si $y-x \lt 0$. Ainsi, l’algorithme termine après $n$ itérations de boucles. Or chacune n’effectue qu’une unique lecture. On effectue donc exactement $n$ lectures mémoires.
Prouvons la correction de cet algorithme. Pour ce faire, nous exhibons un invariant de boucle $\mathcal{I}$ en définissant $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues et les boules de $y+1$ à $n$ sont toutes blanches » . Avant d’entrer dans la boucle, $x(i)=1$ et $y(i)=n$ donc la propriété est vérifiée.
On suppose que l’invariant est vérifié à l’étape $i$. À l’étape $i+1$ si $T[x(i)]$ est bleue et $x(i+1)=x(i)+1$. Les boules de $0$ à $x(i+1)-1$ sont bleues et comme $y$ n’est pas modifié, on a encore que les boules de $y(i+1)+1$ à $n-1$ sont toutes blanches. Si $T[x(i)]$ est blanche, on montre de même que l’invariant est conservé.
Enfin, à la sortie de la boucle après l’itération $n$, on a $y(n) \lt x(n)$. Ainsi, notre algorithme renvoie bien un tableau trié.
$2)$ Dans chaque itération, on effectue au plus un échange. On effectue donc au plus $n$ échanges. De plus, ce nombre est atteint dans le cas du tableau ne contenant que des boules blanches.
$3)$ On considère l’algorithme suivant.
On effectue exactement $n$ passages dans la boucle. On effectue donc bien exactement $n$ lectures de cases.
La preuve de la correction et de la terminaison est similaire à l’algorithme du cas deux couleurs. L’invariant à considérer est $\mathcal{I}(i) = $ « À la fin de l’itération $i$, les boules de $1$ à $x$ sont toutes bleues, les boules de $y+1$ à $z$ sont toutes blanches et les boules de $z+1$ à $n$ sont toutes rouges. »
$4)$ Dans le pire des cas, on effectue deux échanges par itération. On effectue donc au plus $2n$ échanges. Ce pire cas est atteint dans le cas du tableau ne contenant que des boules rouges.