N.B. Niveau : Terminale Générale, enseignement de spécialité NSI (Numérique et Sciences Informatiques)
À savoir
Le tri par sélection d'un tableau consiste à
Ainsi, après k étapes de tri, les k premiers éléments du tableau (donc les éléments d'indice 0 à k - 1) sont triés. On cherche le plus petit des éléments restants (les éléments restants étant les éléments d'indices supérieurs ou égaux à k), et on l'échange avec l'élément d'indice k du tableau.
Étape | Tableau au départ | Indice du premier élément non trié | Minimum à partir de l'indice | Indice du minimum | Tableau après échange |
---|---|---|---|---|---|
1 | |||||
2 | |||||
3 | |||||
4 |
Compléter le tableau ci-dessous avec les différentes étapes du tri par sélection, si le tableau à trier est [100, 3, 0, 7, 10, 80] :
Étape | Tableau au départ | Indice du premier élément non trié | Minimum à partir de l'indice | Indice du minimum | Tableau après échange |
---|---|---|---|---|---|
1 | |||||
2 | |||||
3 | |||||
4 | |||||
5 |
Lorsqu'on réalise un tri par sélection, après k étapes, les éléments d'indice 0 à k - 1 sont triés. Notons m l'indice du plus petit des éléments non triés (ceux dont l'indice est supérieur ou égal à k). L'étape suivante du tri consiste à échanger l'élément d'indice k et l'élément d'indice m. Bien sûr, cela nécessite de connaître la valeur de m. On peut l'obtenir grâce à une fonction.
a) Écrire en Python une fonction selection_min
qui :
tab
et un indice k
,tab
à partir de l'indice k
.Par exemple selection_min([1,3,7,10,5], 2)
devra retourner l'indice du plus petit élément
à partir de l'indice 2, c'est-à-dire 4 (l'indice de l'élément 5).
b) Tester la fonction selection_min dans plusieurs cas, sans oublier les cas limites.
Considérons un tableau tab
et notons n
sa longueur. Pour réaliser un tri par sélection,
il faut initialiser une variable k
à 0 puis répéter n - 1 fois :
m
l'indice du plus petit élément du tableau à partir de l'indice k
,k
et l'élément d'indice m
du tableau,k
.a) Écrire en Python une fonction tri_selection qui
:
tab
Par exemple tri_selection([3, 1, 0, 5, 8])
devra retourner [0, 1, 3, 5, 8]
Attention : La fonction tri_selection
devra faire appel à la fonction selection_min
.
b) Tester la fonction tri_selection
, en pensant à réaliser plusieurs tests et à tester les cas limites.
a) Écrire en Python une fonction récursive tri_selection_rec
qui :
tab
et un entier debut
,debut
grâce au tri par sélection.Par exemple tri_selection_rec([3, 1, 8, 5, 18]
, 2) devra retourner [3, 1, 5, 8, 18]
La fonction tri_selection_rec
devra faire appel à la fonction selection_min
.
b) Regrouper les fonctions selection_min
et tri_selection_rec
en une seule fonction de tri
que l'on nommera tri_selection2
.
Fond : Texte : Tables : Thème Python:
Contenu sous licence CC BY-NC-SA 3.0
Amandine SCHRECK
MAJ : 08/10/2023