Tri par la méthode de Batcher.

Pour accélérer la vitesse d'un tri par échange, il est nécessaire de comparer des éléments qui ne sont plus adjacents et c'est ce que proposa K.E.Batcher en 1968.

En voici une description appliquée à un tableau A de N éléments numérotés de 1 à N:

* déterminons t qui est la plus petite valeur telle que 2t>=N
* assignons à p la valeur 2t-1, c'est le plus grand écart
  exprimé sous forme de puissance de 2 qui existe entre des
  numéros de position d'éléments de A.
* il faut "boucler" sur p: 2t-1, 2t-2, ... jusqu'à p=1.
  Pour chaque valeur de p, il faut
   * initialiser q à 2t-1, r à 0 et d à p.
   * "boucler" sur i de 0 à N-d-1:
        si i AND p=r alors il faut comparer/échanger Ai+1 et Ai+d+1
   * si q=p, on change de p
     sinon d vaut q-p, q vaut q\2 et r vaut p.

NOTE: i AND p = r implique que d est un multiple impair de p
tel que i AND p est différent de (i+d) AND p
ce qui implique que les comparaisons/échanges concernent des
éléments différents et peuvent être exécutés simultanément.


Exemple: il faut trier
1 2 3 4 5 6 7 8 9
7 8 9 1 0 2 5 6 3

Comme N vaut 9, la plus petite puissance de 2 supérieure à N est 16.
Donc, t vaut 4 et p vaut 8. 


    p = 8   q = 8    r = 0    d = 8

Comparons A1 à A9 et échangeons-les.
1 2 3 4 5 6 7 8 9
3 8 9 1 0 2 5 6 7

Comme nous avons examiné tous les éléments dont les numéros ont un écart de 8, nous nous occupons de ceux dont l'écart est de 4. 


    p = 4   q = 8    r = 0    d = 8

Examinons les couples A1 - A5, A2 - A6, A3 - A7, A4 - A8. Si ils ne sont pas dans l'ordre croissant, nous les échangeons.
1 2 3 4 5 6 7 8 9
3 8 9 1 0 2 5 6 7

Et nous obtenons:
1 2 3 4 5 6 7 8 9
0 2 5 1 3 8 9 6 7

Passons à l'étape suivante: 


    p = 4   q = 4    r = 4    d = 4

Nous comparons/échangeons A5 - A9.
Comme nous avons examiné tous les éléments dont les numéros ont un écart de 4, nous nous occupons de ceux dont l'écart est de 2. 


    p = 2   q = 8    r = 0    d = 2

Examinons donc les couples A1 - A3, A2 - A4, A5 - A7, A6 - A8. Si ils ne sont pas dans l'ordre croissant, nous les échangeons et nous obtenons.
1 2 3 4 5 6 7 8 9
0 1 5 2 3 6 9 8 7

Ensuite 


    p = 2   q = 4    r = 2    d = 6

Comparons/échangeons donc A3 - A9.
Comme continuons à examiner les éléments dont les numéros ont un écart de 2. 


    p = 2   q = 2    r = 2    d = 2

Examinons les couples A3 - A5, A4 - A6, A7 - A9. Si ils ne sont pas dans l'ordre croissant, nous les échangeons et nous obtenons.
1 2 3 4 5 6 7 8 9
0 1 3 2 5 6 7 8 9

Occupons-nous maintenant des éléments dont l'écart est de 1. 


    p = 1   q = 8    r = 0    d = 1

Examinons les couples A1 - A2, A3 - A4, A5 - A6, A7 - A8. Si ils ne sont pas dans l'ordre croissant, nous les échangeons et nous obtenons.
1 2 3 4 5 6 7 8 9
0 1 2 3 5 6 7 8 9

Ensuite 


    p = 1   q = 4    r = 1    d = 7

Nous comparons/échangeons A2 - A9.
Restons avec p=1, 


    p = 1   q = 2    r = 1    d = 3

Il nous reste ` nous occuper des couples A2 - A5, A4 - A7, A6 - A9. Si ils ne sont pas dans l'ordre croissant, nous les échangeons et nous obtenons.
1 2 3 4 5 6 7 8 9
0 1 2 3 5 6 7 8 9

Maintenant, 


    p = 1   q = 1    r = 1    d = 1

et nous terminons par les couples A2 - A3, A4 - A5, A6 - A7, A8 - A9. Si ils ne sont pas dans l'ordre croissant, nous les échangeons et nous obtenons.
1 2 3 4 5 6 7 8 9
0 1 2 3 5 6 7 8 9

Et le tri est terminé.

Page précédente.

Page d'accueil.