Tri par file de priorité

Un tri par file de priorité est un algorithme de tri utilisant comme support principal une implémentation du type abstrait file de priorité.

Si l'exemple classique de tri par file de priorité est le tri par tas, on peut aussi classifier d'autres tris usuels comme tri par file de priorité comme le tri par insertion, le tri par sélection ou encore le tri rapide.

Principe

Une fois que l'on dispose d'une file de priorité, on dispose alors des opérations enfiler, défiler et est_vide.

Pour trier une collection d'éléments, on va alors itérer une première fois la collection des éléments à trier pour les enfiler dans la file de priorité. Ensuite, tant que la file de priorité n'est pas vide (avec est_vide) on peut en défiler les éléments dans l'ordre triés.

Pseudo-code

‎

Tri par file de priorité

Entrée = Un ensemble d'éléments E muni d'un ordre total < Sortie = Une liste d'éléments triés selon <

fonction tri_file_priorité (E) :     P une file de priorité initialement vide     L une liste initialement vide     tant que E non vide :         e <- retirer élément de E         enfiler e dans P     tant que P non vide :         e <- défiler P         ajoute e à L     renvoyer L

Représentation des tris classiques

nom de l'algo	implémentation de la file de priorité	meilleur cas	cas moyen	pire cas
Smoothsort	Tas de Léonard	$n$	$n\log(n)$	$n\log(n)$
Tri par tas	Tas	$n\log(n)$	$n\log(n)$	$n\log(n)$
Tri arborescent	ABR équilibré	$n\log(n)$	$n\log(n)$	$n\log(n)$
Tri rapide	ABR	$n\log(n)$	$n\log(n)$	$n^{2}$
Tri par insertion	Tableau trié	$n$	$n^{2}$	$n^{2}$
Tri par sélection	Tableau non trié	$n^{2}$	$n^{2}$	$n^{2}$

Tri par tas

Si la file de priorité est implémentée par un tas, le tri par file de priorité associée revient au tri par tas par définition de celui-ci.

Tri par insertion

Si la file de priorité est implémentée par une liste triée, le tri par file de priorité associée revient au tri par insertion.

En effet, enfiler un élément revient à une opération d'insertion du tri par insertion. La seconde boucle pour defiler n'est pas nécessaire comme l'on peut renvoyer la file de priorité elle-même qui est la liste triée.

Tri par sélection

Si la file de priorité est implémentée par une liste quelconque, le tri par file de priorité associée revient au tri par sélection.

En effet, la file de priorité est la liste d'élément elle-même. La première boucle pour enfiler les éléments n'est pas nécessaire. La seconde, qui consister à défiler les éléments un par un, reviens à l'opération de sélection des éléments du tri par sélection.

Tri rapide

Si la file de priorité est implémentée par un arbre binaire de recherche, le tri par file de priorité associée revient au tri rapide.

En effet, les différents nœuds de l'arbre binaire de recherche sont les pivots du tri rapide.

Utilisation d'un tri pour faire une file de priorité

Si l'implémentation d'un tri à partir d'une file de priorité est assez immédiat, la réciproque est moins intuitive.

Pourtant, on peut déduire de l'existence d'algorithmes de tri l'existence d'une file de priorité associée. En effet, d'après Mikkel Thorup :

Si l'on peut trier $n$ clef en temps $S(n)$ par clef alors, il existe une file de priorité avec une complexité d'enfiler et de défiler en $O(S(n))$.