Python tri par sélection
Fonctions et méthodes Python
Michael Zippo
01.11.2021
Un tri par sélection Python divise une liste en deux petites listes. Une liste représente les éléments triés. L’autre liste contient les éléments non triés. Le tri par sélection trouve les valeurs les plus petites ou les plus élevées dans chaque itération et déplace ces valeurs vers la liste ordonnée.
Le tri des listes est une opération courante dans une gamme de programmes.
Considérez cet exemple : un enseignant souhaite en savoir plus sur les résultats obtenus par ses élèves lors de leur test le plus récent. Un enseignant peut vouloir trier les élèves‚Äô scores par ordre croissant et décroissant. Cela leur permettra de savoir facilement quels ont été les scores de test les plus élevés et les plus bas.
Entrez, le tri par sélection. Le tri par sélection est un algorithme que vous pouvez utiliser pour trier une liste dans l’ordre croissant ou décroissant.
Dans ce guide, nous allons expliquer comment écrire un programme de tri par sélection en Python. Nous allons parcourir un exemple tout au long de ce guide afin que vous puissiez apprendre les tenants et les aboutissants des tris de sélection.
Qu’est-ce qu’un tri de sélection Python ?
Un tri de sélection Python trouve à plusieurs reprises l’élément minimum dans une liste et déplace cet élément à une fin particulière de la liste. Le tri continue jusqu’à ce que le tableau soit trié dans l’ordre. Vous pouvez également demander un tri par sélection pour trouver l’élément maximum. Les deux approches trient une liste.
Les tris par sélection supposent que le premier élément d’une liste est la plus petite valeur. Le tri comparera ensuite cette valeur avec le deuxième élément. Si le deuxième élément est inférieur à la valeur minimale, le deuxième élément devient la valeur minimale.
Ce processus est répété jusqu’à ce que le dernier élément de la liste soit atteint. Une fois cet élément atteint, la valeur minimale est placée au début de la liste non triée.
81% des participants ont déclaré qu’ils se sentaient plus confiants quant à leurs perspectives d’emploi technologique après avoir assisté à un bootcamp. Soyez jumelé à un bootcamp aujourd’hui.
Le diplômé moyen d’un bootcamp a passé moins de six mois en transition de carrière, du démarrage d’un bootcamp à la recherche de son premier emploi.
Il n’y a pas de meilleur moyen pour en savoir plus sur les tris par sélection que de parcourir un exemple. Parcourons et trions une liste des notes des élèves par ordre croissant. Considérez cette liste non triée :
Nous allons commencer par appeler la première valeur de notre liste le minimum . Chaque itération du tri par sélection trouvera le plus petit élément et le déplacera dans le sous-tableau trié.
Le tri de l’élément minimum est une option. Un tri par sélection fonctionne si vous triez l’élément maximum. Mais, nous‚Äô utilisez l’élément minimum dans cet exemple.
Ensuite, nous allons comparer la valeur minimale avec le deuxième élément. Si cet élément est inférieur au minimum, le deuxième élément devrait devenir la valeur minimale.
Nous allons comparer 73 et 62. 73 est supérieur à 62, ce qui signifie que notre nouvelle valeur minimale est 62. Notre liste passera alors par tous les autres nombres de notre liste :
- Est 61 supérieur à 6 2 (notre valeur minimale) ? Non, alors échangez les numéros. Le minimum devient 61.
- Est-ce que 69 est supérieur à 61 (notre valeur minimale) ? Oui, alors ne faites rien. Séjours minimum à 61.
Notre liste se ressemble :
Lorsque vous atteignez le fin de la liste, vous pouvez déplacer le minimum au début de la liste :
61 (notre valeur minimale) a été déplacée au début de la liste, et toutes les autres valeurs ont augmenté d’une unité. Nous allons répéter ce processus jusqu’à ce que tous les éléments soient triés.
Chaque itération de notre liste renverra ce qui suit :
- 73, 62, 61, 69
- 61, 73, 62, 69
- 61, 62, 73, 69
- 61, 62, 69, 73
Lorsque le tri par sélection a vérifié tous les éléments de la liste, le tri s’arrêtera.
Le sous-tableau trié et le sous-tableau non trié nous sont tous deux invisibles. Notre algorithme trie un tableau pour nous et garde une trace de la partie non triée du tableau.
Comment effectuer un tri par sélection en Python
Vous êtes maintenant familiarisé avec la théorie : eh bien terminé! C’est l’heure du grand défi. Nous allons implémenter l’algorithme de tri par sélection en Python. √âcrivons un programme qui prend un tableau Python et le trie par ordre croissant.
Définir une fonction de tri
Nous allons commencer par définir une fonction Python qui effectue notre tri par sélection :
Nous avons commencé par utiliser la méthode Python len() pour obtenir la longueur de notre liste. Nous puis utilisez-le pour initier une boucle Python for qui boucle sur chaque élément de notre liste.
Pour chaque itération de la boucle, nous définissons la valeur de minimum comme premier élément de notre liste. Nous l’avons fait dans notre procédure pas à pas plus tôt. Une fois que nous avons‚Äô Après avoir défini une valeur minimale, une autre boucle for commence qui parcourt chaque élément de notre liste.
Pour chaque élément de la liste, notre algorithme vérifie si la valeur minimale est supérieure à cet article. Si c’est le cas, rien ne se passe ; sinon, la valeur minimale devient l’élément que le programme lit.
En parcourant chaque élément de notre liste, notre algorithme déplace la valeur minimale au début de la liste. Ensuite, notre programme continuera jusqu’à ce que la boucle for supérieure se termine. C’est parce que les tris par sélection s’exécutent un nombre de fois égal à la longueur d’une liste.
Appelez la fonction de tri
Vous avez peut-être remarqué que si nous exécutons notre programme, rien ne se passe. C’est parce que nous n’avons pas encore dit à notre code quelles valeurs utiliser. Ajoutez le code suivant au bas de votre programme, en dehors de la fonction sortList :
"Career Karma est entré dans ma vie au moment o√π j’en avais le plus besoin et m’a rapidement aidé à suivre un bootcamp. Deux mois après avoir obtenu mon diplôme, j’ai trouvé mon travail de rêve qui correspond à mes valeurs et à mes objectifs dans la vie !"
Venus, ingénieur logiciel chez Rockbot
Lorsque nous exécutons notre programme , ce qui suit est renvoyé :
Notre liste a été triée. Tapotez-vous dans le dos ; vous l’avez fait !
Les tris par sélection peuvent être utilisés pour trier une liste par ordre décroissant. Si vous souhaitez trier une liste de cette manière, vous pouvez modifier le paramètre "if" instruction dans la sélection trier comme suit :
Nous avons changé le signe inférieur à en signe supérieur à. Cela triera notre liste par ordre décroissant, car la valeur minimale sera définie sur la valeur la plus élevée de la liste. Techniquement, notre valeur minimum devient une valeur maximum.
Les tris par sélection, comme les tris à bulles, sont mieux utilisés pour les petites listes. En effet, l’algorithme n’est pas‚Äô Il est aussi efficace que d’autres, comme un tri par insertion lorsqu’il est utilisé sur de plus grandes listes.
Un tri par sélection est un excellent tri à apprendre lorsque vous débutez avec les algorithmes de tri. D’autres tris peuvent être difficiles à maaîtriser, mais avoir une compréhension claire des tris par sélection peut vous aider à comprendre différents types de listes.
Le tri par sélection a une complexité temporelle de O( n2). Cela signifie que la complexité de l’algorithme augmentera de façon exponentielle en fonction du nombre d’éléments dans la liste.
O(n2) est la complexité la pire, la moyenne et la meilleure pour ce cas. algorithme. Si vous souhaitez en savoir plus e sur les complexités de tri, consultez notre guide sur la Big O Notation.
Sélection Les tris sont une méthode importante de tri des données. Les tris par sélection parcourent chaque élément d’une liste et, à chaque itération, déplacent le plus petit élément au début de la liste. Cela se produit jusqu’à ce que chaque élément de la liste ait été lu.
Les tris par sélection ne sont pas largement utilisés en dehors de l’enseignement car il existe des algorithmes plus efficaces à utiliser. Cela dit, ils constituent un bon tremplin pour apprendre d’autres tris, comme un tri par insertion ou par fusion.
