Les algorithmes sont des instructions bien définies utilisées pour résoudre des problèmes. Imaginez que vous habitiez au deuxième étage d’un immeuble et que vous deviez vous donner des instructions pour vérifier votre courrier. Votre algorithme ressemblerait à ceci :
Remarquez que nous devions être très bien définis dans nos instructions. Nous ne pouvons pas sortir de l’appartement sans ouvrir la porte. L’omission d’une instruction peut empêcher les développeurs de résoudre un problème.
Il existe plusieurs types d’algorithmes différents en python. Certains d’entre eux peuvent aider à résoudre les problèmes plus rapidement que d’autres. Nous mesurons cela à l’aide de la notation Big-O.
Dans cet article, nous plongeons dans différents types d’algorithmes de tri tout en mesurant leur efficacité, ou notation Big-O.
Algorithmes de tri Python
Les algorithmes de tri sont des algorithmes de blocs de construction sur lesquels de nombreux autres algorithmes peuvent s’appuyer. Les algorithmes de tri sont utilisés pour résoudre des problèmes tels que la recherche d’un ou plusieurs éléments sur une liste, la sélection d’un ou plusieurs éléments dans une liste et les distributions. Résoudre ces problèmes est beaucoup plus rapide gr√¢ce au tri.
Imaginez que vous ayez un dressing qui n’est pas seulement organisé en termes de vêtements décontractés, de vêtements de sport et d’affaires, mais aussi de couleur coordonné. Dans quelle mesure serait-il plus rapide de trouver votre short de sport bleu dans la liste de votre placard par rapport à un placard non organisé ou non trié ?
Algorithme de tri intégré Python
Python possède un algorithme de tri intégré, sorted(), qui peut être utilisé pour les listes.
Tri à bulles
Le tri à bulles est l’algorithme de tri le plus simple, mais très lent, avec un Notation Big-O de O(n^2). Nous en apprendrons plus sur Big-O plus tard. Pour l’instant, parcourons la liste plusieurs fois, en comparant les éléments un par un et en les échangeant en conséquence. Prenez l’exemple ci-dessous.
81 % des participants ont déclaré qu’ils se sentaient plus confiants quant à leurs perspectives d’emploi en technologie 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.
Remarquez à chaque fois que nous avons pour parcourir la liste, la section de la liste que nous devons parcourir devient plus petite car les éléments à droite (en orange) ont déjà été triés. Vous trouverez ci-dessous une explication de ce qui se passe avec notre visualisation de tri à bulles ci-dessus.
Le code pour le tri à bulles aimerait quelque chose comme l’exemple de code ci-dessous :
Tri par insertion
Si vous avez déjà joué au poker, vous avez probablement utilisé cette méthode de tri. Avec le tri par insertion, vous commenceriez avec une carte en main, choisiriez la carte suivante au hasard, l’inséreriez dans le bon ordre de tri et recommenceriez.
