Le tri est une opération de base dans laquelle les éléments d'un tableau sont disposés dans un ordre spécifique afin d'améliorer sa capacité de recherche. En termes simples, les données sont triées pour faciliter les recherches.
Tableau de comparaison
| Base de comparaison | Tri par insertion | Tri de sélection |
|---|---|---|
| De base | Les données sont triées en les insérant dans un fichier trié existant. | Les données sont triées en sélectionnant et en plaçant les éléments consécutifs dans un emplacement trié. |
| La nature | Stable | Instable |
| Processus à suivre | Les éléments sont connus à l’avance tandis que l’emplacement pour les placer est recherché. | L'emplacement est précédemment connu pendant la recherche des éléments. |
| Données immédiates | Le tri par insertion est une technique de tri en direct pouvant traiter des données immédiates. | Il ne peut pas traiter les données immédiates, il doit être présent au début. |
| Meilleure complexité de l'affaire | Sur) | O (n 2 ) |
Définition du tri par insertion
Le tri par insertion consiste à insérer l'ensemble de valeurs dans le fichier trié existant. Il construit le tableau trié en insérant un seul élément à la fois. Ce processus se poursuit jusqu'à ce que tout le tableau soit trié dans un ordre quelconque. Le principe de base du tri par insertion consiste à insérer chaque élément à son emplacement approprié dans la liste finale. La méthode de tri par insertion enregistre une quantité efficace de mémoire.
Fonctionnement du tri par insertion
- Il utilise deux ensembles de tableaux où l’un stocke les données triées et l’autre sur des données non triées.
- L'algorithme de tri fonctionne jusqu'à ce qu'il y ait des éléments dans l'ensemble non trié.
- Supposons qu'il y a 'n' éléments numériques dans le tableau. Initialement, l'élément d'indice 0 (LB = 0) existe dans le jeu trié. Les éléments restants sont dans la partition non triée de la liste.
- Le premier élément de la partie non triée a l'index de tableau 1 (Si LB = 0).
- Après chaque itération, il choisit le premier élément de la partition non triée et l'insère à l'emplacement approprié dans l'ensemble trié.
Avantages du tri par insertion
- Facilement implémenté et très efficace lorsqu'il est utilisé avec de petits ensembles de données.
- L'espace mémoire supplémentaire requis pour le tri par insertion est inférieur (c'est-à-dire, O (1)).
- Il s'agit d'une technique de tri en direct, car la liste peut être triée à mesure que les nouveaux éléments sont reçus.
- Il est plus rapide que les autres algorithmes de tri.
Exemple :
Définition du tri par sélection
Le tri Sélection effectue le tri en recherchant le numéro de valeur minimale et en le plaçant à la première ou à la dernière position en fonction de l'ordre (croissant ou décroissant). Le processus de recherche de la clé minimale et de son positionnement correct est poursuivi jusqu'à ce que tous les éléments soient correctement placés.
Fonctionnement du tri de sélection
- Supposons un tableau ARR avec N éléments dans la mémoire.
- Dans la première passe, la plus petite clé est recherchée avec sa position, puis l'ARR [POS] est échangé avec ARR [0]. Par conséquent, ARR [0] est trié.
- Lors du second passage, la position de la plus petite valeur est à nouveau déterminée dans le sous-tableau de N-1 éléments. Échangez l'ARR [POS] avec l'ARR [1].
- Dans la passe N-1, le même processus est effectué pour trier le nombre N d'éléments.
Exemple :
Principales différences entre le tri par insertion et le tri par sélection
- Le tri par insertion effectue généralement l'opération d'insertion. Au contraire, le tri de sélection effectue la sélection et le positionnement des éléments requis.
- Le tri par insertion est dit stable, alors que le tri par sélection n'est pas un algorithme stable.
- En algorithme de tri par insertion, les éléments sont connus auparavant. En revanche, le tri par sélection contient l’emplacement au préalable.
- Le tri par insertion est une technique de tri en direct dans laquelle les éléments entrants sont immédiatement triés dans la liste, tandis que le tri par sélection ne peut pas fonctionner correctement avec des données immédiates.
- Le tri par insertion a le temps d'exécution O (n) dans le meilleur des cas. Par contre, la complexité optimale du tri par sélection lors de l'exécution du cas est O (n2).
Complexité du tri par insertion
La complexité de cas optimale du tri par insertion est O (n) fois, c'est-à-dire lorsque le tableau est précédemment trié. De la même manière, lorsque le tableau est trié dans l'ordre inverse, le premier élément du tableau non trié doit être comparé à chaque élément de l'ensemble trié. Ainsi, dans le pire des cas, la durée d'exécution du type Insertion est quadratique, c'est-à-dire O (n2) . En moyenne, il doit également effectuer les comparaisons minimum (k-1) / 2. Par conséquent, le cas moyen a également un temps d'exécution quadratique O (n2).
Complexité du tri de sélection
En tant que travail de sélection, le tri ne dépend pas de l'ordre d'origine des éléments dans le tableau. Il n'y a donc pas beaucoup de différence entre la complexité du meilleur des cas et celle du pire des cas.
Le tri par sélection sélectionne l'élément de valeur minimale. Dans le processus de sélection, tous les nombres "n" d'éléments sont analysés; par conséquent, n-1 comparaisons sont effectuées lors du premier passage. Ensuite, les éléments sont interchangés. De même, dans le second passage, pour rechercher le second élément le plus petit, nous devons analyser les n-1 éléments restants et poursuivre le processus jusqu’à ce que tout le tableau soit trié.
Ainsi, la complexité en temps d'exécution du tri par sélection est O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Conclusion
Parmi les deux algorithmes de tri, le tri par insertion est rapide, efficace et stable, tandis que le tri par sélection ne fonctionne efficacement que lorsque le petit ensemble d'éléments est impliqué ou que la liste est partiellement triée auparavant. Le nombre de comparaisons effectuées par type de sélection est supérieur aux mouvements effectués, tandis que dans le type par insertion, le nombre de fois qu'un élément est déplacé ou échangé est supérieur aux comparaisons effectuées.
