Tri en tas - Heapsort

Tri en tas
Tri heapsort anim.gif
Une série de tas triant un tableau de valeurs permutées de manière aléatoire. Dans la première étape de l'algorithme, les éléments du tableau sont réorganisés pour satisfaire la propriété de tas . Avant que le tri n'ait lieu, la structure arborescente du tas est brièvement présentée à titre d'illustration.
Classer Algorithme de tri
Structure de données Déployer
Performances dans le pire des cas
Le meilleur cas la performance (touches distinctes)
ou (touches égales)
Performances moyennes
Complexité spatiale dans le pire des cas auxiliaire total

En informatique , le tri par tas est un algorithme de tri basé sur la comparaison . Le tri par tas peut être considéré comme un tri par sélection amélioré : comme le tri par sélection, le tri par tas divise son entrée en une région triée et une région non triée, et il réduit itérativement la région non triée en en extrayant le plus grand élément et en l'insérant dans la région triée. Contrairement au tri par sélection, le tri par tas ne perd pas de temps avec un balayage linéaire de la région non triée ; au lieu de cela, le tri par tas conserve la région non triée dans une structure de données de tas pour trouver plus rapidement le plus grand élément à chaque étape.

Bien qu'un peu plus lent en pratique sur la plupart des machines qu'un quicksort bien implémenté , il a l'avantage d'un runtime O( n log n ) dans le pire des cas plus favorable . Heapsort est un algorithme sur place , mais ce n'est pas un tri stable .

Heapsort a été inventé par JWJ Williams en 1964. C'était aussi la naissance du tas, déjà présenté par Williams comme une structure de données utile à part entière. La même année, RW Floyd a publié une version améliorée qui pouvait trier un tableau sur place, poursuivant ses recherches antérieures sur l' algorithme de tri par arbre .

Aperçu

L'algorithme de tri en tas peut être divisé en deux parties.

Dans la première étape, un tas est construit à partir des données (voir Tas binaire § Construire un tas ). Le tas est souvent placé dans un tableau avec la disposition d'un arbre binaire complet . L'arbre binaire complet mappe la structure de l'arbre binaire dans les indices du tableau ; chaque indice de tableau représente un nœud ; l'index du parent du nœud, de la branche enfant gauche ou de la branche enfant droite sont des expressions simples. Pour un tableau de base zéro, le nœud racine est stocké à l'index 0 ; si iest l'indice du nœud courant, alors

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

Dans la deuxième étape, un tableau trié est créé en supprimant à plusieurs reprises le plus grand élément du tas (la racine du tas) et en l'insérant dans le tableau. Le tas est mis à jour après chaque suppression pour conserver la propriété du tas. Une fois que tous les objets ont été supprimés du tas, le résultat est un tableau trié.

Le tri en tas peut être effectué sur place. Le tableau peut être divisé en deux parties, le tableau trié et le tas. Le stockage des tas sous forme de tableaux est schématisé ici . L'invariant du tas est conservé après chaque extraction, le seul coût est donc celui de l'extraction.

Algorithme

L'algorithme Heapsort consiste à préparer la liste en la transformant d'abord en un tas max . L'algorithme permute ensuite à plusieurs reprises la première valeur de la liste avec la dernière valeur, en diminuant de un la plage de valeurs considérées dans l'opération de tas et en tamisant la nouvelle première valeur dans sa position dans le tas. Cela se répète jusqu'à ce que la plage de valeurs considérées ait une longueur d'une valeur.

Les étapes sont :

  1. Appelez la fonction buildMaxHeap() sur la liste. Également appelé heapify(), cela crée un tas à partir d'une liste en O(n) opérations.
  2. Échangez le premier élément de la liste avec le dernier élément. Diminuer la plage considérée de la liste par un.
  3. Appelez la fonction siftDown() sur la liste pour tamiser le nouveau premier élément à son index approprié dans le tas.
  4. Passez à l'étape (2) sauf si la plage considérée de la liste est un élément.

L'opération buildMaxHeap() est exécutée une fois et est O( n ) en performance. La fonction siftDown() est O(log n ) et est appelée n fois. Par conséquent, la performance de cet algorithme est O( n + n log n ) = O( n log n ) .

Pseudocode

Ce qui suit est un moyen simple d'implémenter l'algorithme en pseudocode . Les tableaux sont basés sur zéro et swapsont utilisés pour échanger deux éléments du tableau. Le mouvement « vers le bas » signifie de la racine vers les feuilles, ou d'indices inférieurs à supérieurs. Notez que lors du tri, le plus grand élément est à la racine du tas à a[0], tandis qu'à la fin du tri, le plus grand élément est dans a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

La routine de tri utilise deux sous-routines, heapifyet siftDown. Le premier est la routine commune de construction de tas sur place, tandis que le second est un sous-programme commun pour la mise en œuvre de heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

La heapifyprocédure peut être considérée comme la construction d'un tas de bas en haut en tamisant successivement vers le bas pour établir la propriété du tas . Une version alternative (illustrée ci-dessous) qui construit le tas de haut en bas et passe au crible vers le haut peut être plus simple à comprendre. Cette siftUpversion peut être visualisée comme commençant par un tas vide et insérant successivement des éléments, alors que la siftDownversion donnée ci-dessus traite l'ensemble du tableau d'entrée comme un tas plein mais "cassé" et le "répare" à partir du dernier sous-tas non trivial ( c'est-à-dire le dernier nœud parent).

Différence de complexité temporelle entre la version "siftDown" et la version "siftUp".

De plus, la siftDownversion de heapify a une complexité temporelle de O ( n ) , tandis que la siftUpversion donnée ci-dessous a une complexité temporelle O ( n log n ) en raison de son équivalence avec l'insertion de chaque élément, un à la fois, dans un tas vide. Cela peut sembler contre-intuitif car, d'un coup d'œil, il est évident que le premier ne fait que deux fois moins d'appels à sa fonction de criblage en temps logarithmique que le second ; c'est-à-dire qu'ils ne semblent différer que par un facteur constant, qui n'affecte jamais l'analyse asymptotique.

Pour saisir l'intuition derrière cette différence de complexité, notez que le nombre d'échanges pouvant se produire lors d'un appel siftUp augmente avec la profondeur du nœud sur lequel l'appel est effectué. Le point crucial est qu'il y a beaucoup (de façon exponentielle beaucoup) de nœuds plus « profonds » que de nœuds « peu profonds » dans un tas, de sorte que siftUp peut avoir son temps d'exécution logarithmique complet sur le nombre approximativement linéaire d'appels effectués sur les nœuds à ou près du "fond" du tas. D'autre part, le nombre d'échanges pouvant se produire au cours d'un appel siftDown diminue à mesure que la profondeur du nœud sur lequel l'appel est effectué augmente. Ainsi, lorsque le siftDown heapifycommence et fait appel siftDownau bas et aux plus nombreux nœuds-couches, chaque appel de tamisage entraînera, au plus, un nombre de swaps égal à la "hauteur" (à partir du bas du tas) du nœud sur lequel l'appel de tamisage est effectué. En d'autres termes, environ la moitié des appels à siftDown n'auront au plus qu'un seul swap, puis environ un quart des appels auront au plus deux swaps, etc.

L'algorithme heapsort lui-même a une complexité temporelle de O ( n log n ) en utilisant l'une ou l'autre version de heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Notez que contrairement à l' siftDownapproche où, après chaque permutation, vous n'avez besoin d'appeler que le siftDownsous - programme pour réparer le tas cassé ; le siftUpsous - programme seul ne peut pas réparer le tas cassé. Le tas doit être construit à chaque fois après un échange en appelant la heapifyprocédure car "siftUp" suppose que l'élément échangé se retrouve à sa place finale, contrairement à "siftDown" qui permet des ajustements continus des éléments plus bas dans le tas jusqu'à ce que le l'invariant est satisfait. Le pseudocode ajusté pour l'utilisation de l' siftUpapproche est donné ci-dessous.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Variantes

La construction du tas de Floyd

La variation la plus importante de l'algorithme de base, qui est incluse dans toutes les implémentations pratiques, est un algorithme de construction de tas de Floyd qui s'exécute en un temps O ( n ) et utilise siftdown plutôt que siftup , évitant ainsi d'avoir à implémenter siftup.

