Voir la source de Tri pair-impair

{{Infobox Algorithme}}
En [[informatique]], le '''tri pair-impair''', appelé plus précisément '''tri pair-impair par transposition''' (en anglais ''odd-even transposition sort'') pour le distinguer du ''tri pair-impair de Batcher'' ou ''tri pair-impair par fusion''  (en anglais ''odd-even merge sort'') est un [[algorithme de tri]] simple, basé sur le [[tri à bulles]], avec lequel il partage quelques caractéristiques. Il opère en comparant tous les couples d'éléments aux positions paires et impaires consécutives dans une liste et, si un couple est dans le mauvais ordre (le premier élément est supérieur au second), il en échange les deux éléments.

L'algorithme continue en alternant les comparaisons entre éléments aux positions paires-impaires et aux positions impaires-paires consécutives jusqu'à ce que la liste soit ordonnée.

Le tri pair-impair peut être vu comme une version parallèle du tri à bulles, où les comparaisons commencent simultanément à toutes les positions de la liste (positions impaires dans la première passe).

En tant que [[réseau de tri]], l'algorithme est peu efficace, ni en ''taille'' ni en ''profondeur'', mais il a une structure particulièrement simple.

== Pseudo-code ==
L'algorithme est aussi simple à mettre en œuvre que le tri à bulles. Le voici en [[pseudo-code]] (on suppose que les tableaux commencent à l'indice 0) :

 trié = '''faux''';
 '''tantque''' '''non''' trié
   trié = '''vrai''';
   <span style="color:green">''comparaisons impaires-paires : ''</span>
   '''pour''' (x = 0; x < list.length-1; x += 2)
     '''si''' list[x] > list[x+1]
       échanger list[x] et  list[x+1]
       trié = faux;
   <span style="color:green">''comparaisons paires-impaires : ''</span>
   '''pour''' (x = 1; x < list.length-1; x += 2)
     '''si''' list[x] > list[x+1]
       échanger list[x] et  list[x+1]
       trié = faux;

On peut encore simplifier le code en remplaçant la boucle extérieure - celle qui s'arrête quand la liste est triée - par un majorant sur le nombre de tours à faire : il suffit de faire ''n''/2 tours pour une liste de taille ''n''. On s'approche alors des réseaux de tri :

 '''pour''' (i = 1; i < list.length-1; i += 1)
   <span style="color:green">''comparaisons impaires-paires : ''</span>
   '''pour''' (x = 1; x < list.length-1; x += 2)
     '''si''' list[x] > list[x+1]
       échanger list[x] et  list[x+1]
   <span style="color:green">''comparaisons paires-impaires : ''</span>
   '''pour''' (x = 0; x < list.length-1; x += 2)
     '''si''' list[x] > list[x+1]
       échanger list[x] et  list[x+1]

== Réseau de tri ==
{{article principal|réseau de tri}}
[[File:Réseau de tri pair-impair.jpg|thumb|Réseau de tri pair-impair de huit éléments. Il est formé de 4 étapes de 8 comparateurs, chacune comparant les éléments voisins aux positions paires-impaires, puis aux positions impaires-paires.]]

=== Réseau de tri pair-impair par transposition ===
Un ''réseau de comparateurs'' est fait de ''fils'' et de ''comparateurs''. Les comparateurs comparent et échangent si nécessaire les données qui entrent par les données qui se trouvent sur les fils. Un ''réseau de tri'' est un réseau de comparateurs qui tri correctement les données. Le principe du zéro-un dit qu'un réseau de comparateurs est un réseau de tri s'il tri correctement les suites composées de 0 et de 1.

