11 - tri par sélection
Nous avons vu également comment programmer un tri avec le tri par insertion qui est le tri usuel qu'on réalise lorsqu'on joue aux cartes.
Imaginons qu'on veuille trier les cartes suivantes de la plus petite à la plus grande.




On vérifie qu'on n'a pas à bouger le 2, puis le 8, puis le 9 mais on voit que le 4 pose problème par rapport au 9.








Du coup, on bouge le 9. Puis, on bouge le 8. Enfin, on voit qu'on a pas besoin de bouger le 2.








Et voilà : il ne reste plus qu'à mettre le 4 entre le 2 et le 8.




Cette manière de trier n'est cependant pas très efficace :
- dans le pire des cas (liste triée à l'envers) : Θ(n2).
- sa complexité est en n2
- on dira que le coût est quadratique.
- dans le meilleur des cas (liste déjà triée) : Θ(n).
- sa complexité est en n
- on dira que son coût est linéaire
Python permet de trier les tableaux ou les dictionnaires plus efficacement avec la méthode sort ou la fonction native sorted. Voir la partie FAQ pour un rappel. Du coup, il n'utilise pas le tri par insertion... En effet, il existe de nombreuses façons de trier les choses.
Nous allons voir aujourd'hui une nouvelle façon de trier : le tri par sélection. Je spoile : nous verrons qu'il n'est pas efficace non plus. Le programme de Terminale permettra par contre de rencontrer des algorithmes bien plus efficace !
Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...
Prérequis : les activités suivantes
- Algorithme : parcours séquentiel d'un tableau,
- Algorithme : Tri par insertion,
- Algorithme : Preuve du tri par insertion
Evaluation ✎ : questions 16-17-18
Résumé de cours : open document ou pdf
1 - Tri par sélection de cartes par un humain
Comme pour le tri par insertion, le principe du tri par sélection est de faire deux listes : une liste des éléments déja triés et une liste des éléments pas encore triés. On ne rajoutera qu'un élément à la fois dans la liste des éléments triés.
Prenons le cas de l'introduction : on a au départ une liste triée vide (en orange) et une liste non triée à priori contenant 4 cartes (sans couleur).




Le principe est simple :
- On lit les cartes une par une et on cherche la carte la plus petite parmi les cartes non encore triées. On lit 2, 8, 9 et 4. On trouve 2 ici en indice 0.
- On la sélectionne et on l'inverse avec celle qui est en première postion (ici, on laisse en réalite le 2 en place du coup).
- On a maintenant deux listes : une liste triée de un élément et une liste non triée contenant les autres cartes.
- On regarde donc quelle est la carte la plus petite à placer en deuxième position parmi les cartes non triées 8, 9 et 4.
- On la sélectionne et on l'inverse avec la carte qui est en deuxième position (on intervertit donc le 8 et le 4).
- On a maintenant deux listes : une liste triée de 2 éléments et une liste contenant les 2 autres cartes non encore traitées.
- ... on continue jusqu'à ce que le paquet rouge des cartes non encore triées soit vide ...
























On voit donc qu'on va avoir besoin de deux fonctions :
- Une fonction permetttant de trouver le plus petit élément dans un tableau entre deux indices
- Une fonction permettant d'intervertir les éléments placés à deux indices connus.
2 - Principe du tri par sélection dans un tableau
Imaginons que vous ayez à trier ce tableau de nombres entiers [90, 60, 20, 50, 80]
.
Recherche du premier minimum
Nous allons commencer par lire un par un les valeurs de l'index 0 à l'index final pour trouver la plus petite valeur. Au début, on considère donc que 60 est le minimum et on va lire les autres valeurs une par une pour voir si il y a mieux.
↓ | |||||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 60 | 90 | 20 | 50 | 80 |
Min |
On trouve 20 au final après avoir lue les cases de 0 à 4.
↓ | ↓ | ↓ | |||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 60 | 90 | 20 | 50 | 80 |
Min |
Il suffit alors d'intervertir les contenus des valeurs des index 0 et 2.
↓ | ↓ | ↓ | |||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 90 | 60 | 50 | 80 |
On obtient alors un sous-tableau de 1 élément trié et un sous-tableau de 4 éléments non triés.
↓ | |||||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 90 | 60 | 50 | 80 |
Trié |
Etape 2 : on cherche à trouver le minimum suivant pour le placer sur l'index 1. Au début, on considère donc que le minimum vaut 90 et on lit les valeurs des indices 2 et plus pour voir si on trouve plus petit.
↓ | |||||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 90 | 60 | 50 | 80 |
Trié | Min |
En cherchant un par un, on trouve que le plus petit est 50.
↓ | ↓ | ↓ | |||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 90 | 60 | 50 | 80 |
Trié | Min |
On intervertit donc les contenus des index 1 et 3.
↓ | ↓ | ↓ | |||
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 50 | 60 | 90 | 80 |
Trié | Min |
On obtient donc un sous-tableau de 2 éléments triés et un sous-tableau de 3 éléments non triés.
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 50 | 60 | 90 | 80 |
Trié | Trié |
Etape suivante : on rajoute l'élément suivant
On prend 60 comme minimum suivant et on ne trouve pas mieux plus loin. On garde donc le 60.
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 50 | 60 | 90 | 80 |
Trié | Trié | Trié |
Etape suivante : on rajoute l'élément suivant
On prend 90 comme minimum suivant et on trouve 80 plus loin : on intervertit donc les deux valeurs aux index 3 et 4.
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 50 | 60 | 80 | 90 |
Trié | Trié | Trié | Trié |
Dernière étape : on rajoute le dernier élément
On prend 90 comme minimum suivant et comme il est le dernier élément, c'est forçément le plus petit de ceux qui restent !
Index | 00 | 01 | 02 | 03 | 04 |
Elément | 20 | 50 | 60 | 80 | 90 |
Trié | Trié | Trié | Trié | Trié |
Voici une animation permettant de comprendre cela avec des différentes valeurs.
01° Utiliser l'animation avec des valeurs au hasard, des tableaux déjà triés ou triés dans le mauvais sens. Voyez-vous une différence de temps de traitement ?
Tri par sélection du plus petit au plus grand
Index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
Elément | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
...CORRECTION...
Et non. Aucune différence de temps.
Que la liste soit aléatoire, bien triée ou mal triée, c'est long...
3 - Algorithme du tri par sélection
Dans la partie 1, vous avez vu le principe, réalisable par un humain.
Dans la partie 2, nous avons vu qu'il fallait parvenir à travailler sur les cases une par une si on veut parvenir à faire réaliser ce tri par un ordinateur.
Nous allons maintenant voir comment convertir chaque action décrite en Français en version algorithme.
Algorithme de tri par sélection
But : trier sur place un tableau initialement non trié.
(ici par odre croissant)
Description des entrées / sortie
ENTREES
:tableau
: un tableau contenant au moins deux éléments.- (optionnelle selon les langages d'implémentation):
longueur
, le nombre d'éléments dans le tableau SORTIE
: aucune. Le tableau est trié sur place. On modifie directementtableau
.
Exemple :
Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]
Initialement le tableau contient donc cela :
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Elément | 13 | 18 | 89 | 1024 | 45 | -12 | 18 |
Après le tri, le tableau contiendra cela :
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Elément | -12 | 13 | 18 | 18 | 45 | 89 | 1024 |
En Français
- Pour chaque index debut du tableau
- On cherche l'index index_min contenant le plus petit élément dans le sous-tableau [index debut ; index final].
- On intervertit les contenus des index debut et index_min.
Algorithme
debut est l'index (flèche en vert clair dans l'animation) de la case à remplir
POUR debut
variant de 0
à (longueur - 1)
index_min
← minimum(tableau, debut)
on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)
intervertir(tableau, debut, index_min)
on intervertit les valeurs situées aux index debut et index_min
Fin POUR
Renvoyer VIDE (∅)
02° Pourquoi pourrait-on dire que cet algorithme décrit une procédure ?
...CORRECTION...
Cet algorithme ne renvoie rien (vide): il modifie juste le tableau en place.
C'est la définition même d'une procédure : on agit mais on ne revoit rien vers le programme qui a fait appel à ce bout de code.
En Python, cela revient à renvoyer None puisque les vrais procédures n'existent pas.
4 - Tri par insertion en Python
Nous allons maintenant transcrire cet algorithme en Python. Cela nous permettra de revoir quelques notions et connaissances fondamentales.
03° Les tableaux de Python (type list pour nous) sont-ils des structures de données mutables ?
Citer deux structures de données mutables en Python et deux structures non mutables en Python.
...CORRECTION...
Les tableaux (le type list) sont mutables en Python : on peut modifier leurs contenus et garder la même adresse mémoire pour le tableau.
Les types list et dict sont mutables.
>>> tableau = [1, 10, 100]
>>> tableau[0]
1
>>> tableau[0] = 2
>>> tableau
[2, 10, 100]
>>> type(tableau)
<class 'list'>
>>> type(tableau) == list
True
>>> dictionnaire = {'a':1, 'b':10, 'c':100}
>>> dictionnaire['a']
1
>>> dictionnaire['a'] = 2
>>> dictionnaire
{'a': 2, 'b': 10, 'c': 100}
>>> type(dictionnaire)
<class 'dict'>
>>> type(dictionnaire) == dict
True
Les types str et tuple sont non mutables.
>>> p_uplet = (1, 10, 100)
>>> p_uplet[0]
1
>>> p_uplet[0] = 2
TypeError: 'tuple' object does not support item assignment
>>> p_uplet
(1, 10, 100)
>>> type(p_uplet)
<class 'tuple'>
>>> type(p_uplet) == tuple
True
>>> texte = "Bonjour"
>>> texte[0]
'B'
>>> texte[0] = 'M'
TypeError: 'str' object does not support item assignment
>>> texte
'Bonjour'
>>> type(texte)
<class 'str'>
>>> type(texte) == str
True
04° Que va-afficher le court programme suivant ? A quoi correspondent les trois arguments envoyés ?
1
2 |
|
...CORRECTION...
5
7
9
Pourquoi ?
Le premier argument (optionnel) correspond à la valeur de départ. Si on ne fournit qu'un seul argument, la valeur de départ est prise à 0 par défaut. Ainsi range(10)
revient à avoir taper range(0, 10)
.
Le deuxième argument correspond à la borne extrême exclue de l'intervalle. Ainsi range(0, 10)
veut dire de commencer à 0 et de finir à ... 9.
Le troisième argument envoyé correspond au pas entre chaque variation. Si on ne fournit pas, c'est qu'il vaut 1. Ainsi range(10)
veut dire range(0, 10, 1)
.
Ici, on commence donc à 5, on augmente de 2 en 2 et la borne limite exlue est 11. Donc 5, 7, 9 et c'est tout.
En résumé, trois possibilités de fournir un ensemble avec range :
range(borne_extreme_exclue)
range(valeur_initiale, borne_extreme_exclue)
range(valeur_initiale, borne_extreme_exclue, pas)
05° Compléter la fonction minimum pour qu'elle renvoie bien l'index du plus petit élément du tableau transmis en cherchant à partir de l'index 0. Tester votre fonction dans le Shell à l'aide de deux-trois appels de tests.
1
2
3
4
5
6
7
8
9
10
11
12 |
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 |
|
06° Compléter la fonction minimum pour qu'elle renvoie bien l'index du plus petit élément du tableau transmis en cherchant à partir d'un index égal au paramètre debut.
Un appel minimum(toto, 10)
veut donc dire de renvoyer l'index du minimum trouvé dans le tableau toto à partir de l'index 10.
Tester votre fonction dans le Shell à l'aide de deux-trois appels de tests.
1
2
3
4
5
6
7
8
9
10
11
12
13 |
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 |
|
07° Ecrire le prototype (pas le corps du code) d'une fonction intervertir qui doit modifier sur place un tableau en intervertissant les valeurs contenues sur deux index qui transmet en argument. Il faudra transmettre le tableau également.
Placer les demandes de types des paramètres dans la documentation de la fonction.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11 |
|
08° Idem mais en utilisant la méthode du typing.
1
2 |
|
...CORRECTION...
1
2
3
4
5
6 |
|
On remarquera que cette notation est plus courte mais qu'elle ne vaut pas une documentation avec quelques mots.
09° Compléter la fonction pour qu'elle réalise la tâche demandée en modifiant le tableau par effet de bord.
1
2
3
4
5
6
7
8
9
10
11 |
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13 |
|
10° Pourquoi ne trouve-t-on pas de return None
dans la correction alors que la postcondition impose de renvoyer None ?
...CORRECTION...
Tout simplement car si on ne place aucun return, on ne renvoie ... rien. Donc, c'est comme si on avait placé return None
.
11° Voici deux façons de créer un tableau de nombres aléatoires compris dans [0; 100].
1
2
3
4
5
6
7 |
|
Question : associer les tableaux serie1 puis serie2 au nom de leur méthode de création. Choisir parmi
- Extension
- Compression
- Compréhension
- Rédaction
...CORRECTION...
serie1 est créé par COMPREHENSION.
serie2 est créé par EXTENSION.
12° Rajouter ces variables dans votre programme et vérifier leurs contenus après l'avoir lancé.
...CORRECTION...
Vous devez obtenir quelque chose de ce type :
>>> serie1
[48, 98, 39, 92, 93, 18, 74, 8, 41, 55, 48, 3, 70, 12, 97, 62, 48, 30, 64, 63]
>>> serie2
[36, 99, 70, 33, 28, 92, 59, 26, 37, 46, 18, 13, 100, 51, 65, 80, 3, 81, 5, 86]
Revenons maintenant à notre problème de tri par sélection.
Algorithme de tri par sélection
debut est l'index (flèche en vert clair dans l'animation) de la case à remplir
POUR debut
variant de 0
à (longueur - 1)
index_min
← minimum(tableau, debut)
on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)
intervertir(tableau, debut, index_min)
on intervertit les valeurs situées aux index debut et index_min
Fin POUR
Renvoyer VIDE (∅)
13° Finaliser cet algorithme en créant la fonction tri_selection qui ne possède qu'un paramètre : le tableau à trier.
Tester ensuite votre code avec un test de ce type :
>>> serie1
[93, 55, 35, 58, 61, 44, 66, 55, 51, 3, 46, 11, 87, 35, 73, 27, 76, 51, 97, 61]
>>> tri_selection(serie1)
>>> serie1
[3, 11, 27, 35, 35, 44, 46, 51, 51, 55, 55, 58, 61, 61, 66, 73, 76, 87, 93, 97]
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 |
|
14° Utiliser cette version qui permet d'afficher les différentes étapes. Il faut appuyer sur ENTREE pour obtenir l'étape suivante.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 |
|
Nous sommes passés ici par des fonctions car cela permet de rendre le code final plus concis. Mais on aurait bien entendu pu s'en passer.
15° Tester cette version sans fonction à l'intérieur de la fonction elle-même. Du coup, on perd en visibilité dans la fonction elle-même : il faut lire le code pour savoir ce qu'il fait.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 |
|
✎ 16° Créer une fonction qui permet d'utiliser le tri par sélection pour trier le tableau en sens décroissant : du plus grand nombre au plus petit nombre.
✎ 17° Rajouter les lignes de code pour parvenir à lancer automatiquement les tests que vous aurez placer dans la documention. Il faudra donc utiliser le module doctest.
✎ 18° Rajouter des assertions pour vérifier les préconditions sur les types de paramètres.
Si vous ne vous souvenez plus comment ça marche, il faut aller revoir la FAQ de la leçon Python : Documenter et tester.
5 - FAQ
Activité publiée le 01 09 2020
Dernière modification : 19 09 2020
Auteur : ows. h.