Plutôt que de commencer par un tas trivial et d'ajouter à plusieurs reprises des feuilles, l'algorithme de Floyd commence par les feuilles, observant qu'il s'agit de tas triviaux mais valides par eux-mêmes, puis ajoute les parents. En commençant par l'élément n /2 et en revenant, chaque nœud interne devient la racine d'un tas valide en passant au crible. La dernière étape consiste à passer au crible le premier élément, après quoi l'ensemble du tableau obéit à la propriété heap.

Le nombre de comparaisons dans le pire des cas au cours de la phase de construction de tas de Floyd de Heapsort est connu pour être égal à 2 n − 2 s 2 ( n ) − e 2 ( n ) , où s 2 ( n ) est le nombre de 1 bits dans la représentation binaire de n et e 2 ( n ) est le nombre de 0 bits de fin.

L'implémentation standard de l'algorithme de construction de tas de Floyd provoque un grand nombre d' échecs de cache une fois que la taille des données dépasse celle du cache CPU . De bien meilleures performances sur de grands ensembles de données peuvent être obtenues en fusionnant par ordre de profondeur d'abord , en combinant les sous-tas dès que possible, plutôt que de combiner tous les sous-tas sur un même niveau avant de passer à celui ci-dessus.

Tri en tas ascendant

Le tri par tas ascendant est une variante qui réduit le nombre de comparaisons requises par un facteur significatif. Alors que le tri en tas ordinaire nécessite 2 n log 2 n + O ( n ) comparaisons dans le pire des cas et en moyenne, la variante ascendante nécessite n log 2 n + O (1) comparaisons en moyenne, et 1,5 n log 2 n + O ( n ) dans le pire des cas.

Si les comparaisons sont bon marché (par exemple des clés entières), alors la différence est sans importance, car le tri de tas descendant compare les valeurs qui ont déjà été chargées à partir de la mémoire. Si, toutefois, les comparaisons nécessitent un appel de fonction ou une autre logique complexe, le tri par tas ascendant est avantageux.

Ceci est accompli en améliorant la siftDownprocédure. Le changement améliore quelque peu la phase de construction de tas en temps linéaire, mais est plus important dans la deuxième phase. Comme le tas ordinaire, chaque itération de la deuxième phase extrait le haut du tas, un [0] , et comble le vide qu'il laisse avec un [ end ] , puis filtre ce dernier élément dans le tas. Mais cet élément provient du niveau le plus bas du tas, ce qui signifie qu'il s'agit de l'un des plus petits éléments du tas, donc le criblage prendra probablement de nombreuses étapes pour le faire redescendre. Dans le tri par tas ordinaire, chaque étape du tri sélectif nécessite deux comparaisons, pour trouver le minimum de trois éléments : le nouveau nœud et ses deux enfants.

