Cours - Algorithmes de Tri⚓︎

1. Tri par sélection⚓︎

1.1 Spécification⚓︎

Définition Spécification du tri par sélection

Soit une fonction tri_selection(t) qui applique le tri par sélection (ordre croissant) à un tableau t :

Paramètre d’entrée : Un tableau t contenant n éléments comparables de même type.
Description : Le tri par sélection dans l’ordre croissant parcourt le tableau de gauche à droite. Le tableau est séparé en deux parties : les éléments déjà triés et à leur place définitive sont à gauche et la partie droite contient tous les autres éléments plus grands et non triés. À chaque itération on recherche le plus petit élément de la partie non triée pour l’échanger avec le premier élément non trié (d’index i), ainsi on étend par la droite la partie triée d’un élément.

Pour visualiser une trace d’exécution : https://professeurb.github.io/articles/tris/

1.2 Algorithme⚓︎

def tri_selection(t):
    n = len(t)
    #boucle externe
    for i in range(0, n):
        #invariant  : t[0:i] trié et t[O:i] <= t[i:n]
        #boucle interne de recherche de l'index du minimum dans t[i:n]
        imin = recherche_index_min(t, i) 
        #postcondition de boucle interne : t[imin] = min(t[i:n])
        #echange de t[i] et t[imin]
        echange(t, i, imin)

Ci-dessous la fonction tri_selection2(t) sans les fonctions auxiliaires recherche_index_min(t, i) et echange(t, a, b).

def tri_selection2(t):
    """
    Trie en place par sélection un tableau d'entiers
    Sans utiliser de fonctions externes

    Parameters : 
    t : tableau d'entiers

    Returns :  None.
    """
    n = len(t)
    #boucle externe
    for i in range(0, n):
        imin = i
        #boucle interne
        for j in range(i, n):
            if t[j] < t[imin]:
                imin = j
        t[i], t[imin] = t[imin], t[i]

Sortie : Le tri s’effectue en place c’est-à-dire que les éléments du tableau t sont déplacés à l’intérieur de la structure et le tri du tableau t le modifie par effet de bord. Ainsi la fonction ne renvoie rien, en fait None par défaut en Python.

1.3 Terminaison⚓︎

Les boucles for étant non bornées (et on ne touche ni aux indices ni à la taille des tableaux), la terminaison cet algorithme est évidente.

1.4 Correction⚓︎

Démontrer la correction de l'algorithme consiste à démontrer que l'algorithme retourne, quand il calcule en partant des données, un objet qui est un des résultats escomptés et qui satisfait la spécification du résultat comme énoncé dans la description de l'algorithme.

Considérons un tableau t de taille $n$.

Pour tout indice $i$ de la boucle externe de tri_selection(t) on considère la propriété $P(i)$ définie avant que le tour de boucle d’indice i s’exécute, par :

$P (i)$ := « t[0:i] trié et t[0:i] <= t[i:n] »

Montrons que la propriété est vraie avant l'exécutin de la boucle, montrons donc que $P (0)$ est vraie.

$P (0)$ := « t[0:0] trié et t[0:0] <= t[0:n] »

Cette propriété est évidemment vraie puisque la liste t[0:0] est vide donc triée.

Montrons que la propriété est conservée pour chaque itération de la boucle. Montrons donc que si $P (i)$ est vraie alors $P (i +1)$ est vraie.

Si $P (i)$ est vraie alors t[0:i] trié et t[0:i] <= t[i:n] or l'algorithme, à l'itération suivante, prend le plus petit élément de t[i:n] (où tous ces éléments sont supérieurs ou égaux à t[0:i]) et le met à la suite de t[0:i]. On peut alors affirmer que t[0:i+1] est trié et que t[0:i+1] <= t[i+1:n].

Une propriété conservée par chaque itération de boucle s’appelle un invariant.

On a démontré précédemment la terminaison de tri_selection(t) pour tout tableau d’entiers t. La propriété $P (i)$ est vraie avant le premier tour de boucle et c’est un invariant de boucle donc $P (n)$ est vraie lorsque la boucle se termine. Or:

