Tri par file de priorité

Un tri par file de priorité^[1] 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.

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

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.

‎

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

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^[3].

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^[1].

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.

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^[1].

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.

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.

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^[2] :

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

Algorithmes de tri
Tris par comparaisons	Sans hypothèse autre Complexité moyenne ${\displaystyle {\mathcal {O}}(n\log n)}$ Tri rapide Tri fusion Tri par tas Introsort Smoothsort Timsort Tri arborescent Tri à peigne (?) Tri de Shell (?) Complexité moyenne ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri à bulles Tri par insertion Tri par sélection Tri cocktail Complexité moyenne moins bonne que ${\displaystyle {\mathcal {O}}(n^{2})}$ Tri spaghetti Tri stupide Tri faire-valoir Avec hypothèse supplémentaire Tri comptage Tri par base Tri par paquets Réseau de tri Tri bitonique Tri pair-impair
Tri utilisant d'autres opérations	Tri de crêpes Algorithme de tri externe Tri topologique
Applications	Problème du drapeau hollandais Recherche dichotomique

• Portail de l'informatique théorique