Tris¶

Dans ce chapitre, nous nous intéressons à différentes manières d’implémenter le même algorithme, dont l’objectif est de trier un tableau :

def tri(a: [float]):
    """
    :e/s a: tableau de float
    :post-cond:
       - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;len(a)[,  aₛ[j] = aₑ[i]
         (les éléments de a ont simplent changé d'ordre)
       - ∀ i ∈ [1;len(a)[,  aₛ[i] ≥ aₛ[i-1]
         (les éléments de a sont triés par valeur croissante)
    """

Tri par sélection¶

Ce tri consiste à placer chaque élément du tableau à sa position définitive, du plus petit au plus grand :

on recherche le plus petit élément du tableau, et on l’échange avec le premier élément, puis
on recherche le plus petit élément entre le deuxième et le dernier, et on l’échange avec le deuxième élément, puis
on recherche le plus petit élément entre la troisième et la dernier, et on l’échange avec le troisième élément,
etc.

Pour cela, on pourra utiliser la fonction indice_min, lui passant à chaque étape le sous-tableau approprié. Attention cependant à interpréter correctement la valeur de retour de cette fonction : c’est un indice du sous-tableau. Par exemple, si indice_min(a[3:]) retourne la valeur 5, c’est que la valeur recherchée est a[8] (8 = 3 + 5).

Complexité

Combien d’étapes de calcul sont elles nécessaires

dans le pire des cas ?
lorsque le tableau est déjà trié ?
lorsque le tableau est trié dans l’ordre décroissant ?

Voir aussi

Avertissement

L’algorithme mis en œuvre dans la deuxième vidéo ci-dessus n’est pas exactement le même que celui décrit ci-dessus : lors de la recherche du minimum, certains éléments sont déplacés dans le tableau… Mais le principe général reste le même.

Tri par insertion¶

Ce tri consiste à insérer successivement chaque valeur du tableau dans un sous-tableau déjà trié :

au départ, le sous-tableau trié est constitué uniquement du premier élément du tableau ;
on insère alors le deuxième élément, c’est à dire que
- s’il est plus grand que le premier, on ne change rien,
- s’il est plus petit que le premier, on intervertit leurs positions,
et ainsi, le sous-tableau constitué des deux premiers éléments est désormais trié ;
à chaque étape, on augmente d’un élément le sous-tableau déjà trié en décalant vers la gauche l’élément suivant jusqu’à sa position correcte dans le sous-tableau déjà trié ;
lorsqu’on a répété cette étape jusqu’au dernier élément du tableau, celui-ci est intégralement trié.

Pour cela, on aura besoin d’une procédure intermédiaire qui, étant donné un tableau partiellement trié, décale le premier élément non-trié pour l’insérer à sa position correcte dans le sous-tableau déjà trié :

def insere_element(a: [float], i: int):
    """
    :e/s a: tableau de float
    :entrée i: int
    :pré-cond:
       - 1 ≤ i < len(a)
       - ∀ j ∈ [1;i[,  a[j] ≥ a[j-1]  (a est trié entre 0 et i-1)
    :post-cond:
       - ∀ j ∈ [0;i+1[, ∃ k ∈ [0;i+1[,  aₛ[k] = aₑ[j]
         (les éléments entre 0 et i+1 ont simplement changé d'ordre)
       - ∀ j ∈ [i+1;len(a)[,  aₛ[j] = aₑ[j]
         (les éléments au delà de i n'ont pas été modifiés)
       - ∀ j ∈ [1;i+1[,  a[j] ≥ a[j-1]
         (a est trié entre 0 et i)
    """

Complexité

Combien d’étapes de calcul sont elles nécessaires

dans le pire des cas ?
lorsque le tableau est déjà trié ?
lorsque le tableau est trié dans l’ordre décroissant ?

Voir aussi

Tri binaire¶

Également appelé tri rapide (quicksort), ce tri utilise le principe de la dichotomie. Il consiste à choisir une valeur pivot dans le tableau, puis à permuter les éléments de sorte que toutes les valeurs plus petites que le pivot soient à sa gauche, et que toutes les valeurs plus grandes que le pivot soient à sa droite. On trie ensuite récursivement les deux sous-tableaux à gauche et à droite du pivot.

Notons que le choix du pivot n’a pas d’influence sur le résultat de l’algorithme (même s’il peut en avoir sur ses performances). Aussi par souci de simplicité, on prendra comme pivot le premier élément du tableau.

