Implémentez un algorithme de tri à bulles unidimensionnel récursif. Tri à bulles (Pascal). Principe de tri visuel
Tout le monde sait parfaitement que de la classe des tris d'échange le plus méthode rapide- c'est ce qu'on appelle tri rapide. Des thèses sont écrites à ce sujet, de nombreux articles sur Habré lui sont consacrés et des algorithmes hybrides complexes sont inventés sur cette base. Mais aujourd'hui nous ne parlerons pas tri rapide, et sur une autre méthode d'échange - le bon vieux tri à bulles et ses améliorations, modifications, mutations et variations.
Les avantages pratiques de ces méthodes ne sont pas si grands, et de nombreux utilisateurs de Habra ont vécu tout cela en première année. Par conséquent, l'article s'adresse à ceux qui viennent de s'intéresser à la théorie des algorithmes et font leurs premiers pas dans cette direction.
image : bulles
Aujourd'hui, nous allons parler du plus simple tris d'échange.
Si quelqu'un est intéressé, je dirai qu'il existe d'autres cours - tri par sélection, tri par insertion, tri par fusion, tri par répartition, sortes hybrides Et tris parallèles. D'ailleurs, il y a aussi tris ésotériques. Il s'agit de divers pseudo-algorithmes faux, fondamentalement irréalisables, comiques et autres, sur lesquels j'écrirai quelques articles dans le hub « IT Humour ».
Mais cela n’a rien à voir avec le cours d’aujourd’hui ; nous ne nous intéressons maintenant qu’aux simples tris d’échanges. Il existe également de nombreux tris d'échange eux-mêmes (j'en connais plus d'une douzaine), nous allons donc examiner ce qu'on appelle tri à bulles et quelques autres qui y sont étroitement liés.
Je vous préviens à l'avance que presque toutes les méthodes ci-dessus sont très lentes et qu'il n'y aura pas d'analyse approfondie de leur complexité temporelle. Certains sont plus rapides, d'autres plus lents, mais grosso modo, on peut dire qu'en moyenne Ô(n°2). De plus, je ne vois aucune raison d'encombrer l'article avec des implémentations dans des langages de programmation. Les personnes intéressées peuvent facilement trouver des exemples de code sur Rosetta, Wikipedia ou ailleurs.
Mais revenons au tri des échanges. L'ordre se produit à la suite d'itérations séquentielles répétées du tableau et de comparaison de paires d'éléments les uns avec les autres. Si les éléments comparés ne sont pas triés les uns par rapport aux autres, nous les échangeons. La seule question est de savoir comment contourner exactement le tableau et sur quelle base sélectionner les paires à comparer.
Commençons non pas par le tri à bulles standard, mais par un algorithme appelé...
Type stupide
Le tri est vraiment stupide. Nous parcourons le tableau de gauche à droite et comparons les voisins en cours de route. Si nous rencontrons une paire d’éléments non triés mutuellement, nous les échangeons et revenons à la case départ, c’est-à-dire au tout début. Nous reprenons et vérifions le tableau si nous rencontrons à nouveau la « mauvaise » paire éléments voisins, puis on change de place et on recommence. On continue jusqu'à ce que le tableau soit petit à petit trié.« N’importe quel imbécile peut faire cela », direz-vous, et vous aurez tout à fait raison. C’est pour cela que le tri est qualifié de « stupide ». Dans cette conférence, nous améliorerons et modifierons constamment cette méthode. Maintenant, il a des difficultés temporaires Ô(n°3), après avoir apporté une correction, nous l'amenerons déjà à Ô(n°2), puis on accélérera un peu plus, puis un peu plus, et à la fin on obtiendra Ô(n enregistrer n) – et ce ne sera pas du tout un « Tri rapide » !
Apportons une seule amélioration au tri stupide. Après avoir découvert deux éléments adjacents non triés lors du passage et les avoir échangés, nous ne reviendrons pas au début du tableau, mais continuerons calmement à le parcourir jusqu'à la toute fin.
Dans ce cas, nous n’avons devant nous rien d’autre que le bien connu...
Tri à bulles
Ou tri par échanges simples. Un classique immortel du genre. Le principe de fonctionnement est simple : on parcourt le tableau du début à la fin, en échangeant simultanément les éléments voisins non triés. À la suite du premier transfert dernier endroit L’élément maximum « apparaîtra ». Maintenant, nous parcourons à nouveau la partie non triée du tableau (du premier élément à l'avant-dernier) et modifions les voisins non triés en cours de route. Le deuxième plus grand élément occupera l’avant-dernière place. En continuant dans le même esprit, nous parcourrons la partie non triée de plus en plus réduite du tableau, poussant les maxima trouvés jusqu'au bout.Si nous poussons non seulement les maximums jusqu'au bout, mais aussi les minimums jusqu'au début, alors nous réussissons...
Tri au shaker
Elle est la même trier aléatoirement, elle est pareille tri des cocktails. Le processus commence comme dans une « bulle » : on fait sortir le maximum jusqu'au fond. Après cela, nous tournons à 180 0 et passons à revers, en roulant en même temps au début non pas le maximum, mais le minimum. Après avoir trié le premier et derniers éléments, on refait un saut périlleux. Après plusieurs allers-retours, nous finissons par mettre fin au processus et nous retrouvons au milieu de la liste.Le tri par shaker fonctionne un peu plus rapidement que le tri par bulles, puisque les maximums et les minimums migrent alternativement à travers le tableau dans les directions requises. Les améliorations, comme on dit, sont évidentes.
Comme vous pouvez le constater, si vous abordez le processus d'énumération de manière créative, le déplacement des éléments lourds (légers) vers les extrémités du tableau se produit plus rapidement. Les artisans ont donc proposé une autre « feuille de route » non standard pour contourner la liste.
Tri pair-impair
Cette fois, nous ne nous précipiterons pas à travers le tableau, mais reviendrons à nouveau à l'idée d'une marche systématique de gauche à droite, mais nous ne ferons qu'un pas plus large. Lors du premier passage, les éléments de clé impaire sont comparés à leurs voisins basés aux places paires (le 1er est comparé au 2ème, puis le 3ème au 4ème, le 5ème au 6ème, et ainsi de suite). Ensuite, au contraire, nous comparons/modifions les éléments « pairs » avec des éléments « impairs ». Puis encore « impair-pair », puis encore « pair-impair ». Le processus s'arrête lorsque, après deux passages consécutifs dans la matrice (« impair-pair » et « pair-impair »), aucun échange n'a eu lieu. Alors, ils ont réglé le problème.Dans une « bulle » régulière, à chaque passage nous pressons systématiquement le maximum actuel jusqu'à la fin du tableau. Si vous sautez le long des indices pairs et impairs, alors tous les éléments plus ou moins grands du tableau sont simultanément poussés vers la droite d'une position en une seule fois. Cela fonctionne plus rapidement de cette façon.
Regardons le dernier redécoré* Pour Sortuvannya bulbashka** - Tri par peigne***. Cette méthode s'organise très rapidement, Ô(n°2) est sa pire difficulté. En moyenne, au fil du temps, nous avons Ô(n enregistrer n), et le meilleur, vous n'y croirez même pas, Ô(n). C'est-à-dire un très digne concurrent de toutes sortes de " tris rapides" Et cela, remarquez, sans recourir à la récursivité. Cependant, j'ai promis qu'aujourd'hui nous n'aborderions pas les vitesses de croisière, je vais donc arrêter de parler et passer directement à l'algorithme.
C'est la faute des tortues
Un peu de contexte. En 1980, Włodzimierz Dobosiewicz expliquait pourquoi le tri à bulles et ses dérivés fonctionnent si lentement. C'est à cause des tortues. Les « tortues » sont de petits éléments situés à la fin de la liste. Comme vous l'avez peut-être remarqué, les tris à bulles se concentrent sur les « lapins » (à ne pas confondre avec les « lapins » de Babushkin) – des éléments de grande valeur au début de la liste. Ils avancent très vite vers la ligne d’arrivée. Mais les reptiles lents rampent jusqu'au début à contrecœur. Vous pouvez personnaliser la tortilla en utilisant peignes.image : tortue coupable
Tri au peigne
Dans « bulle », « shaker » et « impair-pair », lors d'une itération dans un tableau, les éléments voisins sont comparés. L'idée principale du "peigne" est d'en prendre dans un premier temps suffisamment longue distance entre les éléments comparés et, à mesure que le tableau est ordonné, réduisez cette distance au minimum. De cette façon, nous peignons en quelque sorte le tableau, le lissant progressivement en brins de plus en plus nets.Il est préférable de prendre l'écart initial entre les éléments comparés non pas n'importe lequel, mais en tenant compte d'une valeur particulière appelée facteur réducteur, valeur optimale ce qui est environ 1,247. Premièrement, la distance entre les éléments est égale à la taille du tableau divisée par facteur de réduction(le résultat est bien entendu arrondi à l’entier le plus proche). Ensuite, après avoir parcouru le tableau avec ce pas, nous divisons à nouveau le pas par facteur de réduction et parcourez à nouveau la liste. Cela continue jusqu'à ce que la différence d'indice atteigne un. Dans ce cas, le tableau est trié avec une bulle régulière.
La valeur optimale a été établie expérimentalement et théoriquement facteur de réduction:
Lorsque cette méthode a été inventée, peu de gens y prêtaient attention au tournant des années 70 et 80. Une décennie plus tard, alors que la programmation n'était plus l'apanage des scientifiques et des ingénieurs d'IBM, mais gagnait déjà rapidement en popularité, la méthode a été redécouverte, étudiée et popularisée en 1991 par Stephen Lacy et Richard Box.
C’est en fait tout ce que je voulais vous dire sur le tri à bulles et autres.
- Remarques
* raccourci ( ukrainien) - amélioration
** Triés par ampoule ( ukrainien) – Tri à bulles
*** Tri par peigne ( ukrainien) – Tri au peigne
Un algorithme pour trier un tableau unidimensionnel en utilisant la méthode « bulle ». Description de l'algorithme. Schéma fonctionnel et programme pour trier par ordre croissant un tableau de types réelde 7 éléments.
Description de l'algorithme
La classification des méthodes de tri n'est pas toujours clairement définie. Arrêtons-nous sur la méthode dans laquelle l'échange de deux éléments est la principale caractéristique du processus. Ci-dessous l'algorithme de tri échange simple basé sur le principe comparaisonsEtéchange paires d’éléments adjacents jusqu’à ce que tous les éléments soient triés.
Comme avec les méthodes de sélection simples précédentes, nous effectuons des passages répétés à travers le tableau, en passant à chaque fois au crible le plus petit élément de l'ensemble restant, en nous déplaçant vers l'extrémité gauche du tableau. Si, pour changer, nous considérons le tableau verticalement plutôt qu'horizontalement, et - avec un peu d'imagination - imaginons les éléments comme des bulles dans un réservoir d'eau, avec des "poids" correspondant à leurs touches, alors chaque passage à travers le tableau donne une bulle « flottante » jusqu'à un niveau correspondant à son poids (voir tableau 2). Cette méthode est communément appelée tri à bulles. Sa version la plus simple est présentée dans le programme 1.
Exemple de tri à bulles
procédure tri à bulles;
var je, j: indice; x: article;
commencer pour je := 2 à n faire
commencer pour j := n jusqu'à je faire
si un[j-1].clé > un[j].clé alors
commencer x := un[j-1]; un[j-1] := un[j]; un[j] := x
fin{tri à bulles}
Tri à bulles
Cet algorithme est facile à optimiser. Exemple dans le tableau. La figure 2 montre que les trois dernières passes n'affectent en rien l'ordre des éléments, puisqu'ils sont déjà triés. Une manière évidente de s’améliorer cet algorithme- il s'agit de rappeler si un échange a été effectué sur un pass donné. Sinon, cela signifie que l'algorithme peut être poursuivi si vous vous souvenez non seulement du fait de l'échange, mais également du lieu (index) du dernier échange. Après tout, il est clair que toutes les paires d'éléments voisins avec des indices inférieurs à cet indice k, sont déjà situés dans dans le bon ordre. Par conséquent, les passes suivantes peuvent se terminer à cet index, au lieu de passer à une limite inférieure prédéterminée. je. Cependant, un programmeur attentif remarquera ici une étrange asymétrie : une "bulle" mal placée à l'extrémité "lourde" du tableau trié flottera en un seul passage, et un élément mal placé à l'extrémité "légère" coulera en un seul passage. bon endroit un seul pas à chaque passage. Par exemple, tableau
12 18 42 44 55 67 94 06
sera trié en utilisant la méthode des bulles en un seul passage et en triant un tableau
94 06 12 18 42 44 55 67
nécessitera sept passes. Cette asymétrie contre nature suggère une troisième amélioration : changer la direction des passages successifs.
Analyse du tri des bulles.
Le nombre de comparaisons dans l'algorithme d'échange simple est
,
les nombres minimum, moyen et maximum de transferts (affectations d'éléments) sont égaux
,
,
.
Organigramme du tri des bulles.
Programmetri
A : tableau de réels ;
N, j, k : entier ;
WriteLn("Tableau d'entrée");
pour j:= 1 à N faire
Écrire("A", j, "=");
WriteLn("Tableau source");
pour j:= 1 à N faire
Écrire(A[j]:8:1);
pour j:= 2 à k faire
si A > A[j] alors
UNE := UNE[j];
WriteLn("Tableau trié");
pour j:= 1 à N faire
Écrire(A[j]:8:1);
On estime que jusqu'à un quart du temps ordinateurs centralisés axé sur le tri des données. En effet, il est beaucoup plus facile de trouver une valeur dans un tableau pré-trié. Sinon, la recherche s’apparente un peu à chercher une aiguille dans une botte de foin.
Il y a des programmeurs qui font tout heures de travail sont réalisés dans l'étude et la mise en œuvre d'algorithmes de tri. En effet, la grande majorité des logiciels d’entreprise impliquent la gestion de bases de données. Les gens recherchent constamment des informations dans les bases de données. Cela signifie que les algorithmes de recherche sont très demandés.
Mais il y a un « mais ». Algorithmes de recherche travaillez beaucoup plus rapidement avec des bases de données déjà triées. Dans ce cas, seule une recherche linéaire est requise.
Même si les ordinateurs sont parfois sans utilisateurs, les algorithmes de tri continuent de fonctionner sur les bases de données. Les chercheurs reviennent et la base de données est déjà triée en fonction de l'un ou l'autre objectif de recherche.
Cet article fournit des exemples d'implémentations d'algorithmes de tri standard.
Tri de sélection
Afin de trier un tableau par ordre croissant, à chaque itération vous devez retrouver l'élément avec valeur la plus élevée. Avec cela, vous devez échanger le dernier élément. L’élément suivant avec la valeur la plus élevée est placé à l’avant-dernière place. Cela devrait se produire jusqu'à ce que les éléments aux premiers endroits du tableau soient dans le bon ordre.
Code C++
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
données[i] = données[j];
données[j] = tmp;
Code C++
) ) Le tri par insertion divise le tableau en deux régions : ordonnée et non ordonnée. Initialement, le tableau entier est une région non ordonnée. Lors du premier passage, le premier élément de la région non ordonnée est supprimé et placé à la position correcte dans la région ordonnée. À chaque passage, la taille de la région ordonnée augmente de 1 et la taille de la région désordonnée diminue de 1. La boucle principale va de 1 à N-1. À la jième itération, l'élément [i] est inséré à la position correcte dans la région ordonnée. Cela se fait en déplaçant tous les éléments de la région ordonnée qui sont supérieurs à [i] une position vers la droite. [i] est inséré dans l'espace entre les éléments inférieurs à [i] et ceux supérieurs à [i]. Code C++
void SortAlgo::insertionSort(int data, int lenD) ( int key = 0; int i = 0; for (int j = 1;j Code C++
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = nouvel int; int * R = nouvel int; pour ( int je = 0; je Le tri rapide utilise un algorithme diviser pour régner. Cela commence par diviser le tableau d’origine en deux régions. Ces pièces se trouvent à gauche et à droite de l'élément marqué, appelé support. A la fin du processus, une partie contiendra des éléments plus petits que la référence, et l'autre partie contiendra des éléments plus grands que la référence. Code C++
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = nouvel int ; int * R = nouvel int ; pivot = données; pour (i=0;i Il existe un assez grand nombre d'algorithmes de tri, dont beaucoup sont très spécifiques et ont été développés pour résoudre un éventail restreint de problèmes et travailler avec des types de données spécifiques. Mais parmi toute cette diversité, l’algorithme le plus simple est à juste titre le tri à bulles, qui peut être implémenté dans n’importe quel langage de programmation. Malgré sa simplicité, il sous-tend de nombreux algorithmes plutôt complexes. Un autre avantage tout aussi important est sa simplicité et, par conséquent, il peut être mémorisé et mis en œuvre immédiatement, sans avoir de documentation supplémentaire sous les yeux. Contrairement à un programme informatique, le tri ne sera pas difficile pour vous, car vous êtes capable de voir l'ensemble du tableau et de déterminer immédiatement quel héros doit être déplacé où pour que le tri par hauteur soit effectué avec succès. Vous avez probablement déjà deviné que pour trier cette structure de données par ordre croissant, il suffit d'échanger les places de Hulk et d'Iron Man : Après avoir parcouru toute la liste en un seul passage avec un tel algorithme, le tri ne sera pas complètement terminé. Mais d’un autre côté, l’élément le plus grand de la liste sera déplacé à l’extrême droite. Cela se produira toujours, car dès que vous trouverez le plus grand élément, vous changerez constamment de place jusqu'à ce que vous le déplaciez jusqu'au bout. Autrement dit, dès que le programme « trouvera » Hulk dans le tableau, il le déplacera plus loin à la toute fin de la liste : C'est pourquoi cet algorithme est appelé tri à bulles, car à la suite de son fonctionnement, le plus grand élément de la liste sera tout en haut du tableau et tous les éléments plus petits seront décalés d'une position vers la gauche : Pour terminer le tri, vous devrez revenir au début du tableau et répéter à nouveau les cinq étapes décrites ci-dessus, en vous déplaçant à nouveau de gauche à droite, en comparant et en déplaçant les éléments si nécessaire. Mais cette fois, vous devez arrêter l'algorithme un élément avant la fin du tableau, car nous savons déjà que le plus grand élément (Hulk) est absolument à l'extrême droite : Le programme doit donc avoir deux boucles. Pour plus de clarté, avant de passer à la révision du code du programme, vous pouvez voir une visualisation du fonctionnement du tri à bulles sur ce lien : Visualisation du fonctionnement du tri à bulles // affiche à nouveau la liste triée ) ) Malgré les commentaires détaillés dans le code, nous fournirons une description de certaines des méthodes présentées dans le programme. Les méthodes clés qui effectuent le travail principal du programme sont écrites dans la classe ArrayBubble. La classe contient un constructeur et plusieurs méthodes : into – méthode d'insertion d'éléments dans un tableau ; La vitesse de l’algorithme dépend non seulement du nombre de passes, mais également du nombre de permutations à effectuer. Pour les données aléatoires, le nombre de permutations est en moyenne de (N ^ 2) / 4, soit environ la moitié du nombre de passes. Cependant, dans le pire des cas, le nombre de permutations peut également être N^2/2 - c'est le cas si les données sont initialement triées dans l'ordre inverse. Bien qu'il s'agisse d'un algorithme de tri plutôt lent, il est très important de connaître et de comprendre son fonctionnement et, comme mentionné précédemment, il constitue la base d'algorithmes plus complexes. Bon Dieu ! Les avantages pratiques de ces méthodes ne sont pas si grands, et de nombreux utilisateurs de Habra ont vécu tout cela en première année. Par conséquent, l'article s'adresse à ceux qui viennent de s'intéresser à la théorie des algorithmes et font leurs premiers pas dans cette direction. image : bulles Aujourd'hui, nous allons parler du plus simple tris d'échange. Si quelqu'un est intéressé, je dirai qu'il existe d'autres cours - tri par sélection, tri par insertion, tri par fusion, tri par répartition, sortes hybrides Et tris parallèles. D'ailleurs, il y a aussi tris ésotériques. Il s'agit de divers pseudo-algorithmes faux, fondamentalement irréalisables, comiques et autres, sur lesquels j'écrirai quelques articles dans le hub « IT Humour ». Mais cela n’a rien à voir avec le cours d’aujourd’hui ; nous ne nous intéressons maintenant qu’aux simples tris d’échanges. Il existe également de nombreux tris d'échange eux-mêmes (j'en connais plus d'une douzaine), nous allons donc examiner ce qu'on appelle tri à bulles et quelques autres qui y sont étroitement liés. Je vous préviens à l'avance que presque toutes les méthodes ci-dessus sont très lentes et qu'il n'y aura pas d'analyse approfondie de leur complexité temporelle. Certains sont plus rapides, d'autres plus lents, mais grosso modo, on peut dire qu'en moyenne Ô(n°2). De plus, je ne vois aucune raison d'encombrer l'article avec des implémentations dans des langages de programmation. Les personnes intéressées peuvent facilement trouver des exemples de code sur Rosetta, Wikipedia ou ailleurs. Mais revenons au tri des échanges. L'ordre se produit à la suite d'itérations séquentielles répétées du tableau et de comparaison de paires d'éléments les uns avec les autres. Si les éléments comparés ne sont pas triés les uns par rapport aux autres, nous les échangeons. La seule question est de savoir comment contourner exactement le tableau et sur quelle base sélectionner les paires à comparer. Commençons non pas par le tri à bulles standard, mais par un algorithme appelé... « N’importe quel imbécile peut faire cela », direz-vous, et vous aurez tout à fait raison. C’est pour cela que le tri est qualifié de « stupide ». Dans cette conférence, nous améliorerons et modifierons constamment cette méthode. Maintenant, il a des difficultés temporaires Ô(n°3), après avoir apporté une correction, nous l'amenerons déjà à Ô(n°2), puis on accélérera un peu plus, puis un peu plus, et à la fin on obtiendra Ô(n enregistrer n) – et ce ne sera pas du tout un « Tri rapide » ! Apportons une seule amélioration au tri stupide. Après avoir découvert deux éléments adjacents non triés lors du passage et les avoir échangés, nous ne reviendrons pas au début du tableau, mais continuerons calmement à le parcourir jusqu'à la toute fin. Dans ce cas, nous n’avons devant nous rien d’autre que le bien connu... Si nous poussons non seulement les maximums jusqu'au bout, mais aussi les minimums jusqu'au début, alors nous réussissons... Le tri par shaker fonctionne un peu plus rapidement que le tri par bulles, puisque les maximums et les minimums migrent alternativement à travers le tableau dans les directions requises. Les améliorations, comme on dit, sont évidentes. Comme vous pouvez le constater, si vous abordez le processus d'énumération de manière créative, le déplacement des éléments lourds (légers) vers les extrémités du tableau se produit plus rapidement. Les artisans ont donc proposé une autre « feuille de route » non standard pour contourner la liste. Dans une « bulle » régulière, à chaque passage nous pressons systématiquement le maximum actuel jusqu'à la fin du tableau. Si vous sautez le long des indices pairs et impairs, alors tous les éléments plus ou moins grands du tableau sont simultanément poussés vers la droite d'une position en une seule fois. Cela fonctionne plus rapidement de cette façon. Regardons le dernier redécoré* Pour Sortuvannya bulbashka** - Tri par peigne***. Cette méthode s'organise très rapidement, Ô(n°2) est sa pire difficulté. En moyenne, au fil du temps, nous avons Ô(n enregistrer n), et le meilleur, vous n'y croirez même pas, Ô(n). Autrement dit, un concurrent très digne de toutes sortes de « tris rapides » et ce, remarquez, sans recourir à la récursivité. Cependant, j'ai promis qu'aujourd'hui nous n'aborderions pas les vitesses de croisière, je vais donc arrêter de parler et passer directement à l'algorithme. image : tortue coupable Il est préférable de prendre l'écart initial entre les éléments comparés non pas n'importe lequel, mais en tenant compte d'une valeur particulière appelée facteur réducteur, dont la valeur optimale est d'environ 1,247. Premièrement, la distance entre les éléments est égale à la taille du tableau divisée par facteur de réduction(le résultat est bien entendu arrondi à l’entier le plus proche). Ensuite, après avoir parcouru le tableau avec ce pas, nous divisons à nouveau le pas par facteur de réduction et parcourez à nouveau la liste. Cela continue jusqu'à ce que la différence d'indice atteigne un. Dans ce cas, le tableau est trié avec une bulle régulière. La valeur optimale a été établie expérimentalement et théoriquement facteur de réduction: Lorsque cette méthode a été inventée, peu de gens y prêtaient attention au tournant des années 70 et 80. Une décennie plus tard, alors que la programmation n'était plus l'apanage des scientifiques et des ingénieurs d'IBM, mais gagnait déjà rapidement en popularité, la méthode a été redécouverte, étudiée et popularisée en 1991 par Stephen Lacy et Richard Box. C’est en fait tout ce que je voulais vous dire sur le tri à bulles et autres. - Remarques * raccourci ( ukrainien) - amélioration Le tri à bulles compare les éléments adjacents et échange leurs places si l'élément suivant est plus petit que le précédent. Plusieurs passages dans les données sont nécessaires. Lors du premier passage, les deux premiers éléments du tableau sont comparés. S'ils ne sont pas en ordre, ils sont échangés puis les éléments de la paire suivante sont comparés. Dans les mêmes conditions, ils changent également de place. Ainsi, le tri a lieu à chaque cycle jusqu'à ce que la fin du tableau soit atteinte.
Tri par fusion
Tri rapide
Introduction
L'ensemble de l'Internet moderne se compose d'un grand nombre de types différents de structures de données collectées dans des bases de données. Ils stockent toutes sortes d'informations, depuis les données personnelles des utilisateurs jusqu'au noyau sémantique des systèmes automatisés hautement intelligents. Il va sans dire que le tri des données joue un rôle extrêmement important dans cette énorme quantité d’informations structurées. Le tri peut être une étape obligatoire avant de rechercher une information dans la base de données, et la connaissance des algorithmes de tri joue un rôle extrêmement important dans la programmation. Il existe un assez grand nombre d'algorithmes de tri, dont beaucoup sont très spécifiques et ont été développés pour résoudre un éventail restreint de problèmes et travailler avec des types de données spécifiques. Mais parmi toute cette variété, l'algorithme le plus simple est à juste titre tri à bulles, qui peut être implémenté dans n’importe quel langage de programmation. Malgré sa simplicité, il sous-tend de nombreux algorithmes plutôt complexes. Un autre avantage tout aussi important est sa simplicité et, par conséquent, il peut être mémorisé et mis en œuvre immédiatement, sans avoir de documentation supplémentaire sous les yeux. Trier les yeux des machines et les yeux humains
Imaginons que vous deviez trier 5 colonnes de hauteurs différentes par ordre croissant. Ces colonnes peuvent contenir n'importe quelle information (cours des actions, capacité du canal de communication, etc.), vous pouvez présenter certaines de vos propres versions de cette tâche pour la rendre plus claire. Eh bien, à titre d'exemple, nous allons trier les Avengers par hauteur : Fait!
Et cela terminera le tri avec succès. Cependant, l'ordinateur, contrairement à vous, est quelque peu stupide et ne voit pas l'ensemble de la structure des données dans son ensemble. Son programme de contrôle ne peut comparer que deux valeurs à la fois. Pour résoudre ce problème, elle doit mettre deux nombres en mémoire et effectuer une opération de comparaison sur ceux-ci, puis passer à une autre paire de nombres, et ainsi de suite jusqu'à ce que toutes les données aient été analysées. Ainsi, tout algorithme de tri peut être très simplifié sous la forme de trois étapes :
Différents algorithmes peuvent effectuer ces opérations de différentes manières, mais nous allons maintenant examiner le fonctionnement du tri à bulles. Algorithme de tri à bulles
Le tri des bulles est considéré comme le plus simple, mais avant de décrire cet algorithme, imaginons comment vous trieriez les Avengers par hauteur si vous pouviez, comme une machine, comparer seulement deux héros entre eux sur une période de temps. Très probablement, vous feriez ce qui suit (de la manière la plus optimale) : Implémentation du tri à bulles en Java
Pour démontrer comment fonctionne le tri en Java, voici le code du programme :
Vous pouvez consulter le code ci-dessous et même le télécharger dans votre IDE IntelliJ préféré. Il sera analysé ci-dessous : class ArrayBubble ( private long a; //lien vers le tableauéléments int privés ; //nombre d'éléments dans le tableau public ArrayBubble (int max) ( //constructeur de classe a = nouveau long[max] ; //création d'un tableau de taille maxéléments = 0 ; //une fois créé, le tableau contient 0 élément) vide public dans (valeur longue) ( // méthode d'insertion d'un élément dans un tableau a[ éléments] = valeur ; //insérer la valeur dans le tableau aéléments++ ; //la taille du tableau augmente) imprimante vide public () ( //méthode pour afficher un tableau sur la console pour (int je = 0 ; je<
elems;
i++
)
{
//pour chaque élément du tableau Système. dehors. imprimer (a[ i] + " " ) ; //sortie vers la console Système. dehors. println(""); //à partir d'une nouvelle ligne) Système. dehors. println("----Fin de sortie du tableau----" ) ;) private void toSwap (int premier, int deuxième) ( //la méthode échange quelques nombres dans le tableau mannequin long = a[ premier] ; // met le premier élément dans une variable temporaire a[ premier] = a[ seconde] ; //à la place du premier on met le deuxième élément a[seconde] = factice ;<
out;
in++
)
{
//au lieu du deuxième élément, nous écrivons le premier depuis la mémoire temporaire) public void bubbleSorter () ( pour (int out = elems - 1 ; out > //Boucle intérieure if (a[ in] > a[ in + 1 ] ) toSwap (in, in + 1 ) ; //remplit le tableau tableau. dans(300); tableau. dans(184); tableau. dans(191); tableau. dans(174); tableau. imprimante(); //sortie des éléments avant le tri tableau. bubbleSorter();
si (a[ in] > a[ in + 1 ] ) //Si l'ordre des éléments est rompu toSwap (dans, dans + 1 ) ; // appelle une méthode qui échange de place Ici, vous devez faire attention à deux compteurs : externe out et interne in. Compteur de sortie externe
commence à parcourir les valeurs à partir de la fin du tableau et diminue progressivement de une à chaque nouveau passage. La variable out est décalée davantage vers la gauche à chaque nouveau passage, afin de ne pas affecter les valeurs déjà triées sur le côté droit du tableau. Compteur interne Ainsi, lors du tri, l'algorithme effectue des comparaisons d'environ 0,5x(N^2). Pour N = 5, le nombre de comparaisons sera d'environ 10, pour N = 10 le nombre de comparaisons passera à 45. Ainsi, à mesure que le nombre d'éléments augmente, la complexité du tri augmente considérablement :
Tout le monde sait très bien que parmi la classe des échanges, la méthode la plus rapide est ce qu'on appelle tri rapide. Des thèses sont écrites à ce sujet, de nombreux articles sur Habré lui sont consacrés et des algorithmes hybrides complexes sont inventés sur cette base. Mais aujourd'hui nous ne parlerons pas tri rapide, et sur une autre méthode d'échange - le bon vieux tri à bulles et ses améliorations, modifications, mutations et variations. Type stupide
Le tri est vraiment stupide. Nous parcourons le tableau de gauche à droite et comparons les voisins en cours de route. Si nous rencontrons une paire d’éléments non triés mutuellement, nous les échangeons et revenons à la case départ, c’est-à-dire au tout début. Nous parcourons et vérifions à nouveau le tableau, si nous rencontrons à nouveau une paire « incorrecte » d'éléments voisins, alors nous changeons de place et tout recommence. On continue jusqu'à ce que le tableau soit petit à petit trié. Tri à bulles
Ou tri par échanges simples. Un classique immortel du genre. Le principe de fonctionnement est simple : on parcourt le tableau du début à la fin, en échangeant simultanément les éléments voisins non triés. À la suite du premier passage, l'élément maximum « flottera » jusqu'à la dernière place. Maintenant, nous parcourons à nouveau la partie non triée du tableau (du premier élément à l'avant-dernier) et modifions les voisins non triés en cours de route. Le deuxième plus grand élément occupera l’avant-dernière place. En continuant dans le même esprit, nous parcourrons la partie non triée de plus en plus réduite du tableau, poussant les maxima trouvés jusqu'au bout. Tri au shaker
Elle est la même trier aléatoirement, elle est pareille tri des cocktails. Le processus commence comme dans une « bulle » : on fait sortir le maximum jusqu'au fond. Après cela, nous tournons autour de 180 0 et partons dans la direction opposée, en revenant au début non pas au maximum, mais au minimum. Après avoir trié le premier et le dernier élément du tableau, nous effectuons à nouveau un saut périlleux. Après plusieurs allers-retours, nous finissons par mettre fin au processus et nous retrouvons au milieu de la liste. Tri pair-impair
Cette fois, nous ne nous précipiterons pas à travers le tableau, mais reviendrons à nouveau à l'idée d'une marche systématique de gauche à droite, mais nous ne ferons qu'un pas plus large. Lors du premier passage, les éléments de clé impaire sont comparés à leurs voisins basés aux places paires (le 1er est comparé au 2ème, puis le 3ème au 4ème, le 5ème au 6ème, et ainsi de suite). Ensuite, au contraire, nous comparons/modifions les éléments « pairs » avec des éléments « impairs ». Puis encore « impair-pair », puis encore « pair-impair ». Le processus s'arrête lorsque, après deux passages consécutifs dans la matrice (« impair-pair » et « pair-impair »), aucun échange n'a eu lieu. Alors, ils ont réglé le problème. C'est la faute des tortues
Un peu de contexte. En 1980, Włodzimierz Dobosiewicz expliquait pourquoi le tri à bulles et ses dérivés fonctionnent si lentement. C'est à cause des tortues. Les « tortues » sont de petits éléments situés à la fin de la liste. Comme vous l'avez peut-être remarqué, les tris à bulles se concentrent sur les « lapins » (à ne pas confondre avec les « lapins » de Babushkin) – des éléments de grande valeur au début de la liste. Ils avancent très vite vers la ligne d’arrivée. Mais les reptiles lents rampent jusqu'au début à contrecœur. Vous pouvez personnaliser la tortilla en utilisant peignes. Tri au peigne
Dans « bulle », « shaker » et « impair-pair », lors d'une itération dans un tableau, les éléments voisins sont comparés. L'idée principale du « peigne » est de prendre dans un premier temps une distance suffisamment grande entre les éléments comparés et, au fur et à mesure que le tableau est ordonné, de réduire cette distance au minimum. De cette façon, nous peignons en quelque sorte le tableau, le lissant progressivement en brins de plus en plus nets.
** Triés par ampoule ( ukrainien) – Tri à bulles
*** Tri par peigne ( ukrainien) – Tri au peigne