Tri d'insertion Python

Dans cet article, nous parlerons de l'algorithme de tri d'insertion à Python. Il s'agit de l'algorithme de tri le plus simple et est plus efficace ou plus puissant pour gérer les données avec une petite gamme ou tri une liste partiellement triée. Une procédure appelée le tri d'insertion est utilisée pour classer les nombres dans les tableaux de manière ascendante ou descendante. Cet algorithme utilise une approche en place et stable pour trier efficacement le tableau. Ici, nous expliquerons en détail cet algorithme de tri et implémenter l'algorithme de tri d'insertion en Python à l'aide d'exemples. Élaborons le fonctionnement du tri d'insertion.

Comment fonctionne le tri d'insertion?

Le fonctionnement du type d'insertion est discuté en détail ici. Les nombres sont triés en utilisant le tri d'insertion. Il place à plusieurs reprises l'élément non trié ultérieur à l'endroit approprié dans la liste précédemment triée. Le concept fondamental consiste à comparer le deuxième membre au premier élément du tableau qui est vraisemblablement déjà trié. Si le deuxième élément est une valeur plus petite que la première, il est commuté. Cette procédure est répétée pour les éléments de tableau restants. Les pires et moyens cas de tri d'insertion ont une complexité temporelle O (n2), tandis que le meilleur cas a une complexité temporelle O (n).

Exemple 1:
Nous prenons un exemple linéaire pour comprendre le concept de tri d'insertion. Le code de référence est fourni dans ce qui suit:

def insertionsortalgo (arr):
pour n dans la gamme (1, Len (ARR)):
key = arr [n]
M = n-1
tandis que m> = 0 et clé < arr[m] :
arr [m + 1] = arr [m]
m - = 1
arr [m + 1] = clé
arr = [29, 15, 7, 10, 46]
Insertionsortalgo (arr)
Print ("Le résultat du tableau trié est:", arr)

Comme le montre cet exemple, nous définissons une fonction de tri d'insertion à la ligne 1. Cette implémentation prend une liste de nombres en entrée et trie la liste dans l'ordre croissant. Nous attribuons la variable «Arr» en tant que liste dans cet exemple. Après cela, nous commençons la boucle extérieure qui vérifie l'index du tableau. La boucle «pour» est utilisée ici. La gamme commence à 1, qui est le deuxième numéro d'un tableau, et se poursuit à travers la boucle jusqu'au dernier élément.

À l'intérieur de cette boucle, nous initialisons une variable clé qui vérifie la valeur de l'index un par un. Après cela, nous créons une variable qui contient la valeur du tableau (N-1). La boucle intérieure commence maintenant à vérifier les valeurs du tableau. La boucle intérieure commence à l'indice actuel de la boucle externe et compare l'élément actuel avec l'élément précédent. Si l'élément précédent est plus grand, il est décalé vers la droite et l'indice de l'élément actuel est diminué. Cela continue jusqu'à ce que la position correcte pour l'élément actuel soit trouvé.

L'élément actuel est placé dans l'endroit approprié après la fin de la boucle intérieure. En fin de compte, nous déclarons et initialisons le tableau nommé «ARR». Nous avons utilisé ce tableau dans la fonction d'insertion précédemment décrite pour effectuer le tri sur le tableau. Enfin, nous fournissons le tableau dans la déclaration d'impression pour afficher le résultat sur la console.

La sortie de cet exemple de programme est donnée dans ce qui suit:

[7, 10, 15, 29, 46]

Exemple 2:
Nous expliquerons également le tri de l'insertion à Python à l'aide d'un autre exemple. Nous créons et exécutons cet exemple à l'aide de n'importe quel outil Python tel que PyCharm ou Jupiter Notebook. Le code de référence pour cet autre exemple est joint dans les éléments suivants:

def sortArray (arrayx):
pour i à portée (1, Len (Arrayx)):
temp = arrayx [i]
PREMERSEMENT = I-1
tandis que préalable> = 0 et temp < arrayX[previousElement]:
ArrayX [PREVERSEMENT + 1] = ArrayX [PREVERSEMENT]
PREMERSEMENT- = 1
arrayx [préalable + 1] = temp
Arrayx = [45, 66, 37, 99, 10, 5, 2, 78, 1]
SoiRARray (ArrayX)
print ("Le résultat du tableau trié est", arrayx)

Nous déclarons un tableau à des fins de tri en définissant la fonction nommée «Sultarray». Nous utilisons une boucle pour traverser le tableau et démarrer la recherche par index «1». Nous mettons la longueur du tableau et de l'index «1» dans la fonction de plage où la boucle est exécutée. Nous mettons une autre variable dans laquelle nous stockons actuellement la valeur de l'itération de la boucle «i» dans le tableau et attribuons la valeur à la variable «temporaire». Nous stockons la valeur précédente qui est probablement le premier élément du tableau à partir duquel nous comparons la variable «temporaire» pour rechercher si cette valeur est supérieure ou plus petite que la valeur stockée dans la variable «temporaire» et nommer cette variable comme « préalable ».

La boucle intérieure prend la valeur présente dans la variable «Précéaire» pour vérifier si la valeur est supérieure à «0». Ensuite, nous comparons les deux variables nommées «Temp» et «Précéaire» qui sont stockées dans le tableau. Cette valeur est passée jusqu'à ce que la boucle ne reste pas à la fin. Si la valeur du tableau qui est stockée dans «PREVERSEMENT» est «+1», cela signifie que la valeur de modification de la boucle est moindre que la valeur précédente du tableau qui est stocké dans l'index «0». Ensuite, nous échangeons ces deux variables à travers lesquelles la valeur moindre est déplacée vers l'index «0» et la plus grande valeur est déplacée à la place d'une autre variable.

Ici, nous écrivons la logique pour échanger les éléments du tableau pour trier les éléments. Maintenant, toutes les valeurs du tableau sont vérifiées une par une. La modification de la position des valeurs est moindre et déplacée vers le début du tableau. Prenons ce tableau pour considérer. Nous commençons le tableau avec l'index «1». Cela signifie que nous prenons d'abord «66». Ensuite, nous comparons la valeur de «66» à la valeur précédente qui est stockée dans l'index «0» qui est «45». Maintenant, «45» est moins que «66». Ainsi, nous échangeons ensuite la variable qui stocke la valeur de «66». Ensuite, nous attribuons la valeur précédente du tableau dans la variable «Temp». Maintenant, nous stockons la valeur de «45» dans la variable «Temp».

Enfin, nous attribuons la valeur stockée dans «Array [PREVERSElement +1]» où la valeur suivante à la valeur précédente est stockée. Après cela, nous stockons la valeur précédente suivante en température pour recommencer à trier. De cette façon, nous échangeons les valeurs plus grandes et plus petites. Donc, jusqu'à ce que la boucle soit valide, les éléments du tableau sont stockés rapidement, un par un. À la fin du code, nous affichons le résultat de ce tableau sur la console via l'instruction PRINT.

Ici, la sortie de ce tableau est affichée sur la console car le résultat du tableau stocké est

[1,2,5,10,37,45,66,78,99].

Conclusion

Nous concluons que le tri de l'insertion est le type de tri le plus important qui est utilisé pour trier tous les éléments d'un tableau en python. Le tri de l'insertion est un algorithme stable et en place mais inefficace qui a de nombreux avantages dont nous avons discuté avec l'aide d'exemples. Ici, nous avons divisé le tableau en deux parties: trié et non trié. La comparaison entre ces deux parties a créé le tableau trié à la fin.