Quel est cet étrange algorithme de tri ?

Question

Quelques réponse avait à l'origine cet algorithme de tri :

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]

Notez que les deux i y j sur toute la gamme et donc j peut être à la fois plus grand et plus petit que i Il peut donc faire des paires dans le bon et le mauvais ordre (et en fait, il peut faire des paires dans le bon et le mauvais ordre). hace faire les deux !). J'ai pensé que c'était une erreur (et l'auteur l'a dit plus tard) et que cela brouillerait le tableau, mais il semble que le tri soit correct. La raison n'est pas évidente, cependant. Mais le código simplicité (passage à la gamme complète, et pas de +1 comme dans "bubble sort") le rend intéressant.

Est-il correct ? Si oui, pourquoi cela fonctionne-t-il ? Et a-t-il un nom ?

Implémentation de Python avec tests :

from random import shuffle

for _ in range(3):
    n = 20
    A = list(range(n))
    shuffle(A)
    print('before:', A)

    for i in range(n):
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]

    print('after: ', A, '\n')

Exemple de sortie ( Essayez-le en ligne ! ) :

before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

Edit : Quelqu'un a signalé une très belle marque de nouveau papier sur cet algorithme. Juste pour clarifier : nous n'avons aucun lien, c'est une coïncidence. Pour autant que je sache, c'était soumis vers arXiv antes de cette réponse qui a suscité ma question et publié sur par arXiv après ma question.

Answer 1

C'est un tri d'insertion correct mais étrange et inefficace.

Visualisons-le d'abord en imprimant A après chaque itération complète de la boucle interne. Exemple :

before: [1, 12, 13, 8, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [19, 1, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 19, 12, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 12, 19, 8, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 19, 13, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 19, 15, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 19, 18, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 18, 19, 16, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 8, 12, 13, 15, 16, 18, 19, 7, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 15, 16, 18, 19, 14, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 3, 2, 9, 5, 4, 0, 10, 17]
        [1, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 2, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 11, 12, 13, 14, 15, 16, 18, 19, 9, 5, 4, 0, 10, 17]
        [1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 5, 4, 0, 10, 17]
        [1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 4, 0, 10, 17]
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 0, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 18, 19, 10, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 17]
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

Graphiquement, mais mis à jour après chaque échange, la barre rouge indique l'indice i ( code ici ) :

