On veut donc trier un tableau ou pour nous une liste qu’on nomme ici t
.
t = [8, 6, 2, 9, 3, 4]
Questions 1 :
- Que vaut
len(t)
? - Que vaut
t[0]
?t[1]
? - Que vaut
t[5]
?t[6]
? - Que vaut
t[-1] ?
Réponses 1 :
Question 2 :
- Comment trouver l’indice du minimum de cette liste ?
t = [8, 6, 2, 9, 3, 4]
Réponse 2 :
En code, qu’est-ce que ça donne ?
def indice_minimum(liste): assert len(liste) > 0 i_min = ... for i in range(..., ......): if liste[...] < liste[...]: i_min = ... return ...
Question 3 :
- Compléter le code ci-dessus.
Pour le tester :>>> t = [8, 6, 2, 9, 3, 4] >>> indice_minimum(t) 2 >>>
Réponse 3 :
Question 4 :
- Comment intervertir les valeurs de deux variables
a
etb
enpython
?
Réponse 4 :
- En
python
, c’est plus facile que dans d’autres languages :>>> a = 42 >>> b = 21 >>> a, b (42, 21) >>> a, b = b, a # interversion >>> a, b (21, 42) >>> a 21 >>> b 42 >>> # c'est gagné 🙂
Le tri en lui même
Reprenons maintenant notre tri, comme sur la vidéo. Les étapes sont :
[8, 6, 2, 9, 3, 4] indice du minimum : 2 On intervertit les valeurs des rangs 0 et 2 [2, 6, 8, 9, 3, 4] indice du minimum : 4 On intervertit les valeurs des rangs 1 et 4 [2, 3, 8, 9, 6, 4] indice du minimum : 5 On intervertit les valeurs des rangs 2 et 5 [2, 3, 4, 9, 6, 8] indice du minimum : 4 On intervertit les valeurs des rangs 3 et 4 [2, 3, 4, 6, 9, 8] indice du minimum : 5 On intervertit les valeurs des rangs 4 et 5 [2, 3, 4, 6, 8, 9] >>>
On a donc deux boucles imbriquées (je proposerai un corrigé avec deux fonctions pour éviter cette lourdeur) :
- une boucle « extérieure » avec une indice
rang
qui parcourt la listet
an allant des rangs0
à4
ici, donc de0
àlen(t) - 2
en règle générale,- une boucle « intérieure » avec un indice
i
qui cherche l’indice du minimumi_min
, - on intervertit alors
t[rang]
ett[i_min]
après cette boucle « intérieure ».
- une boucle « intérieure » avec un indice
En pseudo-code, l’algorithme du tri par sélection est (source Wikipedia) :
procédure tri_selection(liste t) pour rang de 0 à len(t) - 2 i_min ← rang pour i de rang + 1 à len(t) - 1 si t[i] < t[i_min], alors i_min ← i fin pour si i_min ≠ rang, alors échanger t[rang] et t[i_min] fin pour fin procédure
Mieux comprendre le rôle des indices ? Une nouvelle vidéo :
Question 5 pour vendredi :
- programmer une fonction
tri_selection(t)
qui effectue ce tri. - déposer ce code dans la collecte prévue à cet effet sur mon bureau numérique.
Réponse 5, finalement samedi – CORRIGÉ :
Déception : seulement huit neuf codes rendus, mais aussi des satisfactions !
J’ai commenté individuellement sur MBN.
Version 1 – deux boucles imbriquées :
def tri_selection(t): # il faut une liste non vide assert len(t) > 0 print(t) # parcours de la liste jusqu'à l'avant dernier for rang in range(len(t) - 1): # recherche de l'indice du minimum # on initialise i_min = rang # on parcourt le reste de la liste for i in range(rang + 1, len(t)): # si on trouve plus petit ... if t[i] < t[i_min]: # ... alors l'indice change ! i_min = i print("indice du minimum :", i_min) if i_min != rang : # interversion : le minimum passe devant print("On intervertit les valeurs des rangs", rang, "et", i_min) t[rang], t[i_min] = t[i_min], t[rang] print(t) t = [8, 6, 2, 9, 3, 4] tri_selection(t)
Version 2 – en utilisant la fonction indice_minimum
:
def indice_minimum(liste, rang): # il faut une liste non vide assert len(liste) > 0 # on initialise i_min = rang # on parcourt le reste de la liste for i in range(rang + 1, len(liste)): # si on trouve plus petit ... if liste[i] < liste[i_min]: # ... alors l'indice change ! i_min = i # On renvoie l'indice du minimum return i_min def tri_selection(t): print(t) # parcours de la liste jusqu'à l'avant dernier for rang in range(len(t) - 1): # recherche de l'indice du minimum ind_min = indice_minimum(t, rang) print("indice du minimum :", ind_min) if ind_min != rang : # interversion : le minimum passe devant print("On intervertit les valeurs des rangs", rang, "et", ind_min) t[rang], t[ind_min] = t[ind_min], t[rang] print(t) t = [8, 6, 2, 9, 3, 4] tri_selection(t)
Besoin d’un autre regard ?
Suite de notre progression en NSI ?
- Corrigé et autre algorithme de tri vendredi.
- Salon de discussion discord lundi prochain le 23 mars à 11h00.
Bonjour !
Je n’ai pas compris un petit détail dans le pseudo-code de Wikipédia (ligne 4) :
pour i de rang + 1 à len(t) – 1
Pourquoi « len(t) -1 » ? Celui-ci n’est-t’il pas exclu ? J’ai essayé avec ce len(t) – 1 mais cela ne triait pas t[5] (qui est ici égal à 4). En revanche, avec len(t), mon code fonctionne. Je ne comprends pas pourquoi…
(j’ai cette même interrogation à la ligne 2 « pour rang de 0 à len(t) – 2 » où je ne comprends pas pourquoi « – 2 » et non « – 1 »)
Merci de vos réponses 🙂
Une autre question sur ce pseudo-code, a-t-on besoin du « si i_min ≠ rang » (ligne 7) ?
Si la boucle intérieure commence à rang + 1, est-il possible que i_min soit égal à rang ?
Re-Bonjour,
Il n’est pas indispensable, le test de
i_min != rang
,en effet, on peut intervertir même si c’est le même, genre
a, a = a, a
😀Il est possible que
i_min == rang
puisqu’on initialisei_min = rang
avant la boucle.Merci de donner votre prénom quand vous commentez.
Je comprends mieux, merci beaucoup !
You’re welcome !
Bon courage !
Bonjour,
Pour i allant de 0 à 5 en pseudo-code se traduit par
En pseudo-code, on va jusqu’à
len(t) - 1
,en
python
, on arrête lerange
àlen(t)
.Merci de donner votre prénom quand vous commentez.