Tri du drapeau américain

Pour comprendre le principe de fonctionnement de ce tri «multibande», il est plus simple de commencer avec l'exemple d'un drapeau à trois bandes. Et afin de gérer facilement le drapeau tricolore, il est préférable de voir d'abord comment cela fonctionne avec l'exemple bicolore. Et pour faire face aux deux couleurs ...

Cet article a été écrit avec le soutien d'EDISON.

Nous sommes engagés dans le portage et la migration de logiciels , ainsi que dans le développement d'applications mobiles Android et iOS .

Nous aimons la théorie des algorithmes! ;-)

Drapeau bicolore

Tout d'abord, considérons le cas où les nombres dans le tableau trié sont distribués en seulement deux bits. Pour simplifier, nous supposons que nous avons un tableau de zéros (ordre faible) et de uns (ordre élevé).

Ainsi, nous n'avons que deux «bandes»: dans l'une nous déplacerons les bits les moins significatifs (zéros), et dans l'autre les bits les plus élevés (unités). Tout drapeau bicolore fera l'objet d'une démonstration. Par exemple, le drapeau de l'Ukraine.



Que se passe-t-il ici? Puisqu'au premier stade, on ne sait pas combien de zéros et combien d'unités nous avons, il n'est donc pas clair dans quelles tailles chacune des «bandes» se retrouvera. Par conséquent, nous mettons deux pointeurs sur les clés du tableau. Pour l'ordre inférieur, le pointeur est placé au début du tableau, pour l'ordre élevé à la fin. Ensuite, nous faisons un seul passage à travers le tableau de gauche à droite et regardons chaque élément de bit.

Si pendant le passage un élément est égal à l'ordre le plus élevé, alors le deuxième pointeur nous indique où transférer cet élément (on fait un échange). Le pointeur pour insérer l'élément suivant se déplace vers la gauche, la "bande" du chiffre supérieur s'est développée.

S'il est égal au chiffre le moins significatif, nous déplaçons le pointeur correspondant d'un élément vers la droite. Comme nous n'avons que deux chiffres, il n'est pas nécessaire de transférer l'élément, il est déjà à sa place. La «bande» pour la catégorie plus jeune s'est naturellement élargie.

En conséquence, deux pointeurs se déplaçant l'un vers l'autre entreront en collision en un point, et les décharges seront ordonnées dans leurs «bandes». Dans le même temps, vous n'aurez pas besoin de traverser l'ensemble du tableau - lorsque les pointeurs se rencontrent quelque part au milieu, l'algorithme fera son travail.

Le problème du drapeau national néerlandais :: Le problème du drapeau national néerlandais

Nous compliquons légèrement la tâche, considérons non pas deux chiffres, mais trois. Faisons en sorte que les éléments du tableau appartiennent aux chiffres les plus bas (zéros), moyens (unités) et supérieurs (deux).

Pour démonstration, nous prenons le drapeau à trois voies rouge-blanc-bleu de la France, le Luxembourg de la Russie, le Schleswig-Goldstein des Pays - Bas. Pourquoi exactement le drapeau des Pays-Bas? Parce que Edsger Dijkstra dans ses conférences sur l'exemple de ce drapeau a examiné l'algorithme correspondant, qui a été appelé "la tâche du drapeau national néerlandais".



Comme vous pouvez le voir, il n'y a rien de particulièrement nouveau. Chaque catégorie a son propre pointeur. Initialement, les étiquettes pour le junior et le milieu prennent les positions de départ au début du tableau et se déplacent vers la droite lorsque l'élément correspondant est rencontré. Le pointeur pour l'ordre supérieur est le premier à la fin du tableau et se déplace vers la gauche.

Le passage dans le tableau sera également incomplet en fait, si les bits sont répartis plus ou moins uniformément, alors l'algorithme passera par 2/3 du tableau avant de disperser tous les éléments dans ses «bandes».

Tri par drapeau américain :: Tri par drapeau américain

Maintenant, dans nos explications, nous pouvons passer au drapeau américain multibande.

Lorsque nous n'avons pas deux, pas trois, mais un nombre quelconque de chiffres, nous fixons où chaque chiffre doit commencer (sa «bande») et redessinons les éléments dans leurs «bandes».

Dans cet algorithme, les nombres ne sont généralement pas considérés comme décimaux, mais avec une profondeur de bits différente, le plus souvent une puissance de deux. Souvent, le nombre 256 est pris comme base pour la profondeur de bits (un peu moins souvent que 128), ce qui vous permet d'adapter efficacement le tri pour organiser les chaînes. Pour les nombres pour la profondeur de bits, il est plus pratique de prendre de petits 2 ⁿ (2, 4, 16, etc.), ce qui vous permet de comparer en décalant par bits, au lieu d'augmenter à une puissance lors de la comparaison des nombres décimaux.

