Tri de trois valeurs
Le tri du drapeau hollandais en bref
On l'utilise dans le cadre des tableaux ne contenant que trois valeurs distinctes (petite, moyenne et grande).
Il a pour avantage d'être de coût linéaire et de trier le tableau en un seul passage.
On partage le tableau en quatre zones :
- les petites valeurs,
- puis les valeurs moyennes,
- puis les valeurs pas encore triées,
- enfin les grandes valeurs.
L'algorithme s'arrête lorsque la zone des valeurs à trier est vide.
On souhaite trier un tableau ne contenant que trois valeurs a, b et c répétées un nombre quelconque de fois. On souhaite trier ce tableau afin de placer au début les a suivis des b et enfin des c.
Par exemple, avec nombres = [2, 0, 2, 1, 2, 1] on a a = 0, b = 1 et c = 2. Le tableau trié est [0, 1, 1, 2, 2, 2].
Dans ce cas de figure, on peut utiliser le tri du drapeau hollandais.
Remarque
Ce tri a été inventé par Edsger Dijkstra qui était de nationalité néelandaise.
Il a donné son nom à l'algorithme en référence aux trois couleurs du drapeau néerlandais : Rouge, Blanc, Bleu.
L'idée est de maintenir quatre zones dans le tableau :
- la première ne contient que des
a, - la deuxième que des
b, - la troisième des valeurs pas encore triées,
- enfin la dernière zone ne contient que des
c.
Ces zones sont délimitées par les bornes suivantes (toutes incluses):
- de l'indice
0àprochain_a - 1, - de
prochain_aàactuel, - de
actuel + 1àprochain_c, - de
prochain_c + 1àlen(tableau) - 1
L'algorithme fonctionne ainsi :
-
Les variables
prochain_aetactuelsont initialisées à0, -
La variable
prochain_cest initialisée àlen(tableau) - 1, -
On répète les actions suivantes tant que la zone des valeurs restant à trier est non vide :
-
On lit l'élément à l'indice
actuel:- Si c'est un
a, on le rajoute à la fin de la zone desaen échangeant les éléments d'indicesprochain_aetactuel(étape 3 sur les figures), - Si c'est un
b, on la laisse à sa position (étape 2 et 6), - Si c'est un
c, on la place à la position précédant le début de la zone descen échangeant les éléments d'indicesprochain_cetactuel(étape 1, 4 et 5), - Dans tous les cas, on prend soin de mettre à jour les différents indices afin de refléter les nouvelles étendues des zones.
- Si c'est un
-
Les figures ci-dessous illustrent le tri du tableau [2, 0, 2, 1, 2, 1] :
-
Étape 1
On lit un
2: on le place au début de la zone desc.prochain_cest décrémenté.⚓︎- Étape 2
On lit un
1: on le laisse à cette position.actuelest incrémenté.
-
Étape 3
On lit un
0: on le place à la fin de la zone desa.prochain_aetactuelsont incrémentés.
-
Étape 4
On lit un
2: on le place au début de la zone desc.prochain_cest décrémenté.
-
Étape 5
On lit un
2: on le place au début de la zone desc.prochain_cest décrémenté.
-
Étape 6
On lit un
1: on le laisse à cette position.
-
Étape 7
actuelest strictement supérieur àprochain_c.L'algorithme se termine.
Vous devez écrire la fonction tri_3_valeurs qui prend en argument un tableau ainsi que les trois valeurs distinctes le composant a, b et c et le trie en place en positionnant les a au début suivis des b et enfin des c.
Contrainte
On interdit d'utiliser la méthode de tri sort et la fonction de tri native sorted.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)