Problème du tri
Étude du problème du tri et implémentation de quelques algorithmes pour voir les différentes façon de trier et leurs complexités.
Les informaticiens adorent les algorithmes de tris. Pas parce qu'ils aiment l'ordre — loin de là — mais parce qu'il existe des millions de façons différentes de trier.
Les algorithmes de tri que nous verrons dans cette partie nous permettrons non seulement de mettre en oeuvre tout ce que nous avons vu sur les techniques de preuves et de calcul de complexités, mais également d'apprendre de nouveaux outils, comme le master theorem.
Commençons par définir le problème :
Problème
- Nom : tri
- Entrées : un tableau d'entiers
- Sortie : un tableau contenant les valeurs du tableau en entrée triées selon l'ordre croissant
Reconnaissance
Commençons par travailler sur un problème connexe au problème du tri, celui de savoir si un tableau d'entiers est trié ou non. Le problème du tri présuppose en effet que l'on sache ce qu'est un tableau trié et, en creux, qu'on puisse vérifier (rapidement) qu'un tableau est trié ou non.
Pouvoir vérifier qu'une solution à un problème en est vraiment une est un point crucial en algorithmie. Nous y reviendrons intensivement lorsque nous parlerons de classes de problèmes.
Algorithmes Tris simples
Deux Algorithmes simples pour trier un tableau.
Tri par sélection
Le plus simple des algorithmes de tri, pour s'échauffer.
Tri par insertion
Son implémentation va nécessiter d'utiliser une nouvelle technique, le placement de sentinelles, et démontrer ses complexités va demander un peu de travail car son nombre d'instructions est très variable selon le tableau donné en paramètre.
Exercices : variantes
La chaîne Youtube Polylog est très bien ! Son niveau moyen est pour l'instant au-dessus de ce que l'on connaît ou que l'on sait faire, mais on abordera petit à petit toutes les notions qu'ils abordent et à l'issue du cours vous serez à l'aise avec son contenu.
Vous allez voir quelques variantes surprenante de tris simple.
Commençons par un petit échauffement. Sélection est identique à l'algorithme ci-dessous :
algorithme sélection(T: [entier]) → ∅:
pour chaque i de [0, T.longueur[:
pour chaque j de [i + 1, T.longueur[:
si T[j] < T[i]:
T[i], T[j] ← T[j], T[i]Pourquoi ?
corrigé
corrigé
A chaque fois qu'un nombre T[j] strictement plus petit que T[i] est trouvé pour un $j > i$, on échange les deux valeurs. A la fin de l'itération le plus petit élément de T[i:] est placé en position T[i].
L'invariant de la boucle 2-5 est donc identique à celui de l'algorithme par sélection que nous avons prouvé pour le précédent algorithme.
Et maintenant un peu de magie :
algorithme sélection_opposé(T: [entier]) → ∅:
pour chaque i de [0, T.longueur[:
pour chaque j de [0, T.longueur[:
si T[j] < T[i]:
T[i], T[j] ← T[j], T[i]Il ressemble à un croisement improbable entre tri par sélection et tri par insertion.
Exécutez l'algorithme sur le tableau [1, 3, 2, 6, 4, 5]
corrigé
corrigé
On note le tableau chaque fin de boucle 2-5 :
- [1, 3, 2, 6, 4, 5]
- [3, 1, 2, 6, 4, 5]
- [3, 2, 1, 6, 4, 5]
- [6, 3, 2, 1, 4, 5]
- [6, 4, 3, 2, 1, 5]
- [6, 5, 4, 3, 2, 1]
Comme vous l'avez remarqué, l'algorithme suivant trie aussi, mais dans le sens opposé.
Pourquoi ?
corrigé
corrigé
La première boucle 2-5 (pour i=0) fait comme le tri par sélection : elle place le plus petit élément en tête de tableau.
A partir de la seconde boucle, on peut montrer que chaque boucle va trier les i+1 premiers éléments du tableau par ordre décroissant. Il se comporte comme le tri par insertion, adaptons son invariant de boucle à cet algorithme.
Par récurrence, on suppose vrai à la fin de l'itération $i$. Au début de l'itération $i+1$, les éléments de 0 à i sont triés par ordre décroissant avec le plus petit élément du tableau à la position $i$, lorsque j va progresser, il va commencer par placer $T[i+1]$ dans sa position dans le tableau (le plus petit indice i' tel que $T[i'] < T[i+1]$), puis placer l'indice échangé à sa nouvelle place et ainsi de suite jusqu'à placer le plus petit élément du tableau en position $i+1$.
Et terminons cette partie en montrant que cette dernière itération est bien un algorithme de tri :
algorithme sélection_opposé(T: [entier]) → ∅:
pour chaque i de [0, T.longueur[:
pour chaque j de [0, T.longueur[:
si T[i] < T[j]:
T[i], T[j] ← T[j], T[i]Pourquoi ?
corrigé
corrigé
C'est exactement la même preuve que précédemment en remarquant qu'à la fin de la première boucle 2-5 (pour i=0) l'algorithme place le plus grand élément en tête de tableau.
A partir de la seconde boucle, chaque boucle va trier les i+1 premiers éléments du tableau par ordre croissant.
Complexité du problème du tri
Algorithmes de tris optimaux
Tri fusion
Le tri fusion utilise une technique de création d'algorithme classique nommée diviser pour régner et nous utiliserons le très utile master Theorem pour en calculer la complexité.
Tri de python
L'algorithme timsort est l'algorithme utilisé par python pour trier des listes :
T = [1, 3, 2, 6, 4, 5]
T.sort()
print(T)Ce tri est in place et est un mix entre le tri fusion et le tri par insertion. C'est un tri très efficace puisque :
Complexités du timsort
Pour un tableau de taille $n$, l'algorithme timsort a :
- une complexité de $\mathcal{O}(n\ln(n))$
- une complexité min de $\mathcal{O}(n)$ pour les tableaux (presque) trié
- une complexité en moyenne de $\mathcal{O}(n\ln(n))$
Ne perdez donc pas de temps à recoder un algorithme de tri : utilisez celui de python !
Cas du tri rapide
Le tri rapide est, malgré sa simplicité apparente, le plus difficile à implémenter proprement et pour en calculer la complexité. Il vous apprendra à avoir une intuition de la complexité d'un algorithme.
Implémentations
Projet de développement pour voir les tris se trier.