Problème du tri
Parties bases et développer du cours de développement.
É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
- données : un tableau d'entiers
- réponse : 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.
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)$
- 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.