7.2 - Algorithme Tri par insertion, par sélection

Algorithmique¶

Tris par insertion, par sélection¶

Capacités attendues :

Écrire un algorithme de tri.
Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.

Commentaires :

La terminaison de ces algorithmes est à justifier.
On montre que leur coût est quadratique dans le pire cas.

Tri par insertion¶

lwh. Merci!
Autre vidéo

L'idée principale du tri par insertion est de construire progressivement une sous-séquence triée au début du tableau. À chaque étape, on prend un élément de la partie non triée et on l'insère à sa place appropriée dans la partie triée.

Début : Au départ, seul le premier élément est considéré comme trié.

Processus :

Sélectionnez l'élément suivant : Commencez par le deuxième élément, car le premier est déjà considéré comme trié.
Trouvez la position correcte : Comparez cet élément avec ceux de la partie triée (à gauche de l'élément) et déplacez tous les éléments qui sont plus grands d'une position vers la droite. Cela crée un espace où l'élément sélectionné peut être inséré.
Insérez l'élément : Placez l'élément à sa position correcte dans la partie triée.
Répétez : Répétez ces étapes pour chaque élément jusqu'à ce que vous atteigniez la fin du tableau.

Fin : Le processus se termine lorsque tous les éléments ont été insérés dans la partie triée, ce qui signifie que le tableau est entièrement trié.

Exemple :¶

Prenons le tableau [4, 3, 5, 1] comme exemple.

Étape 1 : Le tableau commence avec [4 | 3, 5, 1]. 4 est considéré comme trié.
Étape 2 : Insérez 3. Le tableau devient [3, 4 | 5, 1].
Étape 3 : Insérez 5. Le tableau reste [3, 4, 5 | 1], car 5 est déjà plus grand que 4.
Étape 4 : Insérez 1. Le tableau devient [1, 3, 4, 5].

In [3]:

def tri_insertion(tab):
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[i]
        j = i
        while j > 0 and valeur_insertion < tab[j-1]:
            tab[j] = tab[j-1]
            j = j - 1
        tab[j] = valeur_insertion
    return tab

# Exemple d'utilisation
tab = [4, 3, 5, 1]
print("Tableau trié:",tri_insertion(tab) )

Tableau trié: [1, 3, 4, 5]

Invariant de boucle : À la fin de chaque itération de la boucle externe, les éléments dans le sous-tableau tableau[0,...,i-1] sont triés.

Terminaison : Le tri par insertion termine car la boucle externe itère de 1 à n, ce qui est une séquence finie.
De plus, la boucle interne se termine dès que j devient négatif ou dès que tableau[j] <= clé.

Tri par sélection¶

lwh. Merci!
Autre vidéo

Le tri par sélection est une méthode de tri qui divise le tableau en deux parties : une partie triée et une partie non triée.
À chaque étape, il trouve le plus petit élément de la partie non triée et l'échange avec le premier élément non trié.

Début : Considérez le tableau entier comme non trié.

Processus :

Recherchez le plus petit élément : Trouvez le plus petit élément dans la partie non triée du tableau.
Échangez-le avec le premier élément non trié : Échangez ce plus petit élément trouvé avec l'élément situé au début de la partie non triée.
Considérez cet élément comme trié : Déplacez la frontière entre la partie triée et la partie non triée d'une position vers la droite.
Répétez : Répétez ces étapes pour chaque élément dans la partie non triée du tableau.

Fin : Le processus se termine lorsque la partie non triée du tableau est vide, ce qui signifie que le tableau est entièrement trié.

Exemple :¶

Considérons le tableau [4, 3, 5, 1].

Étape 1 : Le plus petit élément dans la partie non triée [4, 3, 5, 1] est 1. 
          Échangez 1 avec 4. 
          Le tableau devient [1 | 3, 5, 4].
          
Étape 2 : Le plus petit élément dans la partie non triée [3, 5, 4] est 3. 
          Il est déjà en première position, donc pas d'échange nécessaire. 
          Le tableau reste [1, 3 | 5, 4].
          
Étape 3 : Le plus petit élément dans [5, 4] est 4. 
          Échangez 4 avec 5. 
          Le tableau devient [1, 3, 4 | 5].
          
Étape 4 : 5 est le seul élément restant dans la partie non triée. 
          Il est déjà en position correcte.

Le tableau final est [1, 3, 4, 5].

In [3]:

def tri_selection(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Exemple d'utilisation
arr = [12, 11, 13, 5, 6]
tri_selection(arr)
print("Tableau trié:", arr)

Tableau trié: [5, 6, 11, 12, 13]

Invariant de boucle :

À la fin de chaque itération de la boucle externe, les éléments dans le sous-tableau tableau[0,...,i] sont les i+1 plus petits éléments du tableau, et ils sont triés.

Terminaison :

Le tri par sélection termine car la boucle externe itère de 0 à len(arr)-1, ce qui est une séquence finie. La boucle interne est également finie, car elle itère de i+1 à len(arr)-1.

Coût des lgorithmes de tris par insertion, par sélection

Propriété :
Les algorithmes de tris par insertion, par sélection ont un coût O($n^2$), où $n$ est la taille du tableau.

Cela signifie que le temps d'exécution augmente de manière quadratrique avec le nombre d'éléments dans le tableau.

Démonstration :
Comme chaque boucle interne peut prendre jusqu'à $n$ itérations et il y a $n$ boucles externes, cela donne un total de $n×n=n^2$ opérations dans le pire cas.