Une introduction à l’algorithme de tri par insertion
Le tri par insertion est une technique qui fonctionne en utilisant une sous-liste triée et en y ajoutant continuellement une valeur à partir de la liste non triée jusqu'à ce que toute la liste soit triée.
L'algorithme commence par le premier élément de la liste en tant que sous-liste triée. Il compare ensuite le numéro suivant avec le premier. S'il est supérieur, il est inséré dans le premier index. Sinon, il est laissé dans son index.
La troisième valeur est ensuite comparée aux deux autres, puis insérée dans l'index correct. Ce processus se poursuit jusqu'à ce que toute la liste soit triée.
Un examen plus approfondi du tri par insertion
La description ci-dessus peut ne pas avoir de sens pour vous. Un exemple devrait vous aider à mieux comprendre.
Supposons que vous ayez une liste : [39, 6, 2, 51, 30, 42, 7].
L'algorithme identifie 39 comme la première valeur de la sous-liste triée. L'évaluation passe ensuite à la deuxième position.
6 est ensuite comparé à 39. Comme 6 est inférieur à 39, 6 est inséré dans la première position et 39 dans la seconde. Le nouvel ordre de liste est après le premier passage est maintenant :
[6, 39, 2, 51, 30, 42, 7]
L'évaluation passe maintenant à la troisième position. 2 est comparé aux deux derniers nombres puis inséré à la bonne position. Le nouvel ordre de liste est après le deuxième passage est maintenant :
[2, 6, 39, 51, 30, 42, 7]
Pour la troisième passe, l'ordre de la liste est :
[2, 6, 39, 51, 30, 42, 7]
Le processus se répète jusqu'à ce que la liste entière soit triée.
Voir le schéma ci-dessous qui résume ces opérations :
Analyse d'algorithmes
La complexité temporelle du tri par insertion est O(n 2 ), tout comme le tri à bulles . Le nombre de comparaisons dans le pire des cas est la somme de tous les entiers de 1 à (n-1), ce qui donne une somme quadratique.
Implémentation du code
Le code Python et Java ci-dessous montre comment vous pouvez implémenter la méthode Insertion Sort.
Python:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x < n; x++) {
int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
}Mieux coder avec le pseudocode
Les exemples de code ci-dessus ont été donnés sans aucun pseudocode auquel vous pouvez vous référer pour écrire cet algorithme dans d'autres langages. La plupart des programmeurs (y compris l'auteur) aiment courir vers leurs claviers après avoir entendu des "chuchotements" sur le fonctionnement d'un programme.
Cette approche est malheureusement sujette aux erreurs car la logique du programme se complique. Aimeriez-vous améliorer votre jeu de programmation en apprenant à utiliser le pseudocode ?