Introduction

Les algorithmes de tri sont des méthodes pour organiser les éléments d'une liste, d'un tableau, ou d'une structure de données dans un certain ordre, généralement croissant ou décroissant. Ils sont fondamentaux en informatique, car de nombreux programmes ont besoin de trier des données pour des recherches, des analyses, ou des affichages efficaces. Les principaux objectifs des algorithmes de tri sont l'efficacité (rapidité), la stabilité (conservation de l'ordre relatif des éléments), et la simplicité (facilité de mise en oeuvre).

Types principaux d'algorithmes de tri

Voici les principaux types d'algorithmes de tri :

• Tri à bulles (Bubble Sort) : Simple, il compare chaque paire d'éléments adjacents et les échange s'ils sont dans le mauvais ordre. Ce processus est répété jusqu'à ce que la liste soit triée. Il est peu efficace pour les grandes listes.
• Tri par insertion (Insertion Sort) : Parcourt la liste et insère chaque élément dans sa position correcte en décalant les éléments plus grands. Il est efficace pour les petites listes ou les listes presque triées.
• Tri par sélection (Selection Sort) : Trouve le plus petit élément et le place en première position, puis répète l'opération pour les éléments restants. Il est simple mais peu performant sur les grandes listes.
• Tri Shell-Metzner (Shell Sort) : Une généralisation du tri par insertion, cet algorithme améliore l'efficacité en effectuant des comparaisons entre des éléments éloignés, avant de les rapprocher progressivement. La complexité de cet algorithme dépend de l'intervalle choisi, et il peut être bien plus rapide que le tri par insertion, mais reste plus lent que QuickSort ou MergeSort dans de nombreux cas.
• Tri rapide (Quick Sort) : Un des plus efficaces, il divise la liste en sous-listes (partitionnement) autour d'un pivot, puis trie les sous-listes de manière récursive. Sa complexité est généralement de O(n log n).
• Tri par fusion (Merge Sort) : Divise la liste en sous-listes jusqu'à avoir des listes de taille 1, puis fusionne les listes triées. Il est stable et fonctionne en O(n log n), mais nécessite de l'espace supplémentaire.
• Tri par tas (Heap Sort) : Utilise une structure de données de type tas (heap) pour organiser les éléments et extraire le plus grand (ou le plus petit) à chaque étape. Sa complexité est O(n log n) et il ne nécessite pas d'espace additionnel.
• Tri Radix (Radix Sort) : Un algorithme de tri non comparatif triant les éléments en fonction de leurs chiffres ou bits individuels. Il est particulièrement efficace pour trier des entiers ou des chaînes de caractères et peut être plus rapide que les algorithmes de tri classiques dans certains cas.
• Tri par comptage (Counting Sort) : Adapté aux entiers dans un intervalle limité, il compte les occurrences de chaque valeur et les réorganise. Il fonctionne en O(n + k), où k est l'intervalle des valeurs.
• Tri Bucket (Bucket Sort) : Cette méthode trie les éléments en les répartissant dans un certain nombre de "seaux" (buckets), puis trie chaque seau individuellement. Elle est souvent utilisée pour des données qui sont uniformément distribuées et peut avoir une complexité de O(n) dans de tels cas.

Critères d'évaluation des algorithmes de tri

Voici les principaux critères d'évaluation des algorithmes de tri :

• Complexité temporelle : Mesure le temps d'exécution en fonction de la taille de la liste.
• Complexité spatiale : Quantité de mémoire supplémentaire requise.
• Stabilité : Capacité à maintenir l'ordre relatif des éléments de valeur égale.

Utilisation des algorithmes de tri

Les algorithmes de tri sont utilisés dans diverses applications, comme le tri des bases de données, le traitement des images, le tri des fichiers pour les systèmes de fichiers, ou l'organisation des informations pour des opérations de recherche optimisées.

Chaque algorithme a ses avantages et inconvénients selon les caractéristiques des données et les exigences de performance.

Les algorithmes de tri

Les algorithmes de tri permettent de mettre en ordre alphabétique ou numérique différents éléments contenu dans un tableau. Voici différents algorithmes en lien avec le tri, comme par exemple : tri à bulles, tri de shell, tri par échange, tri par extraction, tri par insertion, tri sélection, tri QuickSort,...

Tri à bulles

Le tri à bulles (ou tri par bulles en français, ou encore bubble sort en anglais) est un algorithme de tri simple organisant une liste en comparant successivement des paires d'éléments adjacents et en les échangeant si nécessaire. Le processus répète ce balayage jusqu'à ce que la liste soit entièrement triée.

Principe de fonctionnement

• Comparaison et échange : L'algorithme parcourt la liste d'éléments en comparant chaque paire adjacente. Si un élément est plus grand que le suivant, ils sont échangés pour les remettre dans l'ordre.
• Répétition : Ce balayage est répété autant de fois que nécessaire, chaque passage amenant le plus grand élément restant non trié vers la fin de la liste. Cela ressemble à des « bulles » qui montent progressivement vers la fin de la liste.
• Optimisation éventuelle : L'algorithme peut être légèrement optimisé en ajoutant un indicateur qui arrête le processus dès qu'un passage complet n'a pas nécessité d'échange (ce qui signifie que la liste est déjà triée).

Complexité et limites

• Complexité temporelle : La complexité de l'algorithme de tri à bulles est O(n²) dans le pire et le cas moyen, ce qui le rend peu efficace pour les grandes listes.
• Utilisation : En raison de sa simplicité, il est principalement utilisé pour les démonstrations pédagogiques ou dans des cas très simples où les données sont presque triées.

Algorithme

L'idée derrière cette technique est très simple, parcourir le tableau et permuter deux éléments lorsque cela s'avère nécessaire. Voici son algorithme :

Tri de Shell-Metzner

Le tri de Shell-Metzner, ou plus simplement tri de Shell (du nom de son inventeur Donald Shell en 1959), est une amélioration du tri par insertion, conçue pour augmenter son efficacité sur les grandes listes. Il fonctionne en divisant la liste à trier en sous-séries d'éléments séparés par un certain écart (ou "gap"), diminuant progressivement. Au sein de chaque sous-série, les éléments sont triés localement. Au fur et à mesure que l'écart est réduit, les sous-séries se rapprochent, jusqu'à ce que l'écart atteigne 1, ce qui équivaut à un tri par insertion final sur la liste entière. Ce procédé permet de déplacer rapidement les éléments sur de longues distances, ce qui accélère la convergence vers une liste triée.

Principe du tri de Shell-Metzner

• Division en sous-séries : La liste est divisée en plusieurs sous-séries d'éléments en fonction d'un écart initial, généralement une fraction de la taille de la liste.
• Tri des sous-séries : Chaque sous-série est triée individuellement avec un tri par insertion.
• Réduction de l'écart : L'écart est progressivement réduit selon une séquence prédéfinie jusqu'à atteindre 1.
• Tri final : Lorsque l'écart est de 1, la liste est triée comme dans le tri par insertion, mais avec des éléments déjà partiellement ordonnés, rendant l'opération plus rapide.

Avantages et complexité

Le tri de Shell-Metzner est plus rapide que le tri par insertion traditionnel, notamment sur de grands ensembles de données, bien qu'il ait une complexité de temps variable en fonction de la séquence d'écarts choisie. Certaines séquences, comme celles de Hibbard ou de Sedgewick, améliorent son efficacité, réduisant la complexité temporelle dans le meilleur des cas à environ O(n^3/2) voire moins avec certaines optimisations.

Algorithme

La technique de tri nommée «Shell-Metzner», est en fait une technique de réduction du nombre de comparaison a effectuer pour trier un tableau. Comment si prend-on? C'est simple, la comparaison s'effectue entre 2 éléments séparer par un écart égal (au départ) à la moitié de la taille du tableau. Ensuite, la comparaison s'effectue entre des éléments séparées par un écart égal au nombre d'élément du tableau divisée par 4. Lorsque l'écart atteint finalement 1, la tri est terminer.

Tri par échange

La technique de tri par échange consiste a comparer un premier élément avec un autre et lorsqu'il trouve un élément plus petit, un échange est effectuer avec ce premier élément. De cette façon, on finira par placer cette élément correctement. Ensuite, on recommence avec le 2^ième élément jusqu'à la fin. En voici l'algorithme:

Tri par extraction

La tri par extraction est une consiste a tout d'abord trouver le plus élément d'un tableau et de l'échanger avec le premier indice de celui, soit habituellement l'indice 0. Par la suite, il poursuit ses recherches d'un élément minimum entre l'élément 1 à celle de la fin. Il effectuera se traitement jusqu'à terme. Voici donc l'algorithme:

Tri par insertion

La tri par insertion comme son nom l'indique consiste à prendre le premier élément en commençant par le deuxième et d'ensuite de l'insérer directement à la place approprié dans les indices situés entre 0 et I. Voici donc son algorithme:

Tri par sélection

La tri par sélection est une technique très intéressante, en effet, contrairement à la Tri à bulles ou par échanges, elle sélectionne systématiquement le plus petit élément et échange celui-ci avec le premier élément de la liste. Ensuite, il applique cette même manière de procéder avec le 2^ième élément jusqu'à la fin de la liste. En voici l'algorithme :

Tri par QuickSort

Le «QuickSort» est sans nulle doute la technique de tri la plus rapide. Le seul inconvénient de cette technique c'est qu'elle empile un grand nombre d'élément dans la pile, on ne pourra donc pas l'employer par exemple pour une base de données sollicitant des millions d'informations. Toutefois, elle pourra être utilise en graphisme par exemple. Voici l'algorithme de cette technique de tri: