Implémentation des algorithmes de tri en Python Tri à bulles (bubble sort) Le tri à bulles est un algorithme de tri très simple dont le principe est de faire remonter à chaque étape le plus grand élément du tableau à trier, comme les bulles d’air remontent à la surface de l’eau (d’où le nom de l’algorithme).. Commençons par un exemple du fonctionnement de l’algorithme.
Pour limiter les tests inutiles, nous commencerons par tamiser le 3, puis le 7 et enfin le 5. (optionnel) Tout cela ralentit les performances de l'ordinateur et peut même, pour des algorithmes mal ficelés, saturer la mémoire entraînant l'erreur D'où l'intérêt de pouvoir comparer la complexité de différents algorithmes pour ne conserver que les plus efficaces, voire même de prédire cette complexité. Dans cette situation, les algorithmes qui travaillent successivement sur des parties de plus petites tailles de l'entrée (qui seront par exemple fusionnées par la suite) auront tendance à mieux fonctionner que des algorithmes comme Il est également possible d'éviter de telles situations, par exemple en associant aux données à trier des clés plus petites, et en triant directement ces clés en mémoire vive. L'idée n'est pas si compliquée à comprendre, mais un peu plus ardue à mettre en œuvre. Très heureux de voir que nos cours vous plaisent, déjà 5 pages lues aujourd'hui !
Il consiste à parcourir le tableau Le nombre de comparaisons dans la procédure de tri bulle est le même que pour le tri par sélection :Le nombre d’échanges quant à lui dépend de l’ordre des éléments dans le tableau :Quoi qu’il en soit, la complexité du tri bulle reste en \(\mathcal{O}(N^2)\), c’est-à-dire du même ordre de grandeur que le carré du nombre d’éléments.Cette méthode de tri est très différente de la méthode de tri par sélection et s’apparente à celle utilisée pour trier ses cartes dans un jeu : on prend une carte, La comparaison avec les deux algorithmes précédents montre que la complexité du tri par insertion est plus fortement dépendante de l’ordre du tableau initial.
Ce qui devrait nous donner le résultat suivant (voir la figure suivante).Cette manœuvre a ainsi pour but de placer sur la dernière feuille, le nombre le plus grand, tout en gardant un sous-arbre qui soit tamisé. Cest très important pour nous! Nous devrions ainsi obtenir le résultat suivant (voir la figure suivante).Cette fois, l'arbre est trié dans le bon ordre, l'algorithme est terminé.
Elle consiste à trier des sous-suites de longueur 2, 4, …, une puissance de 2, jusqu’à la longueur du tableau.Aidez-nous à évaluer le niveau de lecture de ce document.Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).
En fait, tout facteur constant peut être considéré comme négligeable. Ainsi dans le pire des cas, l’algorithme du tri par insertion a le même coût que celui par sélection : il est quadratique en fonction de la longueur de la liste. Mais rassurez-vous, il reste encore une étape, un peu plus complexe. Nous ne dépasserons pas des tableaux de taille 10 000 (les algorithmes lents devraient déjà mettre de 1 à 4 secondes pour effectuer leur tri), car au-delà, vous pourriez vous lasser. Dans les exemples cités plus haut, on suppose que toutes les données sont présentes en mémoire centrale (ou accessibles en mémoire virtuelle). Un facteur 2, 3, 20… peut être considéré comme négligeable. Je vous expliquerai le principe avant de vous proposer un implémentation possible. Je vous présente sur la figure suivante les résultats obtenus avec mon vieux PC.Avant même de comparer les performances de nos algorithmes, on peut remarquer une certaine irrégularité : des pics et des creux apparaissent et semblent (en général) avoir lieu pour tous les algorithmes.