Le tri de tas ascendant trouve à la place le chemin des enfants les plus grands jusqu'au niveau feuille de l'arbre (comme s'il insérait −∞) en utilisant une seule comparaison par niveau. En d'autres termes, il trouve une feuille qui a la propriété que lui et tous ses ancêtres sont supérieurs ou égaux à leurs frères et sœurs. (En l'absence de clés égales, cette feuille est unique.) Ensuite, à partir de cette feuille, elle recherche vers le haut (en utilisant une comparaison par niveau) la position correcte dans ce chemin pour insérer un [ fin ] . Il s'agit du même emplacement que les recherches de tri de tas ordinaires et nécessite le même nombre d'échanges pour effectuer l'insertion, mais moins de comparaisons sont nécessaires pour trouver cet emplacement.

Parce qu'il va jusqu'en bas puis remonte, il est appelé tri en tas avec rebond par certains auteurs.

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

La valeur de retour de leafSearchest utilisée dans la siftDownroutine modifiée :

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

Le tri par tas ascendant a été annoncé comme battant le tri rapide (avec une sélection de pivot médiane sur trois) sur des tableaux de taille ≥16000.

Une réévaluation de cet algorithme en 2008 a montré qu'il n'était pas plus rapide que le tri par tas ordinaire pour les clés entières, probablement parce que la prédiction de branche moderne annule le coût des comparaisons prévisibles que le tri par tas ascendant parvient à éviter.

Un raffinement supplémentaire effectue une recherche binaire dans le chemin vers la feuille sélectionnée, et trie dans le pire des cas de ( n +1)(log 2 ( n +1) + log 2 log 2 ( n +1) + 1,82) + O (log 2 n ) comparaisons, approchant la limite inférieure information théorétique de n log 2 n - 1.4427 n comparaisons.

Une variante qui utilise deux bits supplémentaires par nœud interne ( n -1 bits au total pour un tas de n éléments) pour mettre en cache les informations sur l'enfant le plus grand (deux bits sont nécessaires pour stocker trois cas : gauche, droite et inconnu) utilise moins que n log 2 n + 1,1 n se compare.

Autres variantes

  • Le tri de tas ternaire utilise un tas ternaire au lieu d'un tas binaire ; c'est-à-dire que chaque élément du tas a trois enfants. Il est plus compliqué à programmer, mais effectue un nombre constant de fois moins d'opérations d'échange et de comparaison. En effet, chaque étape de filtrage dans un tas ternaire nécessite trois comparaisons et un échange, alors que dans un tas binaire, deux comparaisons et un échange sont nécessaires. Deux niveaux dans un tas ternaire couvrent 3 2 = 9 éléments, faisant plus de travail avec le même nombre de comparaisons que trois niveaux dans le tas binaire, qui ne couvrent que 2 3 = 8. Ceci est principalement d'intérêt académique, ou comme exercice d'étudiant , car la complexité supplémentaire ne vaut pas les économies mineures, et le tri par tas ascendant bat les deux.
  • Heapsort à mémoire optimisée améliore la localité de référence de heapsort en augmentant encore plus le nombre d'enfants. Cela augmente le nombre de comparaisons, mais comme tous les enfants sont stockés consécutivement en mémoire, cela réduit le nombre de lignes de cache auxquelles on accède pendant la traversée du tas, une nette amélioration des performances.
  • Le tri par tas hors place améliore le tri par tas ascendant en éliminant le pire des cas, garantissant des comparaisons n log 2 n + O ( n ) . Lorsque le maximum est atteint, plutôt que de remplir l'espace libéré avec une valeur de données non triée, remplissez-le avec une valeur sentinelle −∞ , qui ne « rebondit » jamais. Il s'avère que cela peut être utilisé comme primitive dans un algorithme "QuickHeapsort" en place (et non récursif). Tout d'abord, vous effectuez une passe de partitionnement de type tri rapide, mais en inversant l'ordre des données partitionnées dans le tableau. Supposons ( sans perte de généralité ) que la plus petite partition soit celle plus grande que le pivot, qui devrait aller à la fin du tableau, mais notre étape de partitionnement inversé la place au début. Formez un tas à partir de la plus petite partition et effectuez un tri de tas sur celle-ci, en échangeant les maxima extraits avec les valeurs de la fin du tableau. Celles-ci sont inférieures au pivot, c'est-à-dire inférieures à n'importe quelle valeur du tas, elles servent donc de valeurs sentinelles −∞ . Une fois le tri par tas terminé (et le pivot déplacé juste avant la fin maintenant triée du tableau), l'ordre des partitions a été inversé et la plus grande partition au début du tableau peut être triée de la même manière. (Parce qu'il n'y a pas de récursivité sans queue , cela élimine également l' utilisation de la pile O (log n ) de quicksort .)
  • L' algorithme smoothsort est une variante du heapsort développé par Edsger Dijkstra en 1981. Comme heapsort, la limite supérieure de smoothsort est O ( n log n ) . L'avantage de smoothsort est qu'il se rapproche du temps O ( n ) si l' entrée est déjà triée dans une certaine mesure , alors que le tri par tas fait la moyenne de O ( n log n ) quel que soit l'état de tri initial. En raison de sa complexité, smoothsort est rarement utilisé.
  • Levcopoulos et Petersson décrivent une variante de tri en tas basée sur un tas d' arbres cartésiens . Tout d'abord, un arbre cartésien est construit à partir de l'entrée en temps O ( n ) , et sa racine est placée dans un tas binaire à 1 élément. Ensuite, nous extrayons à plusieurs reprises le minimum du tas binaire, sortons l'élément racine de l'arbre et ajoutons ses enfants gauche et droit (le cas échéant) qui sont eux-mêmes des arbres cartésiens, au tas binaire. Comme ils le montrent, si l'entrée est déjà presque triée, les arbres cartésiens seront très déséquilibrés, avec peu de nœuds ayant des enfants gauche et droit, ce qui fera que le tas binaire restera petit et permettra à l'algorithme de trier plus rapidement que O ( n log n ) pour les entrées qui sont déjà presque triées.
  • Plusieurs variantes telles que le tri par tas faible nécessitent n log 2 n + O (1) comparaisons dans le pire des cas, proche du minimum théorique, en utilisant un bit d'état supplémentaire par nœud. Bien que ce bit supplémentaire rend les algorithmes pas vraiment en place, si de l'espace peut être trouvé à l'intérieur de l'élément, ces algorithmes sont simples et efficaces, mais toujours plus lents que les tas binaires si les comparaisons de clés sont suffisamment bon marché (par exemple, les clés entières) qu'un facteur constant n'a pas d'importance.
  • Le "sort de tas ultime" de Katajainen ne nécessite aucun stockage supplémentaire, effectue des comparaisons n log 2 n + O (1) et un nombre similaire de déplacements d'éléments. Elle est cependant encore plus complexe et ne se justifie que si les comparaisons sont très coûteuses.

Comparaison avec d'autres sortes

Heapsort est principalement en concurrence avec quicksort , un autre algorithme de tri basé sur la comparaison sur place à usage général très efficace.

Les principaux avantages de Heapsort sont son code simple et non récursif , son exigence de stockage auxiliaire minimale et ses bonnes performances fiables : ses meilleurs et pires cas se situent dans un petit facteur constant l'un de l'autre et de la limite inférieure théorique des tris de comparaison . Bien qu'il ne puisse pas faire mieux que O ( n log n ) pour les entrées pré-triées, il ne souffre pas non plus du pire des cas O ( n 2 ) de quicksort . (Ce dernier peut être évité avec une implémentation prudente, mais cela rend le tri rapide beaucoup plus complexe, et l'une des solutions les plus populaires, introsort , utilise le tri par tas à cette fin.)

