Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tri par tas
Résumé
thumb|300px|Animation montrant le fonctionnement du tri par tas (Heapsort).
En informatique, le tri par tas est un algorithme de tri par comparaisons. Cet algorithme est de complexité asymptotiquement optimale, c'est-à-dire que l'on démontre qu'aucun algorithme de tri par comparaison ne peut avoir de complexité asymptotiquement meilleure. Sa complexité est proportionnelle à où est la longueur du tableau à trier. Le tri par tas se fait en place, c’est-à-dire qu’il ne nécessite pas l'allocation d'une zone mémoire supplémentaire (plus précisément il ne nécessite qu'une allocation d'une zone mémoire de taille ). Par contre, il n'est pas stable.
Son inconvénient majeur est sa lenteur comparé au tri rapide (qui est en moyenne deux fois plus rapide) : sur un tableau de taille importante, il sera amené à traiter un nombre élevé d'emplacements mémoire dont l’éloignement peut dépasser la capacité du cache, ce qui ralentit l'accès à la mémoire et l’exécution de l’algorithme.
L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un arbre binaire. Le premier élément est la racine, le deuxième et le troisième sont les deux descendants du premier élément, etc. Ainsi le e élément a pour enfants les éléments et si l'indexation se fait à partir de 1 ( et si l'indexation se fait à partir de 0).
Si le tableau n'est pas de taille , les branches ne se finissent pas toutes à la même profondeur.
Dans l'algorithme, on cherche à obtenir un tas, c'est-à-dire un arbre binaire vérifiant les propriétés suivantes (les deux premières propriétés découlent de la manière dont on considère les éléments du tableau) :
la différence maximale de profondeur entre deux feuilles est de 1 (i.e. toutes les feuilles se trouvent sur la dernière ou sur l'avant-dernière ligne) ;
les feuilles de profondeur maximale sont « tassées » sur la gauche.
chaque nœud est de valeur supérieure (resp. inférieure) à celles de ses deux fils, pour un tri ascendant (resp. descendant).
Il en découle que la racine du tas (le premier élément) contient la valeur maximale (resp.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.