2 minutes
Tri Par Insertion Avec Python
Dernière mise à jour: 23 septembre, 2022Le tri par insertion est l'un des algorithmes de tri simples qui peuvent très bien fonctionner sur des listes (ou tableaux) relativement plus petites. Il fonctionne mieux dans les tableaux qui sont déjà partiellement triés, car il n'a pas besoin de déclencher une seconde itération. Nous allons voir la raison tout de suite.
Ok, donc fondamentalement, nous comparons deux valeurs adjacentes et les échangeons si elles sont dans le mauvais ordre. Cela nous aidera à porter le courant le plus bas au début de la liste (dans un tri maximum).
§Un Exemple Pour Nous Aider À Comprendre
Notre première itération déclenchera la taille du tableau/liste moins une fois. Notre deuxième boucle se déclenchera lorsque la valeur actuelle devra être échangée avec la valeur adjacente. Si le swap est nécessaire lors de la prochaine exécution de la deuxième boucle, nous recherchons à nouveau le besoin de swap dans les valeurs situées à un indice à gauche du précédent. De cette façon, nous poussons la valeur la plus basse vers l'avant à chaque itération. Cette logique est proche de la façon dont nous trierions réellement les cartes de jeu entre nos mains, n'est-ce pas ?
def insertionsort(arr, size):
for i in range(1, size):
j = i-1
while j>=0 and arr[i] < arr[j]:
arr[j], arr[i] = arr[i], arr[j]
j -= 1
i -= 1
array = [5,4,6,8,2,7,1]
sz = len(array)
insertionsort(array, sz)
print(array)
Je pense qu'aller étape par étape sur cet exemple aidera beaucoup.
Lorsque la deuxième boucle commence, nous commençons avec i=1 et j=0. Ensuite, nous vérifions si nous sommes dans les limites du tableau. Si c'est le cas (et nous sommes dans l'exemple), nous commençons la boucle while. Si arr[i] est plus petit que arr[j] (si gauche est plus grand que droite) nous échangeons et décrémentons i et j de un pour vérifier les deux valeurs d'un indice à gauche. Ainsi, à la fin de la première itération de la deuxième boucle, notre tableau ressemble à ceci :
[4, 5, 6, 8, 2, 7, 1]
Comme vous pouvez le voir nous avons échangé 4 et 5 et nous n'avons rien sur la gauche donc nous nous arrêtons. Nous commençons la deuxième exécution de la première itération avec i=2 et j=1. Il n'y a pas besoin d'échanger donc nous passons à autre chose. Pas besoin d'échanger à la troisième exécution non plus.
A la quatrième exécution de la première itération j=3 et i=4. Après le premier échange (2 et 8) :
[4, 5, 6, 2, 8, 7, 1]
Maintenant, nous décrémentons i et j et vérifions à nouveau. Un autre échange est nécessaire et le résultat est (6 et 2 sont échangés) :
[4, 5, 2, 6, 8, 7, 1]
Je suppose que vous avez compris la logique, nous n'allons donc pas expliquer chaque étape. Cela rendrait ce post beaucoup plus long qu'il ne devrait l'être. Nous continuons à exécuter la boucle while jusqu'à ce que le 2 soit la première valeur de notre tableau. Nous continuerons à "sélectionner" le plus bas et à le pousser vers l'avant jusqu'à ce que nous ayons un tableau trié.
§Complexité du Tri de La Sélection
Le tri par sélection n'est pas très efficace en temps avec une boucle imbriquée à l'intérieur d'une itération avec la complexité temporelle de O(N²). Mais c'est vraiment efficace dans l'espace car nous n'avons PAS besoin de garder un gros tableau auxiliaire pour conserver nos valeurs ou quoi que ce soit. La complexité spatiale du tri par sélection est O(1). Alors pensez-y la prochaine fois que vous avez le temps mais pas l'espace.
Continuez à apprendre!
Ilker AkbiyikTable Des Matières
Articles Similaires
