Nicolas DAILLY
www.dailly.info > Dossiers techniques > Algorithmes de Tri > La fonction échanger

La fonction échanger

fonction de base pour la plupart des tris

Pour trier les valeurs d’un tableau, il va être nécessaire de permuter les valeurs contenues dans les différentes cases du tableau. Pour cela, une fonction de permutation, qui sera appelée "echanger", doit être écrite. Cette fonction prend en argument un tableau et deux entiers i et j. Elle récupère la valeur contenue dans la iième case du tableau, affecte à cette case la valeur contenue dans la jième case, puis affecte à la jième case l’ancienne valeur de la iième case.

Soit l’exemple suivant :

Considérons le tableau T suivant [1 ;4;3 ;2;5] dans lequel la permutation des valeurs contenues dans la première et la troisième case va être effectuée (la première case du tableau portant l’indice 0). Soit i=1 et j=3.

- Etape 1 : Mémorisation de la valeur contenue dans la case i=1 : M=T(i)=T(1)=4
- Etape 2 : Affectation à la iième case de la valeur de la jième case : T(i)=T(j)=T(3)=2. Soit T=[1 ;2;3 ;2;5]
- Etape 3 : Affectation à la jième case de la valeur contenue dans la mémoire M : T(j)=M. Soit T=[1 ;2;3 ;4;5]. C’est ce qu’il fallait obtenir.

Remarque : Pour le traitement de listes, il ne faut pas faire une fonction d’échange de ce type car le coût d’un tel échange est trop important. Certains des algorithmes présentés par la suite ne seront d’ailleur pas implémentés dans le cas des listes.

Pseudo langage
C / C++ Caml Java OCaml

- Accueil des algorithmes de tri
- Article précédent : Avant propos
- Article suivant : le tri bulle


© 2000-2017 ~ Nicolas Dailly
Page générée le 18/12/2017 à 07:59:52 ~ Site réalisé avec SPIP