Le tri par sélection

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

Pseudo-code

PROCEDURE tri_Selection ( Tableau a[1:n])
POUR i VARIANT DE 1 A n - 1 FAIRE
TROUVER a[j] le plus petit élément du Tableau a[i:n];
ECHANGER a[j] et a[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;
}
}

Correction de l'algorithme de tri par selection

Dans notre algorithme de tri par selection, l'invariant de boucle est "Le tableau a[1:i+1] est trié" :

INITIALISATION : La valeur avant de rentrer dans la boucle est i=0, donc le tableau a[1:1] contient un seul élément. Un tableau contenant un seul élément est forcément trié (trivial), notre invariant "le tableau a[1:i+1] est trié" est donc vrai.

CONSERVATION : si l'invariant de boucle est vrai avant une itération de la boucle : "Le tableau a[1:i] est trié", alors il le reste à la fin de l'itération : "Le tableau a[1:i+1] est trié".
Le tableau a[1:i] est trié et tous ses éléments sont plus petits ou égaux que les éléments du tableau a[i+1:n], donc le plus petit élément de a[i+1:n] sera le plus grand élément de a[1:i] et après ECHANGE cet élément sera a[i+1], donc le tableau a[1:i+1] sera évidemment trié.

TERMINAISON : La dernière valeur prise de i dans la boucle est i=n-1, donc le tableau a[1:n] sera trié.

Cette démonstration nous permet d'affirmer que l'algorithme de tri par selection est correct.

Complexité de l'algorithme de tri par selection

Pour évaluer la complexité d'un algorithme il faut envisager le pire des cas, ici lorsque la liste est classée dans l'ordre décroissant.

On suppose que notre liste à n éléments, on va essayer de compter le nombres d'opérations nécessaires pour obtenir la liste triée.

Il y a n-1 boucles :

boucle 1 : pour trouver le plus petit élément, il y a n-1 comparaisons et 2 changements de place, soit n+1 étapes
boucle 2 : pour trouver le plus petit élément, il y a n-2 comparaisons et 2 changements de place, soit n étapes
boucle 3 : pour trouver le plus petit élément, il y a n-3 comparaisons et 2 changements de place, soit n-1 étapes
...
boucle n-1 : pour trouver le plus petit élément, il y a 1 comparaisons et 2 changements de place, soit 3 étapes

Soit au total, (n+1)+n+(n-1)+...+3=(n-1)(n+4)/2 (propriété des sommes des suites arithmétiques)

Donc la complexité est de l'ordre de n², on dira que le coût est quadratique.

Interprétation

Un exercice

On utilise un algorithme de tri de coût quadratique. Il met 3 secondes pour trier un liste de 10 000 nombres.
Quel sera le temps approximativement pour trier 20 000 nombres ?

Solution
On calcule le rapport des nombres d'éléments de chaque liste : pour passer de 10 000 à 20 000 on multiplie par 2.
Donc le temps sera multiplié par 2² = 4. Soit 3 × 4 = 12 secondes.