Ses principaux inconvénients sont sa faible localité de référence et sa nature intrinsèquement sérielle ; les accès à l'arbre implicite sont largement dispersés et pour la plupart aléatoires, et il n'y a pas de moyen simple de le convertir en un algorithme parallèle .

Cela le rend populaire dans les systèmes embarqués , l'informatique en temps réel et les systèmes concernés par des entrées choisies de manière malveillante, tels que le noyau Linux. C'est également un bon choix pour toute application qui ne s'attend pas à un goulot d' étranglement lors du tri.

Un tri rapide bien mis en œuvre est généralement 2 à 3 fois plus rapide qu'un tri en tas. Bien que le tri rapide nécessite moins de comparaisons, il s'agit d'un facteur mineur. (Les résultats revendiquant deux fois plus de comparaisons mesurent la version descendante ; voir § Tri par tas ascendant .) Le principal avantage du tri rapide est sa bien meilleure localité de référence : le partitionnement est un balayage linéaire avec une bonne localité spatiale, et la subdivision récursive a une bonne localité temporelle. Avec un effort supplémentaire, le tri rapide peut également être implémenté dans du code principalement sans branche , et plusieurs processeurs peuvent être utilisés pour trier les sous-partitions en parallèle. Ainsi, le tri rapide est préféré lorsque les performances supplémentaires justifient l'effort de mise en œuvre.

