Utilisateur:Saxophile/sandbox

Algorithme du drapeau tricolore

Le problème du Drapeau tricolore (Dutch national flag problem) a été introduit par Edsger Dijkstra. Le problème consiste à réorganiser une collection d'éléments repérés par leur couleur, sachant que trois couleurs seulement sont possibles (par exemple, rouge, blanc, bleu, si on considère le drapeau français). Au départ les objets sont rangés dans un ordre quelconque. A la fin, tous les objets de la même couleur doivent être rangés ensemble et l'ordre entre les couleurs doit être respecté : on trouve par exemple d'abord tous les objets bleus, puis tous les objets blancs et enfin tous les objets rouges.

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

Algorithme

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 .