Le principe du tri par sélection/échange (ou tri par extraction ) est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit élément du vecteur pour le mettre en second, etc...
L'animation ci-après détaille le fonctionnement du tri par sélection :
Démonstration du tri par sélection
PROCEDURE tri_Selection ( Tableau a[ 1 : n] )
POUR i VARIANT DE 1 A n - 1 FAIRE
TROUVER [ j] LE PLUS PETIT ELEMENT DE [ i + 1 : n] ;
ECHANGER [ j] ET [ i] ;
FIN PROCEDURE ;
let rec plus_petit tab debut fin =
if ( debut == fin) then debut else
let temp = plus_petit tab ( debut+ 1 ) fin in
if tab. ( debut) > tab. ( temp) then temp else debut;;
let tri_selection tableau =
for en_cours = 0 to 18 do
let p = plus_petit tableau ( en_cours+ 1 ) 19 in
begin
if p <> en_cours then
begin
let a = tableau. ( en_cours) in
begin
tableau. ( en_cours) <- tableau. ( p) ;
tableau. ( p) <- a;
end ;
end ;
end ;
done ;
tableau;;
type tab = array [ 1 ..20 ] of integer ;
procedure tri_selection( var tableau : tab) ;
var
temp: integer ;
en_cours, plus_petit, j : integer ;
begin
for en_cours:= 1 to 19 do
begin
plus_petit := en_cours;
for j:= en_cours + 1 to 20 do
begin
{Recherche de l'element le plus petit}
if tableau[ j] < tableau[ plus_petit] then plus_petit:= j;
end ;
{On place le plus petit à la position en_cours}
temp:= tableau[ en_cours] ;
tableau[ en_cours] := tableau[ plus_petit] ;
tableau[ plus_petit] := temp;
end ;
end ;
def tri_selection( tableau) :
nb = len ( tableau)
for en_cours in range ( 0 ,nb) :
plus_petit = en_cours
for j in range ( en_cours+1 ,nb) :
if tableau[ j] < tableau[ plus_petit] :
plus_petit = j
if min is not en_cours :
temp = tableau[ en_cours]
tableau[ en_cours] = tableau[ plus_petit]
tableau[ plus_petit] = temp
void tri_selection( int * tableau, int taille)
{
int en_cours, plus_petit, j, temp;
for ( en_cours = 0 ; en_cours < taille - 1 ; en_cours++ )
{
plus_petit = en_cours;
for ( j = en_cours 1 ; j < taille; j++ )
if ( tableau[ j] < tableau[ plus_petit] )
plus_petit = j;
temp = tableau[ en_cours] ;
tableau[ en_cours] = tableau[ plus_petit] ;
tableau[ plus_petit] = temp;
}
}
Précedent
Comparaisons :
Déplacements :
Mélanger
Résoudre