|
I. Introduction
II. Fonctionnement
Il existe de nombreux algorithmes de tri. Je vais vous expliquer ici le fonctionnement du tri par sélection, qui a l'avantage d'être un des plus simples à mettre en oeuvre. Dans cet article, je détaillerais le tri sur un tableau d'entiers, mais cet algorithme est tout aussi valide pour trier un tableau de chaînes de caractères, de flottants, ou de tout autre type tant qu'on peut émettre une comparaison...
Considérons un tableau T de N chaînes de caractères (indicées de 1 à N).
Le principe est le suivant:
- Placer dans l'élément d'indice 1 du tableau T la plus petite valeur présente dans le tableau ; pour cela, on recherche la plus petite valeur dans T et on la place dans T[1] ; la valeur qui se trouvait auparavant dans T[1] est mise à sa place.
- Placer dans l'élément d'indice 2 de T la plus petite valeur présente dans la tranche de tableau T[2..N]
- Placer dans l'élément d'indice 3 de T la plus petite valeur présente dans la tranche de tableau T[3..N]
- et ainsi de suite jusqu'à l'étape N-1
Par exemple, avec le tableau d'entiers suivants:
La première étape consiste à identifier la plus petite valeur de l'intevalle T[1..5] et de faire l'échange avec la valeur de la case d'indice 1 :
on fait l'échange :
La 2° étape consiste à mettre la plus petite valeur de l'intervalle T[2..5] dans la case 2:
on fait l'échange :
La 3° étape consiste à mettre la plus petite valeur de l'intervalle T[3..5] dans la case 3:
on fait l'échange :
La 4° et dernière étape consiste à mettre la plus petite valeur de l'intervalle T[4..5] dans la case 4:
on fait l'échange :
Et voilà, on obtient le tableau trié
Pascal:
|
