Exercices☘
Exercice☘
Appliquer le tri par insertion de la page précédente à la liste:
fruits = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine',
'prune', 'groseille', 'framboise']
et vérifier ainsi que notre fonction de tri fonctionne également sur les chaînes de caractères.
Note
En évitant les lettres accentuées et les majuscules, la comparaison python entre deux mots correspond à l'ordre alphabétique.
Solution
def rechercheIndicePivot(tab, k):
"""
tab -- liste d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant
renvoie le plus petit indice i ( 0 <= i <= k-1)
tel que tab[i] >= tab[k]
et renvoie k si un tel indice n'existe pas.
"""
valeur = tab[k]
for indice in range(0, k):
if tab[indice] >= valeur: return indice
return k
def insertion(tab, k):
"""
tab -- liste d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant
Modifie tab, en sortie:
- tab contient les mêmes éléments qu'en entrée
- tab[0..k] est triée en ordre croissant
- Chaque élément de tab[k+1..] est inchangé.
"""
valeur = tab[k]
# on calcule l'indice où placer valeur:
indicePivot = rechercheIndicePivot(tab, k)
# on remonte d'un rang tous les éléments >= valeur:
for j in range(k-1, indicePivot-1, -1):
tab[j+1] = tab[j]
# on place valeur à sa nouvelle position:
tab[indicePivot] = valeur
def triInsertion(tab):
"""
tab -- liste d'entiers
Modifie tab en triant ses éléments en ordre croissant
(fonction à effet de bord, ne renvoie rien)
"""
for k in range(1, len(tab)):
insertion(tab, k)
#### TESTS
fruits = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine',
'prune', 'groseille', 'framboise']
triInsertion(fruits)
print(fruits)
On obtient:
['abricot', 'brugnon', 'cerise', 'framboise', 'groseille', 'kiwi', 'nectarine', 'noisette', 'noix', 'orange', 'poire', 'pomme', 'prune']
Exercice☘
On dispose de séries de notes d'élèves. Par exemple:
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...
On aimerait maintenant trier les résultats des élèves suivant l'ordre croissant des moyennes.
Reprenez nos fonctions rechercheIndicePivot, insertion et triInsertion
et apporter les modifications nécessaires afin que l'on puisse facilement obtenir
ce tri suivant les moyennes.
Aide
Une modification de rechercheIndicePivotsuffit, il n'y a pas besoin d'apporter de modification
à insertion et à triInsertion.
Solution
def moyenne(tab):
"""
tab -- liste de notes
renvoie la moyenne des notes.
>>> moyenne([8, 14, 11])
11
"""
s = 0
for note in tab:
s += note
return s/len(tab)
def rechercheIndicePivot(tab, k):
"""
tab -- liste de listes d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant des moyennes
renvoie le plus petit indice i ( 0 <= i <= k-1)
tel que moyenne(tab[i]) >= moyenne(tab[k])
et renvoie k si un tel indice n'existe pas.
"""
valeur = moyenne(tab[k])
for indice in range(0, k):
if moyenne(tab[indice]) >= valeur: return indice
return k
def insertion(tab, k):
"""
tab -- liste de listes d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant des moyennes
Modifie tab, en sortie:
- tab contient les mêmes éléments qu'en entrée
- tab[0..k] est triée en ordre croissant des moyennes
- Chaque élément de tab[k+1..] est inchangé.
"""
valeur = tab[k]
# on calcule l'indice où placer valeur:
indicePivot = rechercheIndicePivot(tab, k)
# on remonte d'un rang tous les éléments >= valeur:
for j in range(k-1, indicePivot-1, -1):
tab[j+1] = tab[j]
# on place valeur à sa nouvelle position:
tab[indicePivot] = valeur
def triInsertion(tab):
"""
tab -- liste de listes d'entiers
Modifie tab en triant ses éléments en ordre croissant des moyennes
(fonction à effet de bord, ne renvoie rien)
"""
for k in range(1, len(tab)):
insertion(tab, k)
#### TESTS
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
triInsertion(notes)
print(notes)
for r in notes:
print(f"Moyenne de {r}: {moyenne(r)}.")
Exercice (facultatif)☘
On dispose de séries de notes d'élèves. Par exemple:
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...
On aimerait trier les résultats des élèves suivant différents critères. Notamment on aimerait obtenir le "rang" de chaque élève à chacun des contrôles. Il nous faut donc trier les listes de notes suivant la colonne 0 (ce qui donnera les rangs au premier contrôle), puis trier les listes de notes suivant la colonne 1 (rangs au second contrôle), etc...
Note
La note d'indice 1 de l'élève d'indice 0 s'obtient par:
>>> notes[0][1]
12
Modifier les fonctions rechercheIndicePivot, insertion et triInsertion en leur ajoutant un paramètre
colonne et apporter les autres modifications nécessaires afin que l'on puisse facilement obtenir
ces tris suivant les colonnes.
>>> notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
>>> triInsertion(notes, 0) # tri suivant la première note
>>> notes
[[2, 18, 15], [8, 12, 9], [10, 11, 12], [14, 13, 17]]
>>> triInsertion(notes, 1) # tri suivant la seconde note
>>> notes
[[10, 11, 12], [8, 12, 9], [14, 13, 17], [2, 18, 15]]
>>> triInsertion(notes, 2) # tri suivant la troisième note
>>> notes
[[8, 12, 9], [10, 11, 12], [2, 18, 15], [14, 13, 17]]
Solution
def rechercheIndicePivot(tab, k, colonne):
"""
tab -- liste de listes d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant
suivant les éléments de colonne
renvoie le plus petit indice i ( 0 <= i <= k-1)
tel que tab[i][colonne] >= tab[k][colonne]
et renvoie k si un tel indice n'existe pas.
"""
valeur = tab[k][colonne]
for indice in range(0, k):
if tab[indice][colonne] >= valeur: return indice
return k
def insertion(tab, k, colonne):
"""
tab -- liste de listes d'entiers,
k -- entier, 0 < k < len(tab)
précondition: tab[0..k-1] est triée en ordre croissant
suivant les éléments de colonne
Modifie tab, en sortie:
- tab contient les mêmes éléments qu'en entrée
- tab[0..k] est triée en ordre croissant suivant les éléments de colonne
- Chaque élément de tab[k+1..] est inchangé.
"""
valeur = tab[k]
# on calcule l'indice où placer valeur:
indicePivot = rechercheIndicePivot(tab, k, colonne)
# on remonte d'un rang tous les éléments >= valeur:
for j in range(k-1, indicePivot-1, -1):
tab[j+1] = tab[j]
# on place valeur à sa nouvelle position:
tab[indicePivot] = valeur
def triInsertion(tab, colonne):
"""
tab -- liste de listes d'entiers
Modifie tab en triant ses éléments en ordre croissant suivant les éléments de colonne
(fonction à effet de bord, ne renvoie rien)
"""
for k in range(1, len(tab)):
insertion(tab, k, colonne)
#### TESTS
notes = [[8,12,9], [2,18,15], [14,13,17], [10,11,12]]
triInsertion(notes, 2)
print(notes)