Afin de pouvoir trier récursivement des sous-tableaux, on utilisera les notations a[:i] et a[i:].

Il sera également utile de définir la procédure partitionne qui choisit un pivot dans un sous-tableau donné, permute les valeurs comme indiqué ci-dessus et retourne l’indice du pivot dans le sous-tableau ainsi permuté :

def partitionne(a: [float]) -> int:
    """
    :e/s a: tableau de float
    :sortie ip: int
    :post-cond:
       - 0 ≤ ip < len(a)
       - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;len(a)[,  aₛ[j] = aₑ[i]
         (les éléments de a ont simplement changé d'ordre)
       - ∀ i ∈ [0;ip], aₛ[i] ≤ aₛ[ip]
         (les éléments à gauche du pivot lui sont inférieurs ou égaux)
       - ∀ i ∈ ]ip;len(a)[, aₛ[i] > aₛ[ip]
         (les éléments à droite du pivot lui sont supérieurs)
    """

Voir aussi

http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.htmlm

Tri selon d’autres fonctions de comparaison¶

Les algorithmes de tris ci-dessus ne se limitent pas aux nombres flottants. On peut bien sûr les appliquer à l’identique sur n’importe quel type de données supportant les opérateurs de comparaison (==, <, >, etc.) comme int ou str.

Mais on peut appliquer ces algorithmes à d’autres types de comparaison ; par exemple, on pourrait souhaiter trier un tableau de chaînes de caractères selon la longueur de ces chaînes (et non selon leur ordre « naturel » induit par les opérateur < et >). Le principe des algorithmes ne change pas, ce n’est que la manière de comparer les éléments des tableaux qui change.

Appliquez l’un des algorithmes ci-dessus pour écrire les algorithmes suivant :

def tri_dec(a: [float]):
    """
    :e/s a: tableau de float
    :post-cond:
       - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;len(a)[,  aₛ[j] = aₑ[i]
         (les éléments de a ont simplent changé d'ordre)
       - ∀ i ∈ [1;len(a)[,  aₛ[i] ≤ aₛ[i-1]
         (les éléments de a sont triés par valeur décroissante)
    """

def tri_par_longueur_croissante(a: [str]):
    """
    :e/s a: tableau de str
    :post-cond:
       - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;len(a)[,  aₛ[j] = aₑ[i]
         (les éléments de a ont simplent changé d'ordre)
       - ∀ i ∈ [1;len(a)[,  len(aₛ[i]) ≥ len(aₛ[i-1])
         (les éléments de a sont tries par longueur croissante)
    """

Tri indirect¶

Dans certaines situations, on souhaite pouvoir accéder aux données d’un tableau dans l’ordre (d’où la nécessité d’un tri), mais sans vouloir modifier directement le tableau. Par exemple, les données peuvent être volumineuse, et leur déplacement coûteux en temps. Ou encore, il peut exister plusieurs ordres pertinents pour les données du tableau (par exemple, on peut souhaiter accéder à un tableau de chaînes par longueur croissante, par longueur décroissante, ou dans l’ordre lexicographique).

Dans ces situations, on utilisera un tri indirect : le tableau de données \(ad\) n’est pas modifié, mais on crée un tableau d’entier \(ai\) ayant la même taille, et contenant tous les indices de \(ad\), de sorte que :

\(∀ i ∈ [1;len(ad)[, ~~ ad[ai[i-1]] ≤ ad[ai[i]]\)

En d’autres termes, chaque élément de \(ai\) représente un élément de \(ad\), et les éléments de \(ai\) sont triés dans l’ordre des éléments qu’ils représentent. On peut bien sûr effectuer ce tri indirect avec n’importe lequel des algorithmes vu ci-dessus pour le tri, moyennant une adaptation (pour comparer les \(ad[ai[i]]\) et non les \(a[i]\)).

def tri_indirect(ad: []) -> [int]:
    """
    :entrée ad: tableau
    :sortie ai: tableau d'entiers
    :post-cond:
       - len(ai) = len(ad)
       - ∀ i ∈ [0;len(ad)[, ∃ j ∈ [0;len(ai)[,  ai[j] = i
         (ai contient tous les indices de ad)
       - ∀ i ∈ [1;len(ad)[,  ad[ai[i-1]] ≤ ad[ai[i]]
         (les éléments de ai sont triés
          dans l'ordre des éléments de ad qu'ils représentent)
    """