2 minutes
Tri de Sélection Avec Python
Dernière mise à jour: 21 septembre, 2022Le tri par sélection fonctionne en trouvant de manière répétée le plus bas (minimum) dans un tableau et en le plaçant au début. Nous gardons une trace du minimum et à chaque itération et l'échangeons avec l'élément par lequel l'itération actuelle commence.
§Un Exemple Pour Nous Aider A Comprendre
Alors allons-y étape par étape en expliquant ce que nous devons faire.
Notre itération s'exécutera pour chaque élément de notre liste. Dans la première itération, nous prendrons la première valeur du tableau comme valeur minimale par défaut.
Dans notre deuxième itération imbriquée, nous continuerons à itérer jusqu'à ce que nous trouvions une valeur inférieure à notre min. Lorsque nous la trouvons, la nouvelle valeur devient la nouvelle min et nous continuons comme ça. Lorsque la deuxième itération est terminée, nous nous retrouvons avec la valeur la plus basse comme min. Maintenant, nous échangeons le min et la première valeur que nous avons sélectionnée comme min dans notre première itération.
Dans les étapes suivantes, nous continuons à rechercher la valeur la plus basse dans la liste et à l'échanger avec la valeur avec laquelle l'itération a commencé.
Je crois qu'un exemple nous aidera à mieux comprendre comment tout cela fonctionne.
def selectionSort(arr, size):
for i in range(size):
min = i
for j in range(i+1, size):
if arr[j] < arr[min]:
min = j
arr[i], arr[min] = arr[min], arr[i]
data = [-2, 45, 0, 11, -9]
size = len(data)
selectionSort(data, size)
print('Tableau trié par ordre croissant :')
print(data)
Nous y voilà! Alors que se passe-t-il ici ? Dans la première itération, notre valeur i commence à partir de 0 et va jusqu'à la longueur du tableau moins 1. Nous parcourons donc le tableau, rien d'extraordinaire.
In the second array we start from the i+1. This means the value right next to the one we chose for the minimum. In this second array we look for a smaller value (than the arr[min]). Wehn we find it, tih snew value becomes the new min. So at the end of our first loop of the second iteration our array is this:
Dans le deuxième tableau, nous commençons par i+1. Cela signifie la valeur juste à côté de celle que nous avons choisie pour le minimum. Dans ce deuxième tableau, nous recherchons une valeur plus petite (que arr[min]). Lorsque nous la trouvons, cette nouvelle valeur devient la nouvelle min. Ainsi, à la fin de notre première boucle de la deuxième itération, notre tableau est le suivant :
[-9, 45, 0, 11, -2]
Comme vous pouvez le voir, -9 et -2 ont été échangés. Nous continuons à répéter ces étapes jusqu'à ce que notre tableau soit trié.
A la fin de la deuxième boucle :
[-9, -2, 0, 11, 45]
A la fin de la troisième boucle :
[-9, -2, 0, 11, 45]
À la fin de la quatrième boucle :
[-9, -2, 0, 11, 45]
A la fin de la cinquième boucle :
[-9, -2, 0, 11, 45]
Nos numéros aléatoires se sont avérés très faciles à trier et après la deuxième étape, nous n'avions pas vraiment besoin de faire grand-chose. Cependant, je suppose que vous avez compris comment fonctionne le tri par sélection à ce stade. Assurez-vous de l'écrire vous-même au moins une fois pour vous assurer de le comprendre au lieu de simplement le mémoriser.
§Complexité du Tri de La Sélection
Comme il y a deux boucles, on peut simplement dire que la complexité temporelle est O(N²). Une boucle pour parcourir le tableau et une autre pour les comparaisons.
Le tri par sélection est efficace en mémoire avec le seul coût de mémoire utilisé pour conserver la valeur min. Ainsi, la mémoire utilisée dans le pire des cas est O(1) pour conserver le min et O(N) pour les swaps. Donc, si vous avez le temps mais pas l'espace, optez pour le tri par sélection.
Continuez à apprendre!
Ilker AkbiyikTable Des Matières
Articles Similaires