$P (n)$ := « t[0:n] trié et t[0:n] <= t[n:n] »

Donc le tableau t est trié à la fin de l'algorithme. On démontre ainsi la correction de l’algorithme de tri par sélection.

1.5 Compléxité⚓︎

L’ordre de grandeur du coût d’exécution d’un algorithme en nombre d’opérations élémentaires par rapport à la taille $n$ de son entrée mesure sa complexité temporelle.

Or d'une part, on a remarqué qu'en doublant la taille de la liste à trier, on multipliait le temps d'exécution par 4.

Et d'autre part le nombre de comparaisons réalisées par l'algorithme est $(n-1) + (n-2) + (n-3) ... + 1$ où $n-1$ est le nombre de comparaison de la première boucle interne, $n-2$ la suivante et ainsi de suite. Or cette somme est égale à $\dfrac{n(n-1)}{2}$. Or en développant, le terme dominant (le plus important) est le terme en $n^2$. On parle de compléxité quadratique.

2. Tri par insertion⚓︎

2.1 Spécification⚓︎

Le tri par insertion est aussi appelé tri des joueurs de cartes

Définition Spécification du tri par insertion

Soit une fonction tri_insertion(t) qui applique le tri par insertion (ordre croissant) à un tableau t de taille $n$ :

Paramètre d’entrée : Un tableau t contenant n éléments comparables de même type.
Description : Le tri par insertion dans l’ordre croissant parcourt le tableau de gauche à droite en maintenant à gauche une partie triée et à droite une partie non triée mais à chaque itération, au lieu de rechercher le plus petit élément de la partie non triée, il prend son premier élément d’index i et l’insère à sa place dans la partie triée en décalant vers la droite les éléments plus grands. Ainsi la partie triée gagne un élément à chaque itération mais les éléments triés ne sont pas à leur place définitive comme dans le tri par sélection.

Pour visualiser une trace d’exécution : https://professeurb.github.io/articles/tris/

2.2 Algorithme⚓︎

def tri_insertion(t):
    n = len(t)
    #boucle externe
    for i in range(1, n):
        #invariant de boucle : t[0:i] trié
        #boucle interne d’insertion de t[i] à sa place dans t[0:i]
        insertion(t, i)

Ci-dessous la fonction tri_insertion2(t) sans la fonctions auxiliaires insertion(t, i).

def tri_insertion2(t):
    """
    Trie en place par insertion un tableau d'entiers

    Parameters : 
    t : tableau d'entiers

    Returns :  None.
    """
    n = len(t)
    #boucle externe
    for i in range(1, n):
        #invariant de boucle : t[0:i] trié
        #boucle interne d'insertion de t[i] à sa place dans t[0:i]
        val = t[i]
        j = i
        while t[j - 1] > val and j > 0:
            t[j] = t[j - 1]
            j = j - 1
        t[j] = val

Sortie : Le tri s’effectue en place comme pour le tri par sélection.

2.3 Terminaison⚓︎

L’algorithme se termine car il est constitué d’une boucle externe bornée qui fait varier l’index i de la partie non triée t[i:n] entre 1 et n−1 et d’une boucle interne while non bornée ayant un j comme variant de boucle.

2.4 Correction⚓︎

Au début de l’itération i de la boucle externe, la partie t[0:i] est triée dans l’ordre croissant et l’insertion de t[i] dans t[0:i] par la boucle interne maintient cet invariant, ce qui prouve la correction.

2.5 Compléxité⚓︎

On a remarqué que si le tableau était prélablement trié, l'algorithme réalisait seulement $n$ comparaisons. Mais que si le tableau était inversement trié, l'algorithme réalisait $\dfrac{n(n-1)}{2}$ comparaisons.

Par ailleur, de la même manière qu'avec le tri par sélection, on a remarqué qu'en doublant la taille de la liste à trier, on multipliait le temps d'exécution par 4.

Donc la compléxité de cet algorithme est de nouveau quadratique (dans le pire des cas).