Introduction et terminologies des algorithmes de tri

Un algorithme de tri est utilisé pour réorganiser les éléments d’un tableau ou une liste donnée selon un ordre (Croissant, décroissant) en utilisant l'un des opérateurs de comparaison (<,>).

Exemple :

Un algorithme de tri sur place utilise un espace supplémentaire constant pour produire la sortie (modifie le tableau donné uniquement). Il trie la liste uniquement en modifiant l'ordre des éléments dans la liste d'origine.

Lorsque nous exécutons un programme, nous demandons au processeur d'exécuter les instructions, de sorte que les instructions et les données utilisées doivent être placées dans la mémoire principale. Donc le tri interne et externe est basé sur cette idée

•   Lorsque toutes les données qui doivent être triées ne peuvent pas être placées en mémoire à la fois, le tri est appelé tri externe. Le tri externe est utilisé pour une énorme quantité de données.
•   Lorsque toutes les données sont placées en mémoire, le tri est appelé tri interne.

La stabilité est principalement importante lorsque nous avons des paires clé-valeur avec des clés en double possibles (comme les noms de personnes en tant que clés et leurs détails en tant que valeurs). Et nous souhaitons trier ces objets par clés.

Un algorithme de tri est dit stable si deux objets avec des clés égales apparaissent dans le même ordre en sortie triée comme ils apparaissent dans le tableau d'entrée à trier.

Nous soucions-nous des tableaux simples comme un tableau d’entiers ?

Lorsque des éléments égaux sont indiscernables, comme avec des entiers, ou plus généralement, toutes les données où l'élément entier est la clé, la stabilité n'est pas un problème. La stabilité n'est pas non plus un problème si toutes les clés sont différentes.

Pouvons-nous rendre stable n'importe quel algorithme de tri?

Tout algorithme de tri donné qui n'est pas stable peut être modifié pour être stable. Il peut y avoir des moyens spécifiques à l'algorithme de tri pour le rendre stable, mais en général, tout algorithme de tri basé sur la comparaison qui n'est pas stable par nature peut être modifié pour être stable en changeant l'opération de comparaison de clés de sorte que la comparaison de deux clés tienne compte de la position comme facteur pour des objets avec des clés égales.