Les algorithmes de tri entre la théorie et la pratique

On se propose de présenter un document synthétique sur les algorithmes de tris en présentant leurs principes, leurs complexités, et certaines pistes d'optimisation et puis de les comparer suivant différents critères.

Les tris quadratiques appartenant à cette classe d'algorithmes s'exécutent en O(n²), et ne sont donc pas efficaces (en général) pour des grandes données.
Nous présenterons ici le tri bulles avec 3 variantes :
- Le tri bulles classique
Il s'agit de parcourir le tableau et de comparer deux à deux chaque élément voisin et de les permuter s'ils ne sont pas dans le même ordre et de réitérer ce processus. Le nombre de comparaisons est de l'ordre de n(n-1)/2. Le nombre d'échanges dépendra de la distribution des valeurs et aura comme meilleure valeur 0 si les données sont déjà triées
- Première variante : ajout d'une variable booléenne
On rajoute une variable booléenne qui nous permettra d'arrêter le processus quand on trouve que les données ont été triées et ceci nous évitera de faire des opérations pour rien
- Deuxième variante : ajout d'une deuxième variable booléenne
Ici, on ne va pas utiliser une boucle for pour parcourir le tableau mais plutôt une boucle while qui s'arrêtera quand le tableau sera trié
- Troisième variante : on change la variable du parcours
Pour cette optimisation, on change la variable du parcours pour qu'elle prenne l'indice du dernier emplacement où un échange est survenu.