Les tris

Présentation du problème

Étant donnée une liste quelconque d'un type totalement ordonné (par exemple les nombres réels), faire une fonction qui :

• Approche fonctionnelle : renvoie une copie triée de cette liste
• Approche impérative (effets de bord) : modifie cette liste et la trie directement

Pour les tris en place (voir section ci-dessous), on s'interessera à cette deuxième approche (en gros, il n'y a pas de return).

Vocabulaire

Tris en place

Un tri est dit en place, s'il utilise exclusivement les méthodes suivantes sans utiliser de mémoire supplémentaire :

• len() : renvoie la longueur de la liste
• get(i) : renvoie le ième élément de la liste en commençant par 0
• swap(i, j) : remplace les éléments d'indices i et j
• move(i, j) : déplace l'élément d'indice i en j. Lors de cette procédure, certains éléments seront déplacés d'un cran vers la droite ou vers la gauche.

La complexité spatiale d'un tri en place doit être en $\mathcal{O}(n)$.

La complexité c'est quoi ?

Étant donnée une entrée de longueur $n$, la fonction effectue des opérations unitaires (unitaire signifie ici en $\mathcal{O}(1)$) $^{[1]}$. On note $o(\mathcal A, L)$ le nombre d'opéraions effectuées lorsque l'algorithme $\cal A$ est exécuté avec la liste L en entrée.

Le nombre d'opérations dans le pire des cas pour une taille fixée est :

Toute suite équivalente à $k\times o_p(\mathcal A, n)$ pour une constante $k$ quelconque est appelée complexité de $\cal A$ dans le pire des cas, ou plus simplement complexité de $\cal A$.

$[1]$ : C'est dommage d'utiliser la complexité pour définir ce qu'est la complexité, je le regrette. Disons qu'une "opération unitaire" c'est une opération qui s'execute d'un coup, et ne dépend de la taille d'aucun objet.

Les tris au programme

Tri par insertion

Principe :
On parcourt la liste de gauche à droite et on insère chaque élément à sa bonne position dans la partie déjà triée (voir invariant).

Complexité :

• Meilleur cas : O(n)
• Cas moyen : O(n²)
• Pire cas : O(n²)

En place ? Oui, le tri se fait directement dans le tableau initial.

Invariant : À l'étape $i$, les éléments de $1$ à $i$ sont triés.

Tri à bulles

Principe :
On parcourt plusieurs fois la liste en échangeant les éléments adjacents s’ils sont dans le mauvais ordre. Les plus grands éléments « remontent » progressivement vers la fin.

Complexité :

• Meilleur cas : O(n) (avec optimisation)
• Cas moyen : O(n²)
• Pire cas : O(n²)

En place ?
Oui, les échanges se font directement dans le tableau.

Invariant :
À l'étape $i$, les $i$ derniers éléments sont :

• triés
• les $i$ plus grands éléments de la liste

Tri pivot (ou tri rapide)

Principe :
Si la liste est de longueur 1 : ne rien faire. Sinon, on choisit un pivot, puis on partitionne la liste en deux sous-listes :

• les éléments plus petits que le pivot
• les éléments plus grands que le pivot
  On applique récursivement le tri aux sous-listes.

Complexité :

• Meilleur cas : O(n log n)
• Cas moyen : O(n log n)
• Pire cas : O(n²) (imagine que le pivot est l'élément le plus petit à chaque fois)

En place ?
Oui (dans sa version classique en mémoire).

Correction :
Si les deux sous-listes sont triées alors à la fin de l'algo, la liste est triée.

Tri fusion

Principe :
Si la liste est de longueur 1 : ne rien faire.
Sinon, appliquer récursivement le tri aux deux sous-listes puis les fusionner afin d'obtenir une grande liste triée.

Complexité :

• Meilleur cas : O(n log n)
• Cas moyen : O(n log n)
• Pire cas : O(n log n)

En place ?
Oui, mais c'est pas évident (dans le fichier python ci-dessous un code pour le tri fusion en place est proposé)

Correction :
Si les deux sous-listes sont triées alors à la fin de l'algo, la liste est triée.

Tri par comptage

Principe :
On compte le nombre d’occurrences de chaque valeur dans un tableau de comptage, puis on reconstruit la liste triée à partir de ces comptes.

Complexité :

• $\matcal O(n\times m)$ (n = nombre d’éléments, m = nombre de valeurs possibles)

En place ?
Non, par principe

Correction :
Le tableau reconstruit à partir des comptes ordonnés est nécessairement trié.

Exemple

Le code suivant permet de visualiser des tris en place grâce aux méthodes len, get, swap et move définies plus haut.

Le code python (certaines fonctions sont à compléter)