Il existe plusieurs algorithmes de base pour résoudre le problème du tri d'un tableau. L'un des plus célèbres d'entre eux est le tri par insertion. En raison de sa clarté et de sa simplicité, mais de sa faible efficacité, cette méthode est principalement utilisée dans l'enseignement de la programmation. Il vous permet de comprendre les mécanismes de tri de base.
Description de l'algorithme
L'essence de l'algorithme de tri par insertion est qu'un segment correctement ordonné est formé à l'intérieur du tableau initial. Chaque élément est comparé un par un avec la partie cochée et inséré au bon endroit. Ainsi, après avoir parcouru tous les éléments, ils s'alignent dans le bon ordre.
L'ordre de sélection des éléments peut être quelconque, ils peuvent être sélectionnés arbitrairement ou selon un algorithme. Le plus souvent, l'énumération séquentielle est utilisée à partir du début du tableau, où un segment ordonné est formé.
Le début du tri pourrait ressembler à ceci:
- Prenez le premier élément du tableau.
- Puisqu'il n'y a rien à comparer, prenez l'élément lui-même comme ordonnéséquence.
- Passez au deuxième élément.
- Comparez-le avec le premier basé sur la règle de tri.
- Si nécessaire, permutez les éléments par endroits.
- Prenez les deux premiers éléments comme une séquence ordonnée.
- Passez au troisième élément.
- Comparez-le avec le second, échangez si nécessaire.
- Si le remplacement est effectué, comparez-le avec le premier.
- Prenez trois éléments comme une séquence ordonnée.
Et ainsi de suite jusqu'à la fin du tableau d'origine.
Tri d'insertion dans la vraie vie
Pour plus de clarté, il convient de donner un exemple de la façon dont ce mécanisme de tri est utilisé dans la vie quotidienne.
Prenez, par exemple, un portefeuille. Des billets de cent, cinq cents et mille dollars gisent en désordre dans le compartiment à billets. C'est un gâchis, dans un tel méli-mélo, il est difficile de trouver immédiatement le bon morceau de papier. Le tableau de billets doit être trié.
Le tout premier est un billet de 1000 roubles, et immédiatement après - 100. Nous en prenons cent et le plaçons devant. Le troisième d'affilée est de 500 roubles, la place qui lui revient se situe entre cent et mille.
De la même manière que nous trions les cartes reçues lors de la lecture du "Fool" pour faciliter leur navigation.
Opérateurs et fonctions d'assistance
La méthode de tri par insertion prend en entrée un tableau initial à trier, une fonction de comparaison et, si nécessaire, une fonction qui détermine la règle d'énumération des éléments. Le plus souvent utilisé à la placeinstruction de boucle régulière.
Le premier élément est lui-même un ensemble ordonné, donc la comparaison commence à partir du second.
L'algorithme utilise souvent une fonction d'assistance pour échanger deux valeurs (swap). Il utilise une variable temporaire supplémentaire, qui consomme de la mémoire et ralentit un peu le code.
Une alternative consiste à déplacer en masse un groupe d'éléments, puis à insérer l'élément actuel dans l'espace libre. Dans ce cas, la transition vers l'élément suivant se produit lorsque la comparaison a donné un résultat positif, ce qui indique l'ordre correct.
Exemples d'implémentation
L'implémentation spécifique dépend largement du langage de programmation utilisé, de sa syntaxe et de ses structures.
Implémentation C classique utilisant une variable temporaire pour échanger des valeurs:
int je, j, temp; for (i=1; i =0; j--) { if (array[j] < temp) break; tableau[j + 1]=tableau[j]; tableau[j]=temp; } }
Implémentation PHP:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Ici, d'abord, tous les éléments qui ne correspondent pas à la condition de tri sont décalés vers la droite, puis l'élément courant est inséré dans l'espace libre.
Code Java utilisant la boucle while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
La signification générale du code reste inchangée: chaque élément du tableau est séquentiellement comparé aux précédents et permuté avec eux si nécessaire.
Temps de fonctionnement estimé
Évidemment, dans le meilleur des cas, l'entrée de l'algorithme sera un tableau déjà ordonné dans le bon sens. Dans cette situation, l'algorithme devra simplement vérifier chaque élément pour s'assurer qu'il est au bon endroit sans faire d'échanges. Ainsi, le temps d'exécution dépendra directement de la longueur du tableau d'origine O(n).
L'entrée dans le pire des cas est un tableau trié dans l'ordre inverse. Cela nécessitera un grand nombre de permutations, la fonction d'exécution dépendra du nombre d'éléments au carré.
Le nombre exact de permutations pour un tableau complètement non ordonné peut être calculé à l'aide de la formule:
n(n-1)/2
où n est la longueur du tableau d'origine. Ainsi, il faudrait 4950 permutations pour ranger 100 éléments dans le bon ordre.
La méthode d'insertion est très efficace pour trier des tableaux petits ou partiellement triés. Cependant, il n'est pas recommandé de l'appliquer partout en raison de la grande complexité des calculs.
L'algorithme est utilisé comme auxiliaire dans de nombreuses autres méthodes de tri plus complexes.
Trier les valeurs égales
L'algorithme d'insertion appartient aux sortes dites stables. Ça veut dire,qu'il n'échange pas les éléments identiques, mais préserve leur ordre d'origine. L'indice de stabilité est dans de nombreux cas important pour une commande correcte.
Ce qui précède est un excellent exemple visuel de tri par insertion dans une danse.
