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 : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr, c'est plus de 2500 exercices et 200 problèmes (tous soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. dans une présentation fluide et professionnelle adaptée à toutes les tailles d'écran, pour une souscription de 20€ (un an) ou 30€ (deux ans).

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 : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr, c'est plus de 2500 exercices et 200 problèmes (tous soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. dans une présentation fluide et professionnelle adaptée à toutes les tailles d'écran, pour une souscription de 20€ (un an) ou 30€ (deux ans).

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 : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr, c'est plus de 2500 exercices et 200 problèmes (tous soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. dans une présentation fluide et professionnelle adaptée à toutes les tailles d'écran, pour une souscription de 20€ (un an) ou 30€ (deux ans).

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 : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr, c'est plus de 2500 exercices et 200 problèmes (tous soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. dans une présentation fluide et professionnelle adaptée à toutes les tailles d'écran, pour une souscription de 20€ (un an) ou 30€ (deux ans).