Tri par tas

Tri par tas
Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.
Animation montrant le fonctionnement du tri par tas (Heapsort).

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 à n \ \log \ n n est la longueur du tableau à trier; contrairement au tri rapide qui atteint une complexité au pire en O(n2).

Par ailleurs, cet algorithme est en place, c'est-à-dire qu'il ne nécessite pas l'allocation d'une zone mémoire supplémentaire en plus de celle contenant les données d'entrée.

L'inconvénient majeur de ce tri est sa lenteur en moyenne comparée au tri rapide. En effet, un tri par tas sur un nombre de données élevé (et donc un tableau de taille importante) sera amené à traiter des emplacements mémoire éloignés, dépassant parfois la capacité du cache, ralentissant ainsi l'accès à la mémoire et donc la rapidité du tri.

Sommaire

Principe

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 ne élément a pour enfants les éléments 2n et 2n + 1. Si le tableau n'est pas de taille (2n − 1), 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).

Comme expliqué plus haut, un tas ou un arbre binaire presque complet peut être stocké dans un tableau, en posant que les deux descendants de l'élément d'indice n sont les éléments d'indices 2n et 2n + 1 (pour un tableau indicé à partir de 1). En d'autres termes, les nœuds de l'arbre sont placés dans le tableau ligne par ligne, chaque ligne étant décrite de gauche à droite.

Une fois le tas de départ obtenu, l'opération de base de ce tri est le tamisage, ou percolation, d'un élément, supposé le seul « mal placé » dans un arbre qui est presque un tas. Plus précisément, considérons un arbre A = A[1] dont les deux sous-arbres (A[2] et A[3]) sont des tas, tandis que la racine est éventuellement plus petite que ses fils. L'opération de tamisage consiste à échanger la racine avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'elle soit à sa place.

Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de bas en haut (par taille croissante) et de droite à gauche.

Pour trier un tableau à partir de ces opérations, on commence par le transformer en tas. On échange la racine avec le dernier élément du tableau, et on restreint le tas en ne touchant plus au dernier élément, c'est-à-dire à l'ancienne racine. On tamise la racine dans le nouveau tas, et on répète l'opération sur le tas restreint jusqu'à l'avoir vidé et remplacé par un tableau trié.

Pseudo-code

On fait l'hypothèse que l'arbre est un tableau indexé entre 1 et longueur. arbre[i] désigne le i-ème élément de ce tableau.

fonction tamiser(arbre,nœud,n): {descend arbre[nœud] à sa place, sans dépasser l'indice n}
  k:=nœud
  j:=2k
  tant que j<=n
    si j<n et arbre[j]<arbre[j+1]
      j:=j+1
    fin si
    si arbre[k]<arbre[j]
      échanger arbre[k] et arbre[j]
      k:=j
      j:=2k
    sinon
      terminer
    fin si
  fin tant que
fin fonction
fonction tri_par_tas(arbre,longueur):
  pour i:=longueur/2 a 1
    tamiser(arbre,i,longueur)
  fin pour
  pour i:=longueur a 2
    échanger arbre[i] et arbre[1]
    tamiser(arbre,1,i-1)
  fin pour
fin fonction

À la fin de la fonction tri_par_tas le tableau arbre est trié suivant l'ordre croissant. Il suffit d'inverser les opérateurs de comparaison pour obtenir un tri dans l'ordre décroissant.

Analyse

Cet algorithme permet de trier sur place les éléments d'un tableau en un temps de l'ordre de n \ \log_2 \ n , où n est le nombre d'éléments à trier. Le complexité entre le meilleur des cas et le pire des cas ne varie que d'un facteur constant[1]. L'étape la plus coûteuse de l'algorithme est la seconde boucle, c'est-à-dire l'extraction des éléments du tas. La première étape, consistant à construire le tas, est effectuée en temps linéaire en n.

Les principaux atouts de cette méthode sont la faible consommation mémoire et l'efficacité, optimale étant donné qu'on ne fait aucune hypothèse sur la nature des données à trier.

Amélioration possible

  • Quand le tableau est déjà trié, le tri par tas le mélange d'abord avant de le retrier. L'algorithme Smoothsort a pour but de pallier cet inconvénient.
  • À la fin du tri par tas, pour les 15 derniers éléments environ, l'algorithme effectue plusieurs fois de suite les mêmes inversions, ce qui est inutile. On peut à la place arrêter l'algorithme quand il n'y a plus beaucoup d'éléments et passer à un autre. Les données qui restent sont à peu près triées à l'envers. On peut donc, par exemple, retourner les données restantes (avec une inversion du 1er et du dernier, du 2e et de l'avant-dernier etc.) puis effectuer un tri par insertion.

Notes et références

Sur les autres projets Wikimedia :


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tri par tas de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Tri par sélection — Le tri par sélection (ou tri par extraction) est un algorithme de tri par comparaison. Il est particulièrement simple, mais inefficace sur de grandes entrées, car il s exécute en temps quadratique en le nombre d éléments à trier. Sommaire 1… …   Wikipédia en Français

  • Tri par selection — Tri par sélection Le tri par sélection (ou tri par extraction) est un des algorithmes de tri les plus triviaux. Il consiste en la recherche soit du plus grand élément (ou le plus petit) que l on va replacer à sa position finale c est à dire en… …   Wikipédia en Français

  • Tri par dénombrement — Tri comptage Le tri comptage (appelé aussi tri casier) est un algorithme de tri qui s applique sur des valeurs entières. Sommaire 1 Définition 2 Exemple 3 Algorithme 4 Implémentation …   Wikipédia en Français

  • Tri par base — Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base… …   Wikipédia en Français

  • Tri par insertion — Exemple du tri par insertion utilisant une liste de nombres aléatoires Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C est le tri que la plupart des personnes utilisent naturellement pour trier des… …   Wikipédia en Français

  • Tri par paquets — Le tri par paquets est un algorithme de tri qui fonctionne sur des nombres réels appartenant à un intervalle borné fixé à l avance. Le principe de ce tri consiste à diviser l intervalle d entrée en petits sous intervalles identiques et à répartir …   Wikipédia en Français

  • Tri fusion — appliqué à un tableau de 7 éléments. Le tri fusion est un algorithme de tri stable par comparaison. Sa complexité temporelle pour une entrée de taille n est de l ordre de n log n, ce qui est asymptotiquement optimal. Le tri fusion se décrit… …   Wikipédia en Français

  • Tas (mathématique) — Tas (informatique) Pour les articles homonymes, voir Tas. Un exemple de tas En informatique, un tas, en anglais …   Wikipédia en Français

  • Tas binaire — Tas (informatique) Pour les articles homonymes, voir Tas. Un exemple de tas En informatique, un tas, en anglais …   Wikipédia en Français

  • Tri stable — Algorithme de tri Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d organiser une collection d objets selon un ordre déterminé. Les objets à trier font donc partie d un ensemble muni d une relation d ordre… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”