a.Tri par sélection
L'idée du tri du consiste à chaque étape à rechercher le plus petit élément non encore trié et à le placer à la suite des éléments déjà triés.
A une étape i, les i − 1 plus petits éléments sont en place, et il nous faut sélectionner le ième élément à mettre en position i.
L'analyse de cet algorithme donne :
A chaque étape i
Rechercher le ième élément !
Le placer en position i !
Méthode :
CONST TAILLE=50
TYPE TABL=TABLEAU [TAILLE] DE REEL
PROCEDURETriSélection(VAR T :TABL; TAILLE :ENTIER)
VAR i,pos :ENTIER
DEBUT
POUR i DE 1 A TAILLE -1
FAIRE
pos trouverMin(T ,i) // Plus petit élément du tableau restant
echanger(T,i,pos) // Echanger avec l'élément en position i
FINPOUR
FIN
-----------------------------------------------------------------------------------------------------------------
// Fonction retournant l'indice du plus petit élément dans le tableau entre les indices i et la fin du tableau
FONCTION trouverMin(T:TABL i: ENTIER ):ENTIER
VAR i_Min, j :ENTIER
DEBUT
i_Min i
POUR j DE i_Min +1 A TAILLE
FAIRE
SI T [j] < T[i_Min]
ALORS
i_Min j
FINSI
FINPOUR
RETOURNER( i_Min)
FIN
---------------------------------------------------------------------------------------------------------------------
// PROCEDURE échangeant les éléments d'indices i et j dans un tableau
PROCEDURE Echanger (VAR T: TABL; i,j: ENTIER)
VAR Aux :ENTIER;
DEBUT
Aux T[i]
T[i] T[j]
T[j] Aux
FIN