Pour i = 0 en fait, il hace brouille plus ou moins la liste, mais il apporte la plus grande valeur à A[0] (ou un la plus grande valeur, s'il y en a plusieurs). À partir de ce moment, cette valeur servira de sentinelle.

En raison de ce désordre initial, il serait difficile (et inutile) d'énoncer un invariant basé sur l'état initial du tableau. Au lieu de cela, définissons A0 pour être l'état du tableau après la boucle externe de i = 0 :

Invariant : Après la boucle externe pour certains i :

• La valeur globale la plus importante se situe à A[i]
• A[0 to i] contiennent A0[0 to i] dans un ordre trié.

Preuve par induction :

Cas de base i = 0 est trivial.

Cas i > 0 : Avant la boucle extérieure avec ceci i nous avons la sentinelle (la plus grande valeur globale) à A[i-1] y A[0 to i-1] contient A0[0 to i-1] dans l'ordre trié. Maintenant la boucle interne passe sur tous les éléments et nous échangeons A[i] y A[j] chaque fois que A[j] > A[i] . Examinons à nouveau un exemple de ligne ci-dessus :

[1, 7, 8, 12, 13, 15, 16, 18, 19, 11, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

El 19 est la sentinelle, la partie jusqu'à elle est triée, et i est l'indice du 11. Que se passe-t-il lorsque nous utilisons j de 0 à la fin ? Les valeurs 1, 7 et 8 ne sont pas plus grandes que le 11, donc rien ne se passe. Le 12 est plus grand, donc il sera échangé avec le 11 :

[1, 7, 8, 11, 13, 15, 16, 18, 19, 12, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

Maintenant, c'est le 12 qui est à l'index. i . Ensuite, il est comparé à 13. Comme 13 est plus grand, ils sont échangés :

[1, 7, 8, 11, 12, 15, 16, 18, 19, 13, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

Cela continue, toujours en échangeant, jusqu'à ce que nous échangions avec la sentinelle :

[1, 7, 8, 11, 12, 13, 16, 18, 19, 15, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 18, 19, 16, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 19, 18, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]
[1, 7, 8, 11, 12, 13, 15, 16, 18, 19, 6, 14, 3, 2, 9, 5, 4, 0, 10, 17]

A ce stade, l'insertion du 11 dans la partie triée est terminée. Et la sentinelle s'est déplacée vers l'index i où il empêche ensuite tout autre échange pendant la boucle interne (c'est-à-dire tout échange avec des éléments situés plus à droite). En général, pour une nouvelle valeur (comme le 11), les nombres plus petits que lui restent où ils sont, et les nombres plus grands que lui sont échangés et replacés à un endroit vers la droite.

Quand nous aurons terminé nous avons eu la boucle extérieure avec i = n-1 . L'invariant nous dit alors que A[0 to n-1] contiennent A0[0 to n-1] dans l'ordre trié. C'est-à-dire que le tableau finit par être correctement trié.

Pourquoi je l'appelle une sorte d'insertion : Après le désordre i = 0 Si vous regardez le tableau après chaque boucle interne complète, il est impossible de le distinguer du tri par insertion (voir mon gros bloc de visualisation en haut). Par exemple, le 11 a simplement été inséré dans la partie triée à sa gauche. Ce qui diffère, c'est la façon dont l'insertion se fait. Le tri par insertion normal fait "bouillonner" le 11 vers la gauche jusqu'à sa place correcte, sans même regarder les nombres encore plus petits. Cet algorithme recherche plutôt le point d'insertion, en commençant tout à gauche, puis insère le 11 à cet endroit et fait "bouillonner" les plus grands nombres jusqu'à la sentinelle. vers la droite . Et il continue ensuite avec d'autres comparaisons infructueuses contre la sentinelle qui est maintenant assise à A[i] .

Mise à jour : smusamashah a partagé leur fantastique outil de visualisation ce qui nous permet de comparer cet algorithme avec les autres algorithmes dont il se réclame. Cochez les cases à droite pour Bubble Sort, Insertion Sort et Selection Sort, puis cliquez sur Start. Vous verrez à nouveau que notre tri ressemble beaucoup au tri par insertion, et pas du tout aux autres. Et si vous faites plutôt Tri d'échange (malheureusement non inclus), vous verrez que cela ressemble plus à un tri par sélection (mais plus lent car il y a plus de permutations et l'outil montre toutes les permutations).

Answer 2

Pour prouver que c'est correct, il faut trouver une sorte d'invariant. Quelque chose qui est vrai à chaque passage de la boucle.

En y regardant de plus près, après le tout premier passage de la boucle interne, la le plus grand l'élément de la liste se trouvera effectivement dans le premièrement position.

Maintenant, dans le deuxième passage de la boucle interne, i = 1 et la toute première comparaison se fait entre i = 1 y j = 0 . Ainsi, l'élément le plus grand était en position 0, et après cette comparaison, il sera échangé en position 1.

En général, il n'est donc pas difficile de voir qu'après chaque étape de la boucle externe, l'élément le plus grand se sera déplacé d'une unité vers la droite. Ainsi, après toutes les étapes, nous savons qu'au moins le plus grand élément sera à la bonne position.

Qu'en est-il des autres éléments ? Disons que le deuxième élément le plus important se trouve à la position i de la boucle de courant. Nous savons que le le plus grand L'élément se trouve à la position i-1 selon la discussion précédente. Compteur j commence à 0. Donc maintenant nous cherchons le premier A[j] de telle sorte que c'est A[j] > A[i] . Eh bien, le A[i] est le deuxième plus grand élément, donc la première fois que cela se produit est quand j = i-1 au premier élément le plus grand. Ainsi, ils sont adjacents et sont échangés et sont maintenant dans le "bon" ordre. Maintenant A[i] pointe à nouveau vers l'élément le plus grand, et donc pour le reste de la boucle interne, aucun autre échange n'est effectué.

Donc on peut dire : Une fois que l'index de la boucle externe a dépassé l'emplacement du deuxième plus grand élément, le deuxième et le premier plus grand élément seront dans le bon ordre. Ils vont maintenant glisser ensemble, à chaque itération de la boucle externe, de sorte que nous savons qu'à la fin de l'algorithme, le premier et le deuxième élément le plus grand seront dans la bonne position.

Qu'en est-il du troisième plus grand élément ? Eh bien, nous pouvons utiliser la même logique à nouveau : Une fois que le compteur de la boucle externe i est à la position du troisième élément le plus grand, il sera échangé de façon à ce qu'il soit juste en dessous du deuxième élément le plus grand (si nous l'avons déjà trouvé !) ou sinon juste en dessous du premier élément le plus grand.

Ah. Et voilà, nous avons maintenant notre invariant : Après k itérations de la boucle externe, la séquence d'éléments de longueur k, se terminant à la position k-1 seront classés par ordre d'importance :

Après la 1ère itération, la séquence de longueur 1, en position 0, sera dans l'ordre correct. C'est trivial.

Après la 2ème itération, nous savons que le plus grand élément est en position 1, donc évidemment la séquence A[0] , A[1] est dans le bon ordre.

Maintenant, supposons que nous sommes à l'étape k donc tous les éléments jusqu'à la position k-1 sera en ordre. Maintenant i = k et nous itérons sur j . Il s'agit essentiellement de trouver la position à laquelle le nouvel élément doit être inséré dans la séquence triée existante afin qu'il soit correctement trié. Une fois que cela se produit, les autres éléments "remontent" jusqu'à ce que le plus grand élément se trouve à la position i = k et aucun autre échange ne se produit.

Ainsi, à la fin de l'étape N tous les éléments jusqu'à la position N-1 sont dans le bon ordre, qed.

Answer 3

Je ne suis pas trop sûr que l'algorithme ci-dessus ait un nom explicite, mais d'après une analyse rapide des résultats, il ressemble à une implémentation inefficace de tri par insertion où la région triée est constituée d'indices 0 a i inclusif après avoir exécuté l'itération i .

Débogage de l'impression

Cela peut être vérifié par inspection si nous plaçons une instruction print juste après la boucle interne :

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]
    print(A) <- add here

A = [5, 5, 0, 9, 2]
0.  [9, 5, 0, 5, 2]
1.  [5, 9, 0, 5, 2]
2.  [0, 5, 9, 5, 2]
3.  [0, 5, 5, 9, 2]
4.  [0, 2, 5, 5, 9]

Preuve

Nous pouvons prouver ceci par induction sur i la boucle externe. Après avoir exécuté l'itération i , indices 0 to i y compris A o A[0:i] est trié, avec A[i] = max(A) .

Cas de base : i = 0

Pour i = 0 le maximum de A sera stocké à l'index 0 . C'est ce qui ressort de l'inspection de l'algorithme.

Étape inductive : i > 0

Notre hypothèse inductive est que A[0:i-1] est trié et que A[i - 1] = max(A) . Ce qui se passe dans l'itération i ? En gros, nous déterminons où A[i] doit être placé dans la région triée (géré par la boucle interne), puis le réajuster.

Sous-cas 1 : A[i] < A[j] pour certains 0 <= j <= i - 1

D'après l'algorithme ci-dessus, A[j] sera échangé avec Ap = A[i] . Remarquez que d'après notre hypothèse, A[0:i-1] a été trié. Il s'ensuit donc que pour le reste des indices de j + 1 <= i nous allons réordonner notre région triée après avoir inséré Ap . Il s'ensuit que A[0:i] sera trié lorsque j = i .

Sous-cas 2 : A[i] >= A[j] pour tous 0 <= j <= i - 1

Aucun échange n'a lieu dans ce cas, et il s'ensuit que A[0:i] est trié à partir du A[0:i-1] étant triés et le fait que A[i] >= A[i - 1] .

Autre cas : j > i

Remarquez que, après j indice d'atteinte i le maximum de A sera de retour à l'index i . Ainsi, pour le reste de la boucle intérieure, aucun échange ne sera effectué. Il s'ensuit donc que A[0:i] seront triés.

Parce que ce qui précède est valable pour tous les i < n = len(A) nous pouvons conclure que l'exécution de l'itération n - 1 permettra de trier efficacement A[0:n-1] = A .

Vérification/amélioration

De la preuve ci-dessus, nous avons vu que la vérification pour j > i était redondant. Pour rendre l'algorithme plus efficace et plus en phase avec le tri par insertion habituel, nous pouvons exécuter le code ci-dessous qui triera également le tableau.

for i from 0 to n-1:
    for j from 0 to i: <- claim this line can be changed
        if A[j] > A[i]:
            swap A[i] and A[j]

Answer 4

Il s'agit d'un tri plutôt étrange, qui n'est absolument pas un tri à bulles. À la fin de chaque for i in range(n) itération, les i th contiendra désormais le plus grand élément de la liste. A . C'est-à-dire que nous échangeons l'élément i avec élément j chaque fois que l'élément j est supérieur à l'élément i. Il est clair qu'à la fin de l'algorithme, le dernier élément sera le plus grand.

Le point clé est le suivant : A la fin de l'itération i chaque élément à gauche de la position i (valeurs inférieures de i ) doivent avoir des valeurs inférieures ou égales, c'est-à-dire que A[j] <= A[j+1] pour j < i.

Le programme suivant tente de le démontrer :

from random import shuffle

def assert_partial_sort_order(A, i):
    """
    Assert A[j] <= A[j+1] for j < i
    """
    for j in range(i):
        assert A[j] <= A[j+1]

def sort(A):
    n = len(A)
    print('sort before:', A)
    n_swaps = 0
    for i in range(n):
        print('i =', i)
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]
                print('    swapping for j =', j)
                print('    A =', A)
        assert_partial_sort_order(A, i)
    print('sort after:', A, '\n')

n = 10
A = list(range(n))
shuffle(A)
sort(A)

Imprimés :

sort before: [7, 0, 4, 2, 8, 9, 5, 1, 3, 6]
i = 0
    swapping for j = 4
    A = [8, 0, 4, 2, 7, 9, 5, 1, 3, 6]
    swapping for j = 5
    A = [9, 0, 4, 2, 7, 8, 5, 1, 3, 6]
i = 1
    swapping for j = 0
    A = [0, 9, 4, 2, 7, 8, 5, 1, 3, 6]
i = 2
    swapping for j = 1
    A = [0, 4, 9, 2, 7, 8, 5, 1, 3, 6]
i = 3
    swapping for j = 1
    A = [0, 2, 9, 4, 7, 8, 5, 1, 3, 6]
    swapping for j = 2
    A = [0, 2, 4, 9, 7, 8, 5, 1, 3, 6]
i = 4
    swapping for j = 3
    A = [0, 2, 4, 7, 9, 8, 5, 1, 3, 6]
i = 5
    swapping for j = 4
    A = [0, 2, 4, 7, 8, 9, 5, 1, 3, 6]
i = 6
    swapping for j = 3
    A = [0, 2, 4, 5, 8, 9, 7, 1, 3, 6]
    swapping for j = 4
    A = [0, 2, 4, 5, 7, 9, 8, 1, 3, 6]
    swapping for j = 5
    A = [0, 2, 4, 5, 7, 8, 9, 1, 3, 6]
i = 7
    swapping for j = 1
    A = [0, 1, 4, 5, 7, 8, 9, 2, 3, 6]
    swapping for j = 2
    A = [0, 1, 2, 5, 7, 8, 9, 4, 3, 6]
    swapping for j = 3
    A = [0, 1, 2, 4, 7, 8, 9, 5, 3, 6]
    swapping for j = 4
    A = [0, 1, 2, 4, 5, 8, 9, 7, 3, 6]
    swapping for j = 5
    A = [0, 1, 2, 4, 5, 7, 9, 8, 3, 6]
    swapping for j = 6
    A = [0, 1, 2, 4, 5, 7, 8, 9, 3, 6]
i = 8
    swapping for j = 3
    A = [0, 1, 2, 3, 5, 7, 8, 9, 4, 6]
    swapping for j = 4
    A = [0, 1, 2, 3, 4, 7, 8, 9, 5, 6]
    swapping for j = 5
    A = [0, 1, 2, 3, 4, 5, 8, 9, 7, 6]
    swapping for j = 6
    A = [0, 1, 2, 3, 4, 5, 7, 9, 8, 6]
    swapping for j = 7
    A = [0, 1, 2, 3, 4, 5, 7, 8, 9, 6]
i = 9
    swapping for j = 6
    A = [0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
    swapping for j = 7
    A = [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
    swapping for j = 8
    A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sort after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 5

Je pense qu'il est instructif de le réécrire en supprimant les inefficacités.

En pseudo-code :

Find the largest element.  Move it to the location A[0].
For i from 1 upto n:
  For j from 0 upto i:
    swap A[i] and A[j] if A[j] is greater than A[i]
    Invariant: A[0...j] is sorted
    Invariant: A[j+1...i-1] is sorted
    Invariant: A[i] is larger than anything in A[0...j]

  Invariant: A[0...i] contains the same elements sorted, but now sorted

Cela permet de sauter deux choses. Tout d'abord, elle évite le "désordre" initial du tableau, qui n'a pratiquement aucun sens, et elle évite la comparaison, qui ne fait jamais rien, entre l'élément le plus grand et les éléments qui le suivent.

Sur la boucle i=5, on pourrait commencer par :

                      i
 10  20  30  40  99  25

j puis scanne :

[10] 20  30  40  99  25
 10 [20] 30  40  99  25
 10  20 [30] 40  99  25

à ce stade, A[j] (alias 30) est supérieur à A[i] (alias 25). Ils échangent et j avance :

 10  20  25 [40] 99  30
 10  20  25  30 [99] 40
 10  20  25  30  40 [99]

Dans l'algorithme original, le balayage de j jusqu'à n continue. Cela ne sert à rien, car l'élément le plus grand est déjà en A[i], donc A[j] n'est jamais plus grand que A[i].

La seule bizarrerie restante est le "pêle-mêle" qu'il fait pour déplacer l'élément le plus élevé vers A[0].

Regardez comment cela fonctionne :

A[0] est comparé successivement à A[1..n-1]. Tout élément plus grand que A[0] est échangé. Une fois que l'élément le plus grand est trouvé, les comparaisons restantes ne font rien.

Ce n'est pas quelque chose de super spécial.

La dernière chose à laquelle il faut penser est ce que le circuit - la version infiniment parallèle, où nous ne nous soucions que de dépendances informationnelles La séquence essentielle, et non accessoire, de cet algorithme ressemble à ceci . Soit X un circuit qui lit en haut à gauche et en haut à droite, et qui sort l'élément supérieur en bas à droite et l'élément inférieur en bas à gauche. Soit Y à la place qui sort l'élément supérieur en bas à gauche, et l'élément inférieur en bas à droite.

1 2 3 4 5 6 7
 Y  | | | | |
|  Y  | | | |
| |  Y  | | |
| | |  Y  | |
| | | |  Y  |
| | | | |  Y
| | | | | | *

puis nous tournons * vers le bas jusqu'à la première colonne.

Ainsi, chaque élément qui est plus grand que tout ce qui se trouve à sa gauche est déplacé vers la droite jusqu'à ce qu'il trouve un élément plus grand. Enfin, l'élément le plus grand est placé dans A[0] (car il n'a pas d'élément plus grand auquel s'arrêter).

Sur les itérations ultérieures

1 2 3 * 5 6 7 8

5 est "logiquement" déplacé à l'extrême gauche des valeurs :

5 1 2 3 * 6 7 8
 X  | |
|  X  |
| |  X

et ensuite mis en place avec un circuit comme celui-là.

Si vous suivez le * (le plus grand élément), vous remarquerez que nous connaissons déjà toutes ses comparaisons. Et si nous le déplaçons à l'emplacement 0 à l'étape 1, nous le faisons ensuite glisser (sans comparaisons nécessaires) jusqu'à la fin.

Donc en enlevant le * de la considération

1 2 3 4 5 6 7 8

est câblé comme :

5 1 2 3 4 6 7 8
 X  | | |
|  X  | |
| |  X  |
| | |  X

puis on met 6 dans

6 5 1 2 3 4 6 7 8
 X  | | | |
|  X  | | |
| |  X  | |
| | |  X  |
| | | |  X

À chaque étape, nous prenons le nouvel élément, nous le plaçons à gauche, puis nous effectuons une chaîne de permutations. Nous pouvons considérer cette inversion comme sans importance et obtenir ce schéma de câblage :

1 2 3 4 5 6 7
 X  | | | | |
|  X  | | | | 
 X   X  | | |
|  X   X  | | 
 X   X   X  |
|  X   X   X
 X   X   X  |
|  X   X  | |
 X   X  | | |
|  X  | | | |
 X  | | | | |

ce qui est en fait ce qu'on obtient quand on fait ça avec un tri à bulles. Dans cet algorithme, les boucles internes existent en diagonale dans le circuit ci-dessus. Pendant ce temps, dans une sorte de bulle, les boucles internes existent horizontalement dans le circuit ci-dessus.

En conclusion, je pense qu'il s'agit d'une variante relativiste du tri à bulles ; c'est un tri à bulles, avec un axe temps-espace incliné. Mais le graphe de dépendance pour chaque calcul finit par être presque identique, avec quelques différences relativement peu importantes (la recherche de l'élément le plus grand, et les bits de retournement d'ordre).