Tri par sélection et insertion¶

Pourquoi trier ?¶

Commençons par un exercice pour illustrer l'importance du tri.

On rappelle que la médiane est la valeur qui partage une série statistiques en deux séries de même effectif. Il y a donc autant de valeurs inférieures à la médiane que de valeurs supérieures.

Exercice

Calculer la médiane des notes suivantes : 7 ; 4 ; 13 ; 14; 9 ; 2 ; 16

Que ce soit pour trier des fichiers par taille ou date, des noms de personnes par ordre alphabétique, les algorithmes de tri sont omniprésents.

Nous allons commencer par étudier concrètement le fonctionnement de deux algorithmes de tri différents :

Le tri par sélection
Le tri par insertion

Ce sont deux algorithmes de tri par comparaison, c'est à dire qui nécessitent de comparer deux éléments à chaque itération. On pourrait penser que pour trier on doit nécessairement comparer des éléments pour voir s'ils sont égaux, si l'un des deux est inférieur ou supérieur à l'autre, mais il n'en est rien.

Il existe des algorithmes qui ne reposent pas sur des comparaisons commme les algorithmes de tri par dénombrement.

Ensuite, nous prouverons ce qui s'appelle la terminaison et la correction de ces algorithmes.

Tri par sélection et insertion¶

Tri par sélection¶

Principe:

On cherche le plus petit élément du tableau et on l'échange avec celui qui est au début. Le premier élément est maintenant le plus petit
Maintenant on cherche le plus petit élément du tableau mais en partant du 2nd élément et on l'échange avec celui qui est placé deuxième. Les deux premiers éléments sont les plus petits et sont rangés.
On poursuit ainsi.

Exemple:

Pseudo code :

procédure TriSelection(tableau T, entier n)
    Pour i allant de 0 à n - 2
        min ← i
        Pour j allant de i + 1 à n-1
            Si T[j] < T[min]
                min ← j
        Si min ≠ i
            temp←T[i]
            T[i] ← T[min]
            T[min] ← temp

Tri par insertion¶

On trie les éléments les uns après les autres en les insérant à la bonne position dans la partie gauche déjà triée, et on continue jusqu’à la fin du tableau.

Exemple:

Pseudo code :

procédure TriInsertion2(tableau T, entier n)
    Pour i allant de 1 à n-1
        j ← i
        Tant que j > 0 et T[j-1] > T[j]
            échanger T[j] et T[j-1]
            j ← j – 1

Complexité algorithmique¶

Séries¶

Pour déterminer la complexité d'algorithmes, on utilise souvent certaines formules mathématiques, en particulier celles qui permettent de calculer les sommes de termes d'une suite.

La formule qui permet de calculer la somme des termes d'une suite arithmétique est à connaître :

\(\large{nombre \: de \: termes \times \frac{1er \: terme \: + \: dernier \: terme}{2}}\)

On s'intéresse à la complexité algorithmique dans le pire des cas (c'est à dire le scénario le plus défavorable) et dans le meilleur des cas.

On ne prendra en compte que les comparaisons (et pas les échanges) pour simplifier nos calculs.

Complexité du tri par selection :¶

Pire des cas et meilleur des cas¶

Dans le pire des cas comme dans le meilleur des cas le tri par insertion va effectuer : \(\large{(n - 1) \times \frac{n}{2}}\) comparaisons.

Complexité du tri par insertion :¶

Pire des cas¶

Dans le pire des cas le tableau est trié en ordre inverse. On effectue alors \(\large{(n - 1) \times \frac{n}{2}}\) comparaisons.

Meilleur des cas¶

Dans le meilleur des cas le tableau est déjà trié. On effectue alors \(\large{(n - 1)}\) comparaisons.

Bilan :¶

On remarque que bien que ces deux algorithmes de tri sont assez similaires, la complexité dans le meilleur des cas du tri par insertion est bien supérieure à celle de l'algorithme de tri par sélection.

Le tri par insertion n'est donc pas à négliger car il arrive souvent en pratique que les données traitées soient partiellement triées et qu'on ait pas de grandes quantités de données à manipuler.

Correction et terminaison¶

Lorsque nous souhaitons prouver qu'un algorithme renvoie bien le résultat attendu, nous devons prouver sa correction. Si on s'intéresse au fait qu'un algorithme s'arrête bien à un moment donné alors on étudiera sa terminaison.

Un algorithme peut être incorrect et se terminer. Cependant un algorithme correct doit forcément se terminer.

Invariant de boucle¶

Pour démontrer la correction des algorithmes de tri par sélection et insertion, nous allons utiliser un « invariant de boucle ».

Invariant de boucle

On appelle invariant de boucle une propriété qui est vraie avant et après chaque itération.

Preuve de correction

la démonstration se fait en trois étapes.

L'initialisation

On montre que l'invariant est vrai avant le passage dans une boucle. Si on note la propriété invariante P, on montre donc que P0 est vraie.

La conservation

Si l'invariant est vrai avant une itération de la boucle, il le reste avant l’itération suivante. Cela revient à montrer que si l'invariant est vrai avant l'itération k (Pk), il reste vrai avec un tour de boucle en plus avant l'itération k+1 (Pk+1) : Pk ➡ Pk+1

La terminaison

On exploite les deux phases précédentes pour montrer qu'une fois toutes les itérations effectuées, l'invariant reste vrai et que l'algorithme a bien répondu à son objectif en s'arrêtant lorsqu'il a traité toutes les données.

Preuve de correction du tri par sélection¶

Dans notre algorithme de tri par selection, l'invariant de boucle est "Le tableau a[0:i] est trié" :

INITIALISATION : La valeur avant de rentrer dans la boucle est i=0, donc le tableau a[0:0] contient un seul élément. Un tableau contenant un seul élément est forcément trié (trivial), notre invariant "le tableau a[0:i] est trié" est donc vrai.

CONSERVATION : si l'invariant de boucle est vrai avant une itération de la boucle : "Le tableau a[0:i] est trié", alors il le reste à la fin de l'itération : "Le tableau a[0:i+1] est trié". Le tableau a[0:i] est trié et tous ses éléments sont plus petits ou égaux que les éléments du tableau a[i+1:n-1], donc le plus petit élément de a[i+1:n -1] sera plus grand que chacun des éléments de a[0:i] et après ECHANGE cet élément sera a[i+1], donc le tableau a[0:i+1] sera évidemment trié.

TERMINAISON : La dernière valeur prise de i dans la boucle est i=n-1, donc le tableau a[0:n-1] sera trié.

Cette démonstration nous permet d'affirmer que l'algorithme de tri par selection est correct.

Preuve de correction du tri par insertion¶

Dans notre algorithme de tri par insertion, l'invariant de boucle est "Le tableau a[0:i-1] est trié" :

INITIALISATION : La valeur avant de rentrer dans la boucle est i=1, donc le tableau a[0:0] contient un seul élément. Un tableau contenant un seul élément est forcément trié (trivial), notre invariant "le tableau a[0:0] est trié" est donc vrai.

CONSERVATION : si l'invariant de boucle est vrai avant une itération de la boucle : "Le tableau a[0:i-1] est trié", alors il le reste à la fin de l'itération : "Le tableau a[0:i] est trié". Si on insère a[i] à sa place dans le tableau a[0:i-1], alors le tableau a[0:i] sera également trié.

TERMINAISON : La dernière valeur prise de i dans la boucle est i=n-1, donc le tableau a[0:n-1] sera trié. Cette démonstration nous permet d'affirmer que l'algorithme de tri par insertion est correct.