ALGORITHMES DE TRI

Le tri est le processus consistant à organiser les éléments d'un tableau afin qu'ils puissent être placés par ordre croissant ou décroissant. Par exemple, considérons un tableau A = {A1, A2, A3, A4, ?? An }, le tableau est appelé dans l'ordre croissant si les éléments de A sont disposés comme A1 > A2 > A3 > A4 > A5 > ? > Un .

Considérons un tableau ;

int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 )

Le tableau trié par ordre croissant sera donné comme :

UNE[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }

Il existe de nombreuses techniques permettant d'effectuer un tri. Dans cette section du didacticiel, nous aborderons chaque méthode en détail.

Les algorithmes de tri sont décrits dans le tableau suivant avec la description.

SN	Algorithmes de tri	Description
1	Tri à bulles	Il s'agit de la méthode de tri la plus simple qui effectue un tri en déplaçant à plusieurs reprises le plus grand élément vers l'index le plus élevé du tableau. Il consiste à comparer chaque élément à son élément adjacent et à les remplacer en conséquence.
2	Tri par seau	Le tri par compartiment est également appelé tri par bac. Cela fonctionne en distribuant l'élément dans le tableau également appelé buckets. Dans ces algorithmes de tri, les buckets sont triés individuellement en utilisant différents algorithmes de tri.
3	Tri au peigne	Comb Sort est la forme avancée de Bubble Sort. Le tri à bulles compare toutes les valeurs adjacentes tandis que le tri en peigne supprime toutes les valeurs de tortue ou les petites valeurs vers la fin de la liste.
4	Tri par comptage	Il s'agit d'une technique de tri basée sur les clés, c'est-à-dire que les objets sont collectés selon des clés qui sont de petits nombres entiers. Le tri par comptage calcule le nombre d'occurrences d'objets et stocke ses valeurs clés. Un nouveau tableau est formé en ajoutant des éléments clés précédents et en les attribuant aux objets.
5	Tri en tas	Dans le tri par tas, le tas Min ou le tas max est conservé à partir des éléments du tableau en fonction du choix et les éléments sont triés en supprimant l'élément racine du tas.
6	Tri par insertion	Comme son nom l'indique, le tri par insertion insère chaque élément du tableau à sa place. C'est une méthode de tri très simple qui est utilisée pour organiser le jeu de cartes tout en jouant au bridge.
7	Tri par fusion	Le tri par fusion suit l'approche diviser pour régner dans laquelle la liste est d'abord divisée en ensembles d'éléments égaux, puis chaque moitié de la liste est triée à l'aide du tri par fusion. La liste triée est à nouveau combinée pour former un tableau trié élémentaire.
8	Tri rapide	Le tri rapide est l'algorithme de tri le plus optimisé qui effectue le tri dans des comparaisons O (n log n). Comme le tri par fusion, le tri rapide fonctionne également en utilisant l'approche diviser pour régner.
9	Trier la base	Dans le tri Radix, le tri est effectué comme nous trions les noms selon leur ordre alphabétique. Il s'agit de l'algorithme de tri lenear utilisé pour Inegers.
dix	Tri de sélection	Le tri par sélection trouve le plus petit élément du tableau et le place à la première place de la liste, puis il trouve le deuxième plus petit élément du tableau et le place à la deuxième place. Ce processus se poursuit jusqu'à ce que tous les éléments soient déplacés dans le bon ordre. Il comporte un temps d'exécution O(n2) qui est pire que le tri par insertion.
onze	Tri des coquilles	Le tri Shell est la généralisation du tri par insertion qui pallie les inconvénients du tri par insertion en comparant des éléments séparés par un espace de plusieurs positions.