Un comparateurs pour les fils <math>i</math> et <math>j</math> se note <math>[i:j]</math>. Le réseau pair-impair de ''n'' données est composé de ''n''/2 tranches de comparateurs. Chaque tranche comporte ''n'' comparateurs, d'abord de la forme <math>[i:i+1]</math> pour les entiers <math>i</math> pairs (si on commence à 0) puis de la forme <math>[i:i+1]</math> pour les entiers <math>i</math> impairs. La ''taille'' d'un tel réseau est <math>n^2/2</math>, sa ''profondeur'' est <math>n</math>. Ces deux nombres sont trop élevés pour en faire un réseau efficace en pratique pour des volumes importants, mais il a une structure particulièrement simple<ref name="clrs">Problème 27.1 : « Réseaux de tri par transposition», {{p.|697}}, dans {{Cormen2fr}}.</ref>{{,}}<ref name="FH">{{Lien web|langue=en|url=http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oetsen.htm
|titre= Odd-even transposition sort
|série= Algorithmen - Sortieren - Networks
|auteur= H. W. Lang   |jour= 5 |mois=  mars |année= 1997
|éditeur= FH Flensburg, Allemagne|en ligne le= 18 mai 2010|consulté le=22 juillet 2015|id=FH
}}.</ref> 
L'algorithme a été présenté à l'origine par Habermann en 1972<ref>Nico Haberman, « Parallel Neighbor Sort (or the Glory of the Induction Principle) », Carnegie Mellon University, Computer Science Report (Rapport technique), 1972, {{lire en ligne|url=http://repository.cmu.edu/cgi/viewcontent.cgi?article=3086&context=compsci}}</ref>. Il s'étend au cas de plusieurs items par comparateur ([[processeur]]). Ainsi, dans l'algorithme pair-impair de division-fusion de Baudet et Stevenson<ref>{{article| auteur1 = Gérard M. Baudet| auteur2    = David Stevenson|  titre = Optimal Sorting Algorithms for Parallel Computers|  journal   = IEEE Trans. Computers| volume = 27|  numéro = 1| pages =84-87|  année = 1978| doi = 10.1109/TC.1978.1674957}}.</ref>, chaque processeur trie sa propre sous-liste à chaque étape, en utilisant un algorithme propre, puis réalise une fusion avec son voisin, où les voisins alternent entre pair-impair et impair-pair à chaque étape<ref>{{chapitre| titre ouvrage = Advances in Computers| auteurs ouvrage = Marshall C. Yovits (éditeur) | titre = Parallel Sorting Algorithms | auteur1 = S. Lakshmivarahan | auteur2= S. K. Dhall| auteur3= L. L. Miller | volume = 23 | éditeur = Academic Press | passage = 295–351 | isbn = 978-0-12-012123-6 | année = 1984 | url = https://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322}}.</ref>.

=== Preuve de correction ===
[[File:Tri pair-impair démonstration.jpg|thumb|Tri pair-impair démonstration, deuxième cas.]]
Par le [[Réseau_de_tri#Principe_du_zéro-un|principe du zéro-un]], il suffit de démontrer qu'une suite de 0 et 1 est correctement triée. La preuve est par récurrence sur le nombre ''n'' d'éléments à trier.

Quand ''n''=1, le réseau est composé d'un seul fil sans comparateurs, et la suite est correctement trié. Supposons donc ''n''>1, et soit <math>(a_0,\ldots,a_{n-1})</math> une suite de 0 et 1.

Si <math>a_{n-1}=1</math>, les comparateurs <math>[n-2 : n-1]</math> sont inutiles. Si on supprime ces comparateurs, il reste un réseau pair-impair à <math>n-1</math> fils qui, par hypothèse de récurrence, trie la suite <math>(a_0,\ldots,a_{n-2})</math> de longueur <math>n-1</math>. Comme l'élément <math>a_{n-1}=1</math> est déjà à sa bonne place, la suite entière est déjà triée, et réintroduire les comparateurs <math>[n-2 : n-1]</math> ne modifie pas le résultat.

Si en revanche <math>a_{n-1}=0</math>, les comparateurs impliqués par cette valeur sont successivement <math>[n-2 : n-1], [n-3 : n-2],\ldots,[0,1]</math>, et on peut considérer qu'ils réalisent chacun un échange (même si l'échange de deux valeurs toutes deux égales à 0 ne produit pas d'effet visible). On peut alors  remplacer ces comparateurs correspondants par des lignes qui se croisent, et en "rehaussant" la deuxième partie du réseau d'un fil, on est ramené à un réseau à <math>n-1</math> entrées<ref name="FH" />.

== Notes et références ==
{{Références}}
== Articles connexes ==
* [[Réseau de tri]]
* [[Ken Batcher]]

{{Palette|Algorithmes de tri}}
{{portail|informatique|informatique théorique}}

[[Catégorie:Algorithme de tri|Pair-impair, Tri]]