Problème du drapeau hollandais

Le problème du drapeau hollandais est un problème de programmation, présenté par Edsger Dijkstra^[1], qui consiste à réorganiser une collection d'éléments identifiés par leur couleur, sachant que seules trois couleurs sont présentes (par exemple, rouge, blanc, bleu, dans le cas du drapeau des Pays-Bas).

Étant donné un nombre quelconque de balles rouges, blanches et bleues alignées dans n'importe quel ordre, le problème est à les réarranger dans le bon ordre : les bleues d'abord, puis les blanches, puis les rouges.

Au départ les balles sont disposées dans un ordre quelconque. À la fin, toutes les balles de la même couleur doivent être rangées ensemble et l'ordre entre les couleurs doit être respecté, ainsi que l'ordre que les balles de même couleur avaient les unes par rapport aux autres dans l'agencement initial : on trouve par exemple d'abord tous les objets bleus, puis tous les objets blancs et enfin tous les objets rouges et si une balle rouge apparaissait avant une autre balle rouge, elle doit apparaître dans cet ordre dans l'agencement final (on appelle un tel algorithme de tri un algorithme stable). L'espace mémoire auxiliaire doit aussi être optimisé.

La solution est à la base d'algorithmes de tris, en particulier de variantes de quicksort qui doivent être stables. Autrement dit on cherche à définir un algorithme qui regroupe des items en trois catégories, ceux qui sont plus petits, ceux qui sont plus grands, et ceux qui sont égaux à un élément spécifique sans trop bouleverser l'ordre initial^[2].

Description

L'algorithme proposé par Edsger Dijkstra est un algorithme qui montre que l'on peut ordonner une collection de n objets en un nombre linéaire de tests de couleurs, alors que les algorithmes de tri sans information sur les clés des objets font un nombre de comparaisons entre clés en ordre de grandeur plus grand (en moyenne et au pire de l'ordre de $n\log n$ ) ^[3].

Le cas d'un tableau

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 $\Theta (n)$ déplacements et comparaisons^[4].

Algorithme général

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

Principe

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 :

bleu	bleu	blanc	blanc	blanc	blanc	inconnue	inconnue	inconnue	inconnue	rouge	rouge
1	2	3	4	5	6	7	8	9	10	11	12

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

Pseudocode

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

Complexité

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

Voir aussi

Algorithme du drapeau américain (en)

Liens externes

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

Références

↑ Dans le livre : Edsger W. Dijkstra, A discipline of programming, Englewood Cliffs, N.J., Prentice-Hall, 1976, xvii+217 (ISBN 0-13-215871-X, OCLC 1958445), le chapitre 14 (pages 111-116) a pour titre : « The Problem of the Dutch national flag ».
↑ Ce cas apparaît en particulier dans les chaînes de caractères triées avec la version de Quicksort à plusieurs clefs. Voir : Eunsang Kim et Kunsoo Park, « Improving multikey Quicksort for sorting strings with many equal elements », Information Processing Letters, vol. 109, n^o 9,‎ avril 2009, p. 454–459 (DOI 10.1016/j.ipl.2009.01.007)
↑ ^{a et b} Colin L. McMaster, « An analysis of algorithms for the Dutch national flag problem », Communications of the ACM, vol. 21, n^o 10,‎ octobre 1978, p. 842-846 (DOI 10.1145/359619.359629)
↑ « Dutch National Flag problem and algorithm », Faculty of Information Technology (Clayton), Monash University, Australia, 1998