Exercices Python sur les tris

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):

Exercice (Tri “bulle”)
Le principe de la méthode du “tri bulle” est le suivant:

  • on parcourt la liste à trier (de longueur {n}), et dès qu’on rencontre deux éléments consécutifs qui ne sont pas dans le bon ordre, on les échange; à l’issue de ce parcours, l’élément maximum se retrouve à la fin de la liste.
  • on recommence un parcours sur les {n-1} premiers éléments, etc.
  • le dernier parcours se limite à comparer les deux premiers éléments.

Écrire la fonction tri_bulle(L) qui trie sur place une liste {L} d’éléments comparables entre eux.

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice (Tri “sélection”)
Le principe de la méthode du “tri sélection” est le suivant:

  • rechercher l’élément minimum, puis l’échanger avec le premier élément;
  • recommencer avec la liste des {n-1} éléments suivants;
  • ainsi de suite jusqu’à obtenir la liste trié(e).

Écrire la fonction tri_selection(L) qui trie sur place une liste {L} d’éléments comparables entre eux.

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Exercice (Tri “insertion”)
Le principe de la méthode du “tri insertion” est le suivant:

  • le premier élément constitue à lui seul une séquence déjà triée!
  • on place le deuxième élément par rapport au premier;
    on obtient ainsi une séquence de longueur 2 triée;
  • on insère le troisième élément par rapport aux deux premiers, etc

Écrire la fonction tri_insertion(L) qui trie sur place une liste {L} d’éléments comparables entre eux.

Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

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.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez :