Algorithmes de tri

Tri par sélection

Implémentation Python

					
from random import randint

L = [randint(1,100) for i in range(20)]

def tri_selection(L):
    n = len(L)
    
    for i in range(0, n):
        
        mini = i
        for j in range(i+1, n) : # on parcourt la partie du tableau située APRÈS l'indice i
            if L[j] < L[mini] :
                mini = j
        
        if mini != i :
            temp = L[i]
            L[i] = L[mini]
            L[mini] = temp
            # les trois lignes précédentes peuvent s'écrire aussi L[i], L[mini] = L[mini], L[i]
   
    return L

print(L)
print(tri_selection(L))					
			

1. Les lignes correspondant à la recherche de minimum sont les lignes 11 à 14.
2. La variable mini correspond à un indice dans tableau, pas un de ses éléments ! Après la ligne 15, mini contient l'indice du minimum du sous-tableau considéré (de l'indice i+1 à l'indice n-1
3. Les lignes 16 à 20 correspondent aux instructions pour permuter l'élément d'indice i et celui d'indice mini dans le cas où c'est nécessaire ( c'est à dire quand i != mini ).
   Comme indiqué, il existe en Python une façon plus simple de permuter les valeurs de deux variables.
4. à la ligne 12 on peut lire : pour j de i + 1 à n - 1.
   En effet dans la recherche de minimum, on compare les éléments du sous-tableau deux à deux. Il n'est pas nécessaire de comparer le premier élément à lui même (à la ligne 13 on compare t[j] et t[mini] avec mini = i initialement.)

Coût en temps

1. Pour trouver le premier minimum on fait n-1 comparaisons
2. Pour trouver le premier minimum on fait n-2 comparaisons
3. Pour trouver le premier minimum on fait n-3 comparaisons
4. ...
5. Pour trouver tous les minimums successifs on réalise (n-1) + (n-2) + .... + 1 comparaisons.
   
6. Le nombre de comparaisons, et donc le coût temporel, est alors : n(n-1)/2 = (1/2)(n²-n).

Pour de grandes valeurs de n, cette expression tend vers n²; cet algorithme est donc de complexité O(n²).

Tri par insertion

Implémentation

def tri_insertion(L):
    for i in range(1, len(L)):
        
        temp = L[i]
        j = i
        
        while  j> 0 and L[j-1] > temp:
            L[j] = L[j-1]
            j = j-1 
        L[j] = temp	# on insère l'élément à sa place
    
    return L						
						

1. Les lignes correspondant à la recherche de l'endroit ou placer l'élément courant sont les lignes 8, 9 et 10.
2. On sauvegarde l'élément à déplacer avant de trouver sa place à la ligne 5; on le place à la "bonne" place à la ligne 11.
3. On réalise le "décalage vers la droite du tableau" des éléments à la ligne 9.
4. La ligne "décrémenter j" ( ligne 10 ) correspond au décalage vers la gauche lors de la recherche de la place de l'élément courant.
5. Dans la boucle i ( ligne 3 ), la borne maximum est n-1 car le dernier éléments du tableau est indicé "0" donc le dernier est indicé "n-1".

Coût en temps

Dans le pire des cas, le raisonnement est exactement le même que pour le tri par sélection ( présence de deux boucles imbriquées ).

On peut cependant noter que dans le cas du tri par sélection, on recherche systématiquement le minimum dans le reste du tableau non trié, que l'on est donc obligé de parcourir.
Par contre, dans le tri par sélection, on arrête le "parcours à rebours" de la partie triée du tableau dès que l'on a trouvé la place où insérer l'élément courant; la position de cette place n'est pas forcément au tout début de la partie triée, ce qui fait que ce parcours ne concerne parfois qu'un petit nombre d'éléments : en moyenne, le tri par insertion a donc un coût en temps qui est meilleure que le tri par sélection...

Cela se ressent dans la durée d'exécution du chaque script sur le même tableau non trié. Ceci illustre d'ailleurs le fait qu'il ne faut pas confondre complexité d'un algorithme et temps d'exécution du programme qui l'implémente : ces deux algorithmes sont de complexité O(n²), mais le tri par insertion est quand même souvent plus rapide...