Le problème du tri.

Pour avoir une idée de la difficulté du problème, vous allez trier les tonneaux par ordre de masse croissante par « glisser-déposer ».
La balance non étalonnée vous permet de comparer 2 tonneaux (l’équivalent du test en algorithme).
Les étagères servent de stockage intermédiaire (l’équivalent des variables).
Objectif : trier ces tonneaux en faisant le moins de comparaisons et d’échanges possibles.




Aperçu des différentes méthodes

Tri par sélection

méthode itérative

Sur un tableau de taille n (les éléments sont indexés de 0 à n-1), le principe du tri par sélection est le suivant :

  • rechercher le plus petit élément du tableau, et l’échanger avec l’élément d’indice 0
  • rechercher le 2e plus petit élément du tableau, et l’échanger avec l’élément d’indice 1
  • rechercher le 3e plus petit élément du tableau, et l’échanger avec l’élément d’indice 2
  • etc … jusqu’à ce que le tableau soit entièrement trié

L’algorithme est :

Pour i allant de 0 à n-2 faire
  min = i
  Pour j allant de i+1 à n-1 faire
    Si t[j] < t[min] Alors min = j FinSi
  FinPour
  Si min ≠ i Alors échanger t[i] et t[min]
FinPour

Rappel : Pour échanger 2 valeurs A et B, il faut utiliser une 3ème variable temporaire (pour mémoriser la valeur initiale avant le 1er transfert) :

temp = A
A = B
B = temp

void tri_selection(int tab[], int taille) {
  int min, temp;
  // tant qu'il reste des éléments non triés
  for( int i = 0 ; i < taille-1 ; i++) {
    min = i;
    //on recherche le plus petit élément à droite
    for( int j = i+1; j < taille ; j++) {   
      if (tab[j] < tab[min]) min = j;
    }
    //et on échange (pour ranger le petit élément à gauche)
    if (min != i) {
        temp = tab[i];
        tab[i] = tab[min];
        tab[min] = temp;     
    }  
  }
}

NB : Bien entendu, le tri par sélection peut se faire aussi avec le plus grand élément (au lieu du plus petit).

Le tri par sélection peut aussi être utilisé sur des listes : le principe est identique, mais au lieu de déplacer les éléments par échange, on réalise des suppressions et insertions dans la liste.

méthode récursive

Le tri par sélection peut se faire de manière récursive :

  1. On sort à chaque fois un élément du tableau : le plus petit (ou le plus grand, c’est selon).
  2. La taille du tableau restant à trier, diminue alors de 1.
  3. On ré-applique l’algorithme de tri sur ce tableau de taille n-1 : comme l’algorithme  s’appelle lui-même, on dit qu’il est récursif (tel une formule de récurrence).
  4. etc … On s’arrête lorsque le tableau est de taille 1

Dans un algorithme récursif, il faut toujours prévoir une condition d’arrêt (ici, c’est lorsque la taille du tableau est 1).

void tri_selection_recursif(int tab[], int taille) {
    //si le tableau n'a qu'un élément, on sort (car tableau déjà trié)
    if(taille <= 1)
        return;

    //sinon on cherche le plus grand élément du tableau
    int min = 0;  
    for( int i = 1 ; i < taille ; i++) {   
      if (tab[i] > tab[min]) min = i;
    }    
    
    // on échange le dernier élément avec le plus grand
    if (min != i) {
        int temp = tab[i];
        tab[i] = tab[min];
        tab[min] = temp;     
    } 

    // on rappelle la fonction en diminuant la taille du tableau
    return tri_selection_recursif(tab, taille-1);
}

calcul de la complexité

Le tri par sélection effectue beaucoup de comparaisons de deux éléments et relativement peu d’échanges.

Combien de comparaisons ?

  • À la 1ère itération, on effectue n−1 comparaisons.
  • À la i-ème itération, on effectue donc n−i comparaisons (puisque à chaque itération on décrémente la taille du tableau).

Au total pour i = 1 à n-1 :  ∑ (n – i) = n(n – 1) / 2 = n²/2 – n/2

On dit que la complexité (en comparaisons) de cet algorithme est quadratique : O(n²).
Ce qui signifie que si on double la taille du tableau, il faudra 4 fois plus de temps pour le trier.
A titre de comparaison, le tri par fusion est un meilleur algorithme car il est de l’ordre de O(n log n).

Combien d’échanges ?

Au maximum, le tri par sélection effectue n échanges.

Tri par fusion

Ce tri est basé sur la technique algorithmique « diviser pour régner« , puis fusionner 2 listes triés en une seule.

Cette fusion est rapide car le plus petit élément de la liste à construire est soit le plus petit élément de la 1ère liste, soit le plus petit élément de la 2ème. Cette fusion est en temps linéaire.

fonction triFusion(T[1, …, n])
  Si n ≤ 1 
    Alors retourner T
    Sinon retourner fusion(triFusion(T[1, …, n/2]), triFusion(T[n/2 + 1, …, n]))
  FinSi

fonction fusion(A[1, …, a], B[1, …, b])
  Si A est le tableau vide Alors retourner B FinSi
  Si B est le tableau vide Alors retourner A FinSi
  Si A[1] ≤ B[1]
     Alors retourner A[1] , fusion(A[2, …, a], B)
     Sinon retourner B[1] , fusion(A, B[2, …, b])
  FinSi

La fusion de A et B est en O(a+b) où a est la taille de A et b est la taille de B.
Le tri fusion d’un tableau T est en O(n log n) où n est la taille du tableau T.

sources :
https://visualgo.net/sorting
http://lwh.free.fr/pages/algo/tri/tri.htm
http://cathyatseneca.github.io/DSAnim