Problème du drapeau hollandais

Ce problème peut être vu comme le fait d'ordonner les éléments d'un tableau. Supposons que tous les éléments du tableau puissent être classés en trois catégories (petit, moyen et grand). Par exemple, si tous les éléments sont entre 0 et 1, les petits sont ceux entre 0 et 0,1 (non compris), les moyens entre 0,1 (compris) et 0,3 (non compris) et les grand ceux entre 0,3 (compris) et 1. Le problème est alors de mettre tous les petits éléments au début du tableau, puis les moyens, puis les grands éléments à la fin du tableau.

Un algorithme possible est de faire grandir l'ensemble des grands éléments depuis la fin, celui des petits depuis le milieu, et de garder les éléments moyens juste au-dessus des petits. L'algorithme garde en mémoire trois indices, le début du groupe des grands, la fin du groupe des petits et la fin du groupe des moyens. Les éléments à trier sont entre le groupe moyen et le grand groupe. À chaque étape l'algorithme regarde l'élément juste après les éléments moyens classés. Si cet élément est grand, il est échangé avec l'élément avant l'élément le plus grand classé et son indice est décrémenté, s'il est petit il est échangé avec le plus petit élément moyen et son indice ainsi que l'indice de fin des moyens est incrémenté, sinon l'élément n'est pas bougé et seul l'indice de fin des éléments moyens est incrémenté. La complexité de cet algorithme est ${\displaystyle \Theta (n)}$ déplacements et comparaisons[4].

On considère n éléments rangés dans un tableau T[1..n] (n≥1). Chaque élément a une clé qui ne peut prendre que l’une des trois valeurs : blanc, bleu ou rouge. On souhaite trier le tableau de sorte qu’on ait à gauche tous les éléments bleus (s’il y en a), puis au milieu tous les éléments blancs (s’il y en a), et à droite tous les éléments rouges (s’il y en a).

Le principe est le suivant. On part des deux extrémités, comme dans la procédure partition du tri rapide. On s’intéresse à la case courante du tableau T, dont on teste la couleur, et selon le résultat on procède à des échanges, de sorte qu'on ait à chaque étape à gauche une zone de bleus, puis une zone de blancs, puis une zone inconnue et enfin, à droite une zone de rouges. On va utiliser une variable b (blue), indice de la première case après la zone bleue connue; une variable w (white), indice de la première case après la zone blanche connue et une variable r (red), indice de la première case avant la zone rouge connue. L'algorithme élémentaire consiste à réduire la zone inconnue comprise entre les bornes w et r par test de la couleur de la case w.

Tableau à une étape donnée :

b = 3 ; w = 7 ; r = 10.

Enum couleur {bleu, blanc, rouge}
Lexique : b, w, r : entier ; T : tab[1..n] de couleur
Début
	b ← 1; w ← 1 ; r ← n
	tant que w ≤ r faire 
		si T[w] = blanc alors w ← w+1
		sinon si T[w] = bleu alors 
			{échanger T[b] et T[w] ; 
			b ← b+1 ; w ← w+1 }
		sinon // T[w] = rouge 
			{échanger T[w] avec T[r] ; 
			r ← r-1}
	fintantque ; 
Fin

La complexité au mieux est de n tests de couleur et 0 échange (cas par exemple où tous les éléments sont de couleur bleue) et au pire de 2n tests de couleur et n échanges (par exemple, cas où tous les éléments sont de couleur rouge). Dans le cas où l'on considère que toutes les couleurs sont également possibles en chaque case du tableau, on peut montrer que le nombre moyen de tests est de (5/3)n et que le nombre moyen d'échanges est de (2/3)n [3].

• Une explication interactive de l'exécution de cet algorithme, pour ranger deux ou trois couleurs.