Comparaisons
Échanges
Extraites

  • En descente
  • Comparées
  • Échangées
  • En place

En savoir plus sur le tri par tas

Tri par tas

Le tri par tas lit la liste comme un arbre binaire et la réorganise en tas max, où chaque parent est au moins aussi grand que ses enfants. La plus grande valeur est alors au sommet. Échangez-la avec la fin, où elle reste, réparez le tas et recommencez. L'application dessine le tas en arbre au-dessus des barres : vous suivez chaque valeur pendant qu'elle descend. Appuyez sur Lecture pour regarder le tri, ou sur Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où. L'arbre au-dessus des barres montre les mêmes valeurs sous forme de tas. Les tuiles comptent les comparaisons, les échanges et les valeurs retirées du tas. Choisissez le nombre de barres, leur ordre de départ, ou saisissez vos propres nombres. Quand le tableau est sélectionné, les flèches avancent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez le nombre de barres et leur ordre de départ : aléatoire, presque trié, inversé ou avec peu de valeurs distinctes. Ou saisissez vos propres nombres.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer d'une comparaison à la fois. Faites glisser le curseur d'étapes pour aller n'importe où dans le tri.
  3. Suivez l'arbre : d'abord chaque parent descend jusqu'à ce que le tas soit construit, puis la racine est échangée avec la fin et le tas raccourcit d'une case.

Fonctionnement du tri par tas

Lisez la liste comme un arbre : la valeur en position i a ses enfants aux positions 2i + 1 et 2i + 2. Construisez un tas max en faisant descendre chaque parent, en commençant par le dernier : tant qu'une valeur est plus petite que le plus grand de ses enfants, les deux s'échangent. Quand la racine contient la plus grande valeur, échangez-la avec la dernière valeur du tas. Cette valeur est désormais définitive, le tas raccourcit d'une case, et la nouvelle racine descend pour qu'il redevienne un tas. Recommencez jusqu'à ce que le tas soit vide.

Toujours n log n, en place

L'arbre a environ log₂ n niveaux, donc chaque descente fait au plus environ 2 log₂ n comparaisons, et la construction du tas moins de 2n. Le tri par tas fait donc au pire environ 2n log₂ n comparaisons, sans tampon : pour 40 valeurs, au plus 352. Contrairement au tri rapide, il n'a pas de mauvaises entrées, et contrairement au tri fusion, il ne demande pas de mémoire supplémentaire. En pratique, il est généralement plus lent que les deux, car il saute d'un bout à l'autre de la liste, et il n'est pas stable.

Questions fréquemment posées

Comment fonctionne le tri par tas ?

Il transforme la liste en tas max, un arbre stocké dans la liste où chaque parent est au moins aussi grand que ses enfants. Puis il échange encore et encore la plus grande valeur, à la racine, avec la fin du tas, et fait descendre la nouvelle racine pour réparer le tas.

Qu'est-ce qu'un tas ?

Un arbre binaire complet stocké dans une liste sans pointeurs : les enfants de la position i sont les positions 2i + 1 et 2i + 2. Dans un tas max, chaque parent est au moins aussi grand que ses enfants, donc la plus grande valeur est toujours à la racine, en position 0.

Pourquoi la construction du tas est-elle rapide ?

La plupart des valeurs sont près du bas de l'arbre et ne peuvent descendre que d'un ou deux niveaux. En additionnant le travail de tous les niveaux, on obtient moins de 2n comparaisons pour toute la construction, et non n log n.

Le tri par tas est-il stable ?

Non. Échanger la racine avec la fin déplace les valeurs sur de longues distances, donc des valeurs égales peuvent changer d'ordre.

Mes nombres sont-ils envoyés quelque part ?

Non. Le tri s'exécute dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur