Soit une liste L de n nombres. Le tri de cette liste se fera grâce à une série d'opération d'échange de ces n nombres. Finalement, l'algorithme de tri prendra fin lorsque la liste L ne contiendra que des valeurs rangées dans l'ordre croissant.
Dans ce premier cours, nous étudierons cinq algorithmes de tri.
Le tri à bulles
Lorsque l'ordinateur utilise le tri à bulles, il compare deux éléments côte-à-côte et les intervertis si besoin (bulles). Puis, il compare les deux éléments suivants, et ainsi de suite.
La bulle parcourt la liste autant de fois que nécessaire, jusqu'à ce qu'aucun élément ne soit à déplacer.
Néanmoins, l'efficacité de ce tri est mauvaise. La complexité du tri à bulles est effectivement grande.
Exemples - Animations:
Le tri par sélection du minimum
Le tri par sélection consiste en la recherche du minimum d'une liste. Cette valeur est ensuite placée en première position d'une nouvelle liste qui coprrespond à la liste triée. Puis, on cherche le minimum de la liste restante que l'on place en deuxième position de la liste triée, et ce jusqu'à ce que cette dernière soit pleine.
Le tri par fusion
Le principe du tri par fusion est de diviser en deux moitiés une liste à trier. Puis, l'ordinateur trie individuellement chacune des deux moitiés de listes. Enfin, il fusionne les deux moitiés obtenues pour reconstituer la liste triée.
Exemple:
Le tri par insertion
Avec le tri par insertion, on ajoute un nouvel élément en l'insérant à sa place dans une sous-liste préalablement triée.
Exemple - Animation:
Le tri rapide ou tri par pivot
Tout d'abord, nous définissons une valeur pivot. Ensuite, nous plaçons au début de la liste toutes les valeurs inférieures au pivot et à la fin, toutes les valeurs supérieures. Nous reproduisons cette opération dans chaque partie de la liste, en définissant de nouveaux pivots.
Il est possible de rendre cet algorithme plus rapide, en laissant le choix du pivot être aléatoire.
Exemple:
コメント