21. Algorithmes de tri
Page 78 | Écouter en audio
L'un des sujets les plus cruciaux du cours complet de programmation logique pour débutants est l'étude des algorithmes de tri. Le tri est un problème classique et fondamental en informatique. Trier signifie organiser les éléments d’un ensemble dans un ordre spécifique. Dans le contexte de la programmation, le tri est le processus de réorganisation d'un ensemble de données (comme un tableau) soit par ordre croissant (du plus petit au plus grand), soit par ordre décroissant (du plus grand au plus petit).
Il existe plusieurs algorithmes de tri et chacun d'entre eux a ses particularités, ses avantages et ses inconvénients. Discutons de certains des algorithmes de tri les plus courants et les plus importants.
1. Tri à bulles
Le tri à bulles, ou Float Sort, est l'un des algorithmes de tri les plus simples. Cela fonctionne en répétant le processus de parcours de la liste à trier, en comparant chaque paire d'éléments adjacents et en les échangeant s'ils sont dans le mauvais ordre. Ce processus est répété jusqu'à ce que la liste soit triée.
2. Tri par sélection
Le tri par sélection est un autre algorithme de tri simple. Cela fonctionne en divisant la liste à trier en deux parties : la partie triée et la partie non triée. Initialement, la partie triée est vide et la partie non triée contient tous les éléments. L'algorithme fonctionne en trouvant l'élément le plus petit (ou le plus grand, selon l'ordre de tri) dans la partie non triée et en l'échangeant avec le premier élément non trié, déplaçant ainsi la limite entre les parties triées et non triées.
3. Tri par insertion
Le tri par insertion est un algorithme de tri qui fonctionne de la même manière que les gens trient les cartes à jouer qu'ils ont en main. L'algorithme divise la liste en une partie ordonnée et une partie non ordonnée. La partie triée commence par le premier élément de la liste. A chaque itération, l'algorithme supprime un élément de la partie non triée et l'insère au bon endroit dans la partie triée.
4. Fusionner le tri
Merge Sort est un algorithme de tri qui utilise l'approche diviser pour régner. Il divise la liste à trier en deux moitiés, trie les deux moitiés séparément, puis les fusionne pour obtenir la liste triée. Merge Sort est un algorithme stable et efficace avec une complexité temporelle de O(n log n).
5. Tri rapide
Quick Sort est un algorithme de tri qui utilise également l'approche diviser pour régner. Il sélectionne un élément appelé pivot et divise la liste autour du pivot de sorte que les éléments inférieurs au pivot vont à gauche du pivot et les éléments supérieurs au pivot vont à droite du pivot. Quick Sort trie ensuite les deux partitions de manière récursive. Le tri rapide est l'un des algorithmes de tri les plus rapides, avec une complexité temporelle moyenne de O(n log n).
Ce ne sont là que quelques-uns des nombreux algorithmes de tri qui existent. Chacun d’eux présente ses propres avantages et inconvénients et convient à différents types de problématiques de tri. Dans le cours complet de programmation logique pour débutants, vous en apprendrez davantage sur ces algorithmes de tri et sur d'autres, ainsi que sur quand et comment les utiliser efficacement.
Répondez maintenant à l’exercice sur le contenu :
Lequel des algorithmes de tri suivants fonctionne en divisant la liste à trier en deux parties : la partie triée et la partie non triée, où initialement la partie triée est vide et la partie non triée contient tous les éléments ?
Tu as raison! Félicitations, passez maintenant à la page suivante
Vous avez raté! Essayer à nouveau.
Page suivante de lebook gratuit :
79Algorithmes de recherche
3 minutes
Obtenez votre certificat pour ce cours gratuitement ! en téléchargeant lapplication Cursa et en lisant lebook qui sy trouve. Disponible sur Google Play ou App Store !
