MagPI 11 Page 34

De Le French MagPi
Aller à : Navigation, rechercher

Le Roi du Tas (tri)

DIFFICULTÉ : FACILE


Nous allons ce mois-ci implémenter un tri par tas.


La grande idée sous-jacente est le "tas". Si vous avez un ensemble de nombres, ils peuvent être disposés sous forme arborescente.

Les règles du tas

  • chaque noeud peut avoir jusqu'à deux noeuds enfants.
  • chaque enfant doit être inférieur ou égal à sa racine.



Voici un tas dans une liste Scratch. Le premier élément est le plus grand nombre.

Ses "enfants" sont en positions 2 et 3.

En réalité, les enfants d'un noeud d'index i sont aux index 2i et 2i+1.



Le tri par tas est beaucoup plus rapide que le tri à bulles (étudié dans le numéro 6), car, en moyenne, il fait beaucoup moins de permutations.


Vous pouvez "tassifier" une liste (oui, c'est un vrai mot !) assez rapidement.

Vous savez que le nombre en haut du tas doit être le plus grand.

Vous le placez alors en fin de liste et tassifiez les valeurs qui sont au-dessus.

En répétant cela, la liste sera triée.


Test de vitesse (50 nombres) : Le tri à bulles effectue 637 permutations et prend 52s.
                                 Le tri par tas fait 245 permutations en 37s.
Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Boîte à outils