Lycée > Premiere > NSI > Trier par sélection

Trier par sélection

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Écrire un algorithme de tri par sélection d’un tableau de nombres.
Prouver la terminaison et la correction du tri par sélection.
Montrer que le cout du tri par sélection est quadratique.
Coder en Python l’algorithme de tri par sélection d’un tableau de nombres.

Points clés

Le tri par sélection d’un tableau consiste rechercher le plus petit élément et à le placer en 0, le second plus petit élément et à le placer en 1, etc.
Le cout d’un tri par sélection est toujours quadratique.

Pour bien comprendre

Utiliser des boucles (for et while).
Algorithmes de recherche : rechercher un extremum (terminaison, correction et cout).

1. L’algorithme de tri par sélection

a. Principe

Le tri par sélection (du minimum) d’un tableau de nombres de taille n consiste à le parcourir plusieurs fois et à placer le plus petit élément à sa place, puis le 2^e plus petit élément à sa place, puis le 3^e plus petit élément à sa place, etc. Le tri par sélection se fait en place.
Ainsi, à l’étape k, les k−1 premiers éléments du tableau sont triés et sont inférieurs aux autres éléments du tableau. On place ensuite le plus petit des éléments qui restent au rang k.

Exemple
Voici les étapes du tri par sélection de Tab=[2, 3, 1, 6, 4, 5].

Étape	Tab	Commentaire
1	[1, 3, 2, 6, 4, 5]	Parmi [2, 3, 1, 6, 4, 5], 1 est le plus petit élément. On échange 1 et 2.
2	[1, 2, 3, 6, 4, 5]	Parmi [3, 2, 6, 4, 5], 2 est le plus petit élément. On échange 2 et 3.
3	[1, 2, 3, 6, 4, 5]	Parmi [3, 6, 4, 5], 3 est le plus petit élément. 3 est déjà à sa place.
4	[1, 2, 3, 4, 6, 5]	Parmi [6, 4, 5], 4 est le plus petit élément. On échange 4 et 6.
5	[1, 2, 3, 4, 5, 6]	Parmi [6, 5], 5 est le plus petit élément. On échange 5 et 6.
6	[1, 2, 3, 4, 5, 6]	6 est à sa place.

b. Algorithme et exemple

Voici ci-dessous un algorithme du tri par sélection d’un tableau de nombres Tab de taille n.

Pour i allant de 0 à n−2	i = 0, puis i = 1, puis… i = n−2,
i_mini ← i	on affecte à la variable i_mini l’indice i. C’est i_mini qui va contenir l’indice du plus petit élément après le parcours.
Pour j allant de i+1 à n−1	j = i+1, puis j = i+2, puis… j = n−1,
Si Tab[j] < Tab[i_mini]	si Tab[j] est plus petit que Tab[i_mini],
i_mini ← j	alors on affecte j à i_mini.
FinSi	Fin de l’instruction conditionnelle.
échanger Tab[i] et Tab[i_mini]	On échange Tab[i] et Tab[i_mini].
FinPour	Fin de la seconde boucle « Pour ».
FinPour	Fin de la première boucle « Pour ».

Exemple – Tri par sélection de Tab=[2, 3, 1]

Pour i = 0, i_mini = 0
j = 1
Tab[1] = 3 > Tab[0] = 2
j = 2
Tab[2] = 1 < Tab[0] = 2
i_mini = 2
On échange Tab[0] = 2 (Tab[i]) et Tab[2] = 1 (Tab[i_mini]), ce qui donne [1, 3, 2].
Pour i = 1, i_mini = 1
j = 2
Tab[2] = 1 < Tab[1] = 3
i_mini = 2
On échange Tab[1] = 3 (Tab[i]) et Tab[2] = 2 (Tab[i_mini]), ce qui donne [1, 2, 3].
L’algorithme est fini car la première boucle Pour est terminée pour i = 1.

c. Programmation en Python 3

