Fiche de cours

Trier par sélection

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

Fiche de cours
Quiz et exercices
Vidéos et podcasts

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

Finalement, il y aura (n−1) + (n−2) + … + 3 + 2 + 1 instructions.

On admet la relation suivante :
.

Comme le terme dominant du cout est n², on dit que le cout est quadratique.

À retenir
Le cout du tri par sélection est quadratique dans tous les cas.

Évalue ce cours !

Note 3.6 / 5. Nombre de vote(s) : 33

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT