Algorithmes de tri ; performances.

Tout programmeur est confronté un jour à la nécessité de faire appel à un programme de tri de données par exemple, trier les noms d'une liste, classer des nombres dans l'ordre croissant,...
Il existe une quantité impressionnante de tris. Voici quelques-uns des plus classiques.

  • Tri Bulles
    Principe : 
    Soit un tableau de $n$ entiers.
    On compare successivement $2$ éléments consécutifs en partant du dernier élément.
    Chaque fois que deux éléments ne sont pas dans l'ordre voulu, on les échange.
    Après un examen de tous les couples, l'élément le plus petit se retrouve en 1ère position.
    On recommence pour les $n - 1$ derniers éléments afin d'amener le plus petit d'entre eux en deuxième position.
    Après au plus $ n - 1$ examens, le tableau est trié.
    On appelle ce tri du nom de tri bulle (en anglais bubble sort) car les plus petits éléments remontent petit à petit à leur place.
    Algorithme  : tribulles
    Complexité :
    - Quel est le meilleur des cas ?
    Déterminer en fonction de $n$ le nombre $N_{min}$ de comparaisons à faire pour trier le tableau $T$
    - Quel est le pire  des cas ?
    Déterminer en fonction de $n$ le nombre $N_{max}$ de comparaisons à faire pour trier le tableau $T$
  • Tri sélection
    • Sélection du maximum
      Principe :
      Soit un tableau $T[1],T[2],\cdots,T[n]$
      On recherche le plus grand élément soit par exemple $T[i]$.
      On échange alors $T[j]$ et $T[n]$.
      On recommence cette démarcha sur le reste du tableau $T[1],T[2],\cdots,T[n - 1]$
      puis sur  $T[1],T[2],\cdots,T[n - 2]$ etc ... jusqu'à qu'il ne reste plus qu'un seul élément le plus petit.
      Algorithme : triselectionmax
    • Sélection du minimum
      Principe : 
      Soit un tableau $T[1],T[2],\cdots,T[n]$
      On recherche le plus petit élément soit par exemple $T[i]$.
      On échange alors $T[j]$ et $T[1]$.
      On recommence cette démarcha sur le reste du tableau $T[2],T[3],\cdots,T[n]$
      puis sur  $T[3],T[4],\cdots,T[n]$ etc ... jusqu'à qu'il ne reste plus qu'un seul élément le plus grand.
      algorithme : triselectionmin
    • Complexité :
      Déterminer en fonction de $n$ le nombre $N$ de comparaisons à faire pour trier le tableau $T$.
      Justifier.
      Si l'on prend comme paramètre la taille $n$ des données et comme opération élémentaire la comparaison, déterminer la complexité de cet algorithme en temps $t$ d'exécution.
  • Tri par insertion
  • Tri baquets (Mines Ponts 2004)