Voir la source de Tri par file de priorité

Un '''tri par file de priorité'''<ref name=":0">{{Lien web |langue=fr |titre=FILES A PRIORITÉ |url=https://www.site.uottawa.ca/~stan/csi2514/trs/chap06 |format=pdf |accès url=libre |consulté le=16 octobre 2024}}</ref> 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 <code>enfiler</code>, <code>défiler</code> et <code>est_vide</code><ref name=":1">{{Article|prénom1=Mikkel|nom1=Thorup|titre=Equivalence between priority queues and sorting|périodique=J. ACM|volume=54|numéro=6|pages=28–es|date=2007-12-01|issn=0004-5411|doi=10.1145/1314690.1314692|lire en ligne=https://dl.acm.org/doi/10.1145/1314690.1314692|consulté le=2024-10-16}}</ref>.

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

== Pseudo-code ==
{{Pseudo code
| entree = Un ensemble d'éléments E muni d'un ordre total <
| sortie = Une liste d'éléments triés selon <
| code = 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
| titre = Tri par file de priorité
}}

== Représentation des tris classiques ==
{|class="wikitable sortable"

! nom de l'algo !! implémentation de la file de priorité!! meilleur cas !! cas moyen !! pire cas 
|- align="center"
|[[Smoothsort]]
|[[Tas de Léonard]]
| style="background:#dfd" |<math>n</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
|- align="center"
| [[Tri par tas]]
| [[Tas (informatique)|Tas]]
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
|- align="center"
|[[Tri arborescent]]
|[[Arbre binaire de recherche|ABR équilibré]]
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
|- align="center"
| [[Tri rapide]]
| [[Arbre binaire de recherche|ABR]]
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#ffffdd" |<math>n \log(n)</math>
| style="background:#fdd" |<math>n^2</math>
|- align="center"
| [[Tri par insertion]]
| [[Tableau (structure de données)|Tableau]] trié
| style="background:#dfd" |<math>n</math>
| style="background:#fdd" |<math>n^2</math>
| style="background:#fdd" |<math>n^2</math>

|- align="center"
| [[Tri par sélection]]
| [[Tableau (structure de données)|Tableau]] non trié
| style="background:#fdd" |<math>n^2</math>
| style="background:#fdd" |<math>n^2</math>
| style="background:#fdd" |<math>n^2</math>
|}

=== Tri par tas ===
{{Article détaillé|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<ref>{{Lien web |langue=fr |auteur=François Schwarzentruber |titre=Files de priorité et Tas Binaires |url=https://people.irisa.fr/Francois.Schwarzentruber/algo1/02tas.pdf |format=pdf |accès url=libre |date=18 février 2021 |consulté le=16 octobre 2024}}</ref>.

=== Tri par insertion ===
{{Article détaillé|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<ref name=":0" />.

En effet, <code>enfiler</code> un élément revient à une opération d'insertion du tri par insertion. La seconde boucle pour <code>defiler</code> 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 ===
{{Article détaillé|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<ref name=":0" />.

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

=== Tri rapide ===
{{Article détaillé|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<ref name=":1" /> :

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

== Notes et références ==
{{Références}}
{{Palette Algorithmes de tri}}
{{Portail|informatique théorique}}
[[Catégorie:Algorithme de tri]]