Le tri par tas
Construire un tas maximum dans le tableau même, puis échanger la racine avec la dernière case et retamiser : un tri en n log n garanti, en place, non stable, comparé aux tris fusion et rapide.
- 22 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Tri par tas : de quoi s'agit-il ?
Voir la réponse
Tri qui transforme d'abord le tableau en tas maximum, puis retire à répétition le plus grand élément en le plaçant à la fin du tableau.
Le tas tient dans le tableau lui-même et la zone triée grandit depuis la droite : aucune mémoire auxiliaire n'est nécessaire.
Quel tableau obtient-on en transformant
[3, 9, 2, 7, 5]en tas maximum par descentes successives, du dernier père à la racine ?[9, 7, 2, 3, 5][9, 5, 2, 3, 7][9, 3, 2, 7, 5][3, 9, 7, 2, 5]
Voir la réponse
[9, 7, 2, 3, 5]Le dernier père est en case 1 (9) : plus grand que 7 et 5, il reste. Puis la racine 3 descend : elle est échangée avec son plus grand fils, 9, puis avec 7 (le plus grand de ses fils 7 et 5). On obtient [9, 7, 2, 3, 5].
Le tri par tas se déroule en deux phases : … un tas maximum, puis … la racine à répétition.
Voir la réponse
Le tri par tas se déroule en deux phases : construire un tas maximum, puis extraire la racine à répétition.
La première phase organise tout le tableau en O(n) ; la seconde fait n extractions de O(log n) chacune, d'où n log n au total.
Construction du tas : de quoi s'agit-il ?
Voir la réponse
Phase qui fait descendre chaque père à sa place, du dernier père jusqu'à la racine, pour que le tableau vérifie la propriété de tas.
Pour n éléments, le dernier père est à l'indice n/2 − 1 (division entière) : les cases suivantes sont des feuilles, déjà des tas d'un élément. Cette phase coûte O(n).