L'animation montre un exemple de profondeur de bits avec base 16:

1. Lors de la première passe - recherchez le maximum afin de déterminer le nombre maximum de bits parmi les éléments du tableau (afin d'extraire correctement les bits déterminés à partir du compte des éléments).
2. Ensuite, un traitement récursif se produit. Lorsqu'il est appelé, les limites du sous-tableau et le bit traité actuel sont indiqués. Au premier appel, le tableau entier est un sous-tableau; le tout premier bit à gauche est pris.
3. Parmi les éléments du sous-tableau, un calcul initial est effectué - combien de fois chaque chiffre apparaît dans la catégorie actuelle. Ce comptage vous permet de déterminer la localisation de ces chiffres des chiffres (c'est-à-dire, les limites et l'emplacement de la «bande» vers laquelle vous souhaitez déplacer les éléments qui ont le chiffre suivant dans un chiffre particulier sont connus). En fait, les localisations sont des pointeurs vers des «bandes» où les éléments correspondants doivent être déplacés.
4. Conformément aux pointeurs de localisation, un échange a lieu sur place - le chiffre dans la catégorie indique où l'article doit être envoyé, un autre élément avec lequel l'échange a eu lieu prend sa place. Cette clause est exécutée jusqu'à ce que, lors du prochain échange, un élément arrivant d'un autre endroit ne soit pas à sa place (vous pouvez alors passer à l'élément suivant du sous-tableau et exécuter de la même manière cette clause pour lui).
5. Après que, à la suite des échanges, les éléments ont été redistribués en blocs par des nombres dans le chiffre suivant, une récursivité a lieu - le même algorithme est appliqué à chaque bloc comme un sous-tableau, le suivant est pris comme le chiffre actuel.

Dans l'article sur le comptage des tris avec une distribution approximative, il existe un algorithme visuellement très similaire - le tri par approximation . Là, nous avons compté le nombre de fois où chaque numéro du tableau s'est produit - et redistribué les éléments en fonction des localisations obtenues. Ici, nous comptons le nombre de fois où chaque chiffre de la catégorie se produit pour les éléments du sous-tableau - et nous redistribuons également les éléments du sous-tableau en fonction des localisations obtenues. Si l'approximation est une sorte de tri de comptage, alors «américain» est un tri de bits de comptage.

Sort Ska :: Sort Ska

Le programmeur allemand, Malte Skarupke, a annoncé qu'il a développé un nouvel algorithme de tri, qui est un «drapeau américain» radicalement amélioré et surpasse std :: sort en moyenne 2 fois (std :: sort - un algorithme également connu sous le nom de tri introspectif - un hybride de tri rapide et de tri par tas ).

1. Le tableau est trié récursivement, au premier niveau de récursivité, l'ensemble du tableau est pris comme un sous-tableau.
2. Si le sous-tableau a moins de 128 éléments, std :: sort est appelé pour cela.
3. Si le sous-tableau contient de 128 à 1024 éléments, alors le tri du drapeau américain est appelé pour cela.
4. S'il y a plus de 1024 éléments dans un sous-tableau, le tri ska est appelé pour cela.
5. De plus, pour éviter le pire des cas, si l'imbrication récursive est trop grande (plus de 16 niveaux), l'algorithme passe à std :: sort , même s'il y a plus de 128 éléments dans le sous-tableau.

Apparemment, c'est un algorithme très efficace et en même temps extrêmement complexe - la mise en œuvre de son auteur prend près d'un mille et demi de lignes. Peut-être envisagerons-nous un jour ce tri, maintenant nous n'y entrerons pas. Les personnes intéressées peuvent cliquer sur les liens ci-dessous.

Les références

Problème du drapeau national néerlandais , type de drapeau américain

Tri Ska: J'ai écrit un algorithme de tri plus rapide ( partie 1 , partie 2 ) Code Github

Articles de série:

• Application Excel AlgoLab.xlsm
• Exchange Sorts
• Tri d'insertion
• Trier par sélection
• Fusionner les tris
• Trier par distribution
  • Compter les tris avec une distribution approximative
  • Tri du drapeau américain
  • Arborescence des suffixes dans le tri au niveau du bit
  • Comparaison des tri par distribution
• Tri hybride

Dans l'application AlgoLab Excel, le tri par un drapeau bicolore (trie les zéros et les uns), un drapeau tricolore (trie les zéros, les uns et les égalités), le tri par le drapeau américain est apparu. Pour trier le «drapeau américain», vous pouvez (dans un commentaire sur la cellule avec le nom de l'algorithme) spécifier le système numérique pour la distribution - la valeur par défaut est hexadécimale.