Favicon
NSI Première

Algorithmes de tri

1. Tri par sélection

1.1. Questions sur l'algorithme

  1. Les lignes correspondant à la recherche de minimum sont les lignes 10 à 13.
  2. La variable mini correspond à un indice dans le tableau, pas un de ses éléments ! Après la ligne 13, mini contient l'indice du minimum du sous-tableau considéré (de l'indice i+1 à l'indice n-1
  3. Les lignes 15 et 16 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 ).
  4. à la ligne 11, on peut lire : pour j de i + 1 à n - 1 : ceci traduit la recherche du minimum dans la suite du tableau à partir de l'élément i, c'est à dire de i+1 à n-1.

1.2. Implémentation Python

					
from random import randint

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

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

1.3. Coût en temps

Il n'y a ici pas de "pire cas" ou de "meilleur cas" : dans tous les cas, il faut, pour chacun des éléments, parcourir l'intégralité du reste du tableau :

  • Pour i = 0 : j varie de 1 à n-1 soit n-1 comparaisons
  • Pour i = 1 : j varie de 2 à n-1, soit n-2 comparaisons
  • Pour i = 2 : j varie de 3 à n-1, soit n-3 comparaisons
  • ...
  • Pour i = n - 1 : 0 comparaison
Cout temporel du tri sélection
En vert, l'élément courant; en magenta, les éléments à parcourir pour la recherche de minimum

→ on fait donc en totalité : (n-1) + (n-2) + (n-3) + .... + 0 comparaisons = n(n-1)/2 = (1/2)(n2-n).

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

Un argument plus simple est la présence dans l'algorithme de deux boucles imbriquées :

  • la boucle i "tourne" n fois exactement : sa complexité est donc O(n).
  • la boucle j, par contre, tourne i fois : la complexité globale est donc i ⨯ O(n).
    Le problème est que i change à chaque itération : la dernière itération coûte bien O(n), mais la première seulement O(1) !
    Dans ce cas, on va cependant arrondir par excès, et considérer que i = n; la complexité globale de l'algorithme est donc : n ⨯ O(n) = O(n²)

2. Tri par insertion

2.1. Questions sur l'algorithme

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

2.2. 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 "bonne" place
        
        return L						
    						

    2.3. Coût en temps

    Dans le pire des cas, la "bonne place" de chaque élément est le tout début ( indice 0 ) du tableau ( le pire des cas pour cet algorithme est donc un tableau qui est initialement trié dans l'ordre décroissant ).

    Dans ce pire des cas, on doit alors faire, pour trouver la "bonne place" de chaque élément :

    • Pour i = 1 : j varie de 1 à 0 soit 1 décalage
    • Pour i = 2 : j varie de 2 à 0, soit 2 décalage
    • Pour i = 3 : j varie de 3 à 0, soit 3 décalage
    • ...
    • Pour i = n - 1 : j varie de n-1 à 0, soit n-1 décalages
    Cout temporel du tri insertion
    En vert, l'élément courant; en magenta, les éléments à décaler pour trouver la "bonne place" de l'élément courant dans le pire des cas

    → on fait donc en totalité : 1 + 2 + 3 + ... + (n-1) décalages = n(n-1)/2 = (1/2)(n2-n).

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

    Mais la complexité s'entend dans le pire des cas; or, dans le tri par insertion, 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, surtout si le tableau est d'origine déjà un peu trié : en moyenne, le tri par insertion a donc un coût en temps qui est meilleure que le tri par sélection...

    Animations de différents tris

    Animation montrant la vitesse d'exécution de différents algorithmes de tri dans différentes situations; on constate que le tri par sélection est systématiquement le moins rapide.
    Le tri par insertion est lui plus efficace sur des tableaux presque triés, c'est pourquoi on l'utilise parfois en complément d'autres algorithmes pour "finir le travail" 🙂...