L'autre algorithme de tri majeur O ( n log n ) est le tri par fusion , mais il est rarement en concurrence directe avec le tri par tas car il n'est pas en place. L'exigence du tri par fusion pour l' espace supplémentaire Ω( n ) (environ la moitié de la taille de l'entrée) est généralement prohibitive, sauf dans les situations où le tri par fusion a un net avantage :

  • Lorsqu'un tri stable est requis
  • En tirant parti de l'entrée (partiellement) pré-triée
  • Tri des listes chaînées (auquel cas le tri par fusion nécessite un minimum d'espace supplémentaire)
  • Tri parallèle; Le tri par fusion est encore mieux parallélisé que le tri rapide et peut facilement atteindre une accélération proche de la linéaire
  • Tri externe ; le tri par fusion a une excellente localité de référence

Exemple

Soit { 6, 5, 3, 1, 8, 7, 2, 4 } la liste que nous voulons trier du plus petit au plus grand. (REMARQUE, pour l'étape « Construire le tas » : les nœuds les plus gros ne restent pas en dessous des parents de nœuds plus petits. Ils sont échangés avec les parents, puis vérifiés de manière récursive si un autre échange est nécessaire, pour conserver les plus grands nombres au-dessus des plus petits nombres sur l'arbre binaire du tas .)

Un exemple sur le tri en tas.
1. Construisez le tas
Tas élément nouvellement ajouté échanger des éléments
nul 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5 , 3, 1, 8 5, 8
6 , 8 , 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3 , 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1 , 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1
2. Tri
Tas échanger des éléments supprimer l'élément tableau trié détails
8 , 6, 7, 4, 5, 3, 2, 1 8, 1 échanger 8 et 1 afin de supprimer 8 du tas
1, 6, 7, 4, 5, 3, 2, 8 8 supprimer 8 du tas et ajouter au tableau trié
1 , 6, 7 , 4, 5, 3, 2 1, 7 8 échangez 1 et 7 car ils ne sont pas en ordre dans le tas
7, 6, 1 , 4, 5, 3 , 2 1, 3 8 échangez 1 et 3 car ils ne sont pas en ordre dans le tas
7 , 6, 3, 4, 5, 1, 2 7, 2 8 échanger 7 et 2 afin de supprimer 7 du tas
2, 6, 3, 4, 5, 1, 7 7 8 supprimer 7 du tas et ajouter au tableau trié
2 , 6 , 3, 4, 5, 1 2, 6 7, 8 échangez 2 et 6 car ils ne sont pas en ordre dans le tas
6, 2 , 3, 4, 5 , 1 2, 5 7, 8 échangez 2 et 5 car ils ne sont pas en ordre dans le tas
6 , 5, 3, 4, 2, 1 6, 1 7, 8 échanger 6 et 1 afin de supprimer 6 du tas
1, 5, 3, 4, 2, 6 6 7, 8 supprimer 6 du tas et ajouter au tableau trié
1 , 5 , 3, 4, 2 1, 5 6, 7, 8 échangez 1 et 5 car ils ne sont pas en ordre dans le tas
5, 1 , 3, 4 , 2 1, 4 6, 7, 8 échangez 1 et 4 car ils ne sont pas en ordre dans le tas
5 , 4, 3, 1, 2 5, 2 6, 7, 8 échanger 5 et 2 afin de supprimer 5 du tas
2, 4, 3, 1, 5 5 6, 7, 8 supprimer 5 du tas et ajouter au tableau trié
2 , 4 , 3, 1 2, 4 5, 6, 7, 8 échangez 2 et 4 car ils ne sont pas en ordre dans le tas
4 , 2, 3, 1 4, 1 5, 6, 7, 8 échanger 4 et 1 afin de supprimer 4 du tas
1, 2, 3, 4 4 5, 6, 7, 8 supprimer 4 du tas et ajouter au tableau trié
1 , 2, 3 1, 3 4, 5, 6, 7, 8 échangez 1 et 3 car ils ne sont pas en ordre dans le tas
3 , 2, 1 3, 1 4, 5, 6, 7, 8 échanger 3 et 1 afin de supprimer 3 du tas
1, 2, 3 3 4, 5, 6, 7, 8 supprimer 3 du tas et ajouter au tableau trié
1 , 2 1, 2 3, 4, 5, 6, 7, 8 échangez 1 et 2 car ils ne sont pas en ordre dans le tas
2 , 1 2, 1 3, 4, 5, 6, 7, 8 échanger 2 et 1 afin de supprimer 2 du tas
1, 2 2 3, 4, 5, 6, 7, 8 supprimer 2 du tas et ajouter au tableau trié
1 1 2, 3, 4, 5, 6, 7, 8 supprimer 1 du tas et ajouter au tableau trié
1, 2, 3, 4, 5, 6, 7, 8 terminé

Remarques

Les références

Liens externes