- Échange (informatique)
-
En programmation informatique, l'échange de deux variables (en anglais swap) consiste à intervertir leurs valeurs. Il s'agit d'une opération de base intégrée à de nombreux langages de programmation et faisant partie du jeu d'instructions de certains processeurs.
De nombreux algorithmes, en particulier des algorithmes de tri, modifient les données en utilisant des échanges.
Sommaire
Algorithmes
En utilisant une variable temporaire
La méthode la plus simple et probablement la plus répandue pour échanger deux variables est d'utiliser une troisième variable temporaire :
fonction échanger(x, y) temp := x x := y y := tempL'inconvénient de cette méthode est qu'elle nécessite un espace mémoire supplémentaire. Cela n'a normalement pas d'importance si les variables ont un type élémentaire (entier, nombre flottant, etc), mais peut poser problème pour des structures complexes occupant une grande quantité de mémoire (par exemple des tableaux).
En utilisant l'opération XOR
Lorsque deux variables sont représentées chacune sur un seul mot mémoire, il est possible de les échanger en utilisant la fonction OU exclusif (XOR en anglais). Cette méthode ne nécessite pas de variable temporaire.
fonction échanger(x, y) x := x XOR y y := x XOR y x := x XOR yEn utilisant l'addition et la soustraction
Une variante de l'échange par XOR est d'utiliser une addition et deux soustractions. Elle a l'inconvénient de poser des problèmes de dépassement.
fonction échanger(x, y) x := x + y y := x - y x := x - yImplantation en matériel
Certains processeurs disposent d'une instruction swap permettant d'échanger deux registres. C'est le cas par exemple des processeurs x86 (instruction XCHG).
Sur les processeurs x86, l'instruction NOP consiste à échanger le registre eax avec-lui même[1].
Références
(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « Swap (computer science) » (voir la liste des auteurs)(en) Cet article est partiellement ou en totalité issu de l’article en anglais intitulé « XOR swap algorithm » (voir la liste des auteurs)
Wikimedia Foundation. 2010.
