Tri pair-impair

modifier - modifier le code - modifier Wikidata 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. 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) : 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 : 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.