Dans les exercices suivants, on voit quelques méthodes (les plus simples à programmer, mais pas les plus efficaces) pour trier (dans l’ordre croissant) une liste d’éléments comparables. Les fonctions demandées ne renvoient rien (ou plus exactement renvoient None) : elles modifient la liste passée en argument.
On utilisera la fonction suivante randlist({n,a,b}) renvoyant une liste peusdo-aléatoire de {n} entiers de l’intervalle {[a,b[}. Par défaut {a=100} et {b=1000} (et alors la fonction randlist renvoie des listes de nombres à trois chiffres):
|
1 2 3 4 5 6 |
def randlist(n,a=100,b=1000): from random import randrange return [randrange(a,b) for _ in range(n)] >>> randlist(10) [521, 753, 740, 141, 710, 598, 181, 607, 157, 931] |
| Exercice (Tri « bulle ») Le principe de la méthode du « tri bulle » est le suivant:
Écrire la fonction tri_bulle(L) qui trie sur place une liste {L} d’éléments comparables entre eux. |
| Exercice (Tri « sélection ») Le principe de la méthode du « tri sélection » est le suivant:
Écrire la fonction tri_selection(L) qui trie sur place une liste {L} d’éléments comparables entre eux. |
| Exercice (Tri « insertion ») Le principe de la méthode du « tri insertion » est le suivant:
Écrire la fonction tri_insertion(L) qui trie sur place une liste {L} d’éléments comparables entre eux. |
| Exercice (Tri « insertion dichotomique ») On peut améliorer l’efficacité de la procédure de tri par insertion, en recherchant la position d’insertion du {k}-ème élément de façon dichotomique dans l’intervalle qui va de {L[0]} à {L[k-1]}. Écrire la fonction tri_insertion_dicho(L) qui trie sur place une liste {L} d’éléments comparables entre eux. |