En Python, la fonction tri_selection(Tab) implémente le tri par sélection de Tab.

def tri_selection(Tab):	On définit la fonction tri_selection.
n = len(Tab)	La longueur de la table len(Tab) est affectée à la variable n.
for i in range(0, n−1):	Pour i allant de 0 à n−2.
i_mini = i	i est affecté à la variable i_mini.
for j in range(i+1, n):	Pour j allant de i+1 à n−1
if Tab[j] < Tab[i_mini]:	Si Tab[j] est plus petit que Tab[i_mini]
i_mini = j	alors j est affecté à la variable i_mini.
temp = Tab[i]	Tab[i] est affecté à la variable temporaire temp.
Tab[i] = Tab[i_mini]	Tab[i_mini] est affecté à Tab[i].
Tab[i_mini] = temp	temp est affecté à Tab[i_mini].

2. Terminaison, correction et cout du tri par sélection

a. Terminaison

L’algorithme de la partie précédente contient deux boucles Pour imbriquées. L’algorithme de tri par sélection se termine donc car une boucle Pour se termine toujours.

b. Correction

Pour l’algorithme de tri par sélection de la partie précédente, un invariant de boucle (proposition qui doit être vraie à chaque itération de l’algorithme) peut être :

P(i) : « Après la i-ème itération de la boucle Pour, dans le tableau Tab, les éléments Tab[0], Tab[1], …, Tab[i−1] sont triés dans l’ordre croissant et les autres éléments sont plus grands. »

Démonstration de la correction

Initialisation : P(1) est vraie car, après la première itération, i_mini contient l’indice de l’élément le plus petit du tableau.
Ensuite Tab[0] et Tab[i_mini] sont inversés. Ainsi Tab[0] est est le plus petit élément de Tab (les autres sont donc plus grands).
Hypothèse : Supposons P(i) vraie (pour 1 < i < n−1).
Montrons que P(i+1) est vraie.
Si P(i) est vraie, alors les éléments Tab[0], Tab[1], …, Tab[i−1] sont triés dans le tableau Tab et les éléments Tab[i], Tab[i+1], …, Tab[n−1] sont supérieurs.
À la (i+1)-ième itération, on mémorise i dans la variable i_mini.
La seconde boucle Pour parcourt les éléments Tab[i+1], Tab[i+2], …, Tab[n−1] et conserve dans i_mini l’indice du plus petit élément.
Ensuite, Tab[i_mini] et Tab[i] sont échangés.
Tab[i] est ainsi plus petit que les éléments Tab[i+1], Tab[i+2], …, Tab[n−1] et est supérieur à Tab[0], Tab[1], …, Tab[i−1].
Donc Tab[i] est à sa place.
Or les éléments Tab[0], Tab[1], …, Tab[i−1] sont déjà triés.
Donc les éléments Tab[0], Tab[1], …, Tab[i] sont triés.
C’est pourquoi P(i+1) est vraie.
Finalement, P(i) est vraie pour i entre 1 et n. Comme P(n) est vraie, alors Tab[0], Tab[1], …, Tab[n−1] sont triés. C’est pourquoi Tab est trié.
L’algorithme fait bien ce que l’on veut.

c. Cout

Le cout d’un algorithme de tri par sélection dépend de la taille n du tableau mais pas de sa nature : si le tableau est déjà trié (ou partiellement trié), les deux parcours des boucles Pour se feront malgré tout entièrement.

Le cout d’un algorithme de tri par sélection sera donc toujours le même pour un tableau de taille n.

L’algorithme de tri par sélection contient deux boucles imbriquées.

Ainsi pour un tableau de taille n,

la boucle externe Pour exécute n−1 instructions car for i in range(0, n−1) (i allant de 0 à n−2) correspond à n−1 itérations.
Pour chaque valeur de i de la boucle externe, le nombre d’instructions exécutées par la boucle interne Pour est de
(n−1) − (i+1) + 1 = n − 1 − i − 1 + 1 = n − 1 − i