Tri et recherche

Exercices ou programmes  corrigés (avec solution) sur les algorithmes des tris : Tri par sélection, tri par insertion, tri à bulle, tri par fusion et tri rapide en comparant entre ces tris avec le langage de programmation Python. Chaque solution/correction est enrichi par des commentaire explicatif pour rendre la correction plus claire.




Chercher une valeur dans une liste non triée (Recherche séquentielle)

Fonction Python chercher(v,L) qui retourne True si une valeur v existe dans une liste L ou qui retourne False sinon, v et L sont passés en paramètre.


Vérifier si une liste est triée

Fonction Python Est_trie( L ) qui retourne True si L est trié (soit en ordre croissant soit en ordre décroissant) et elle retourne False sinon.


Insérer un nombre dans une liste triée

Fonction Python inserer( n, L ) qui permet d'insérer un nombre n dans une liste L triée en ordre croissant, n et L sont passés en paramètres.



Recherche dichotomique - Recherche dans une liste triée -

Fonction recherche_dichotomique( v , L) qui retourne l'indice de l'élément recherché v si la valeur v existe dans la liste L, et -1 si v n'existe pas dans la liste L. la valeur v et la liste L sont passés en paramètres.

Une autre technique de recherche dans une liste triée est la recherche dichotomique au lieu de rechercher séquentielle (recherche linière - liste non triée -).


Tri par sélection

Fonction Python tri_par_selection( L ) qui retourne une liste L triée en utilisant l'algorithme de tri par sélection, L est une liste passé en paramètre.


Tri par insertion

Fonction Python tri_par_insertion( L ) qui retourne une liste L triée en utilisant l'algorithme de tri par insertion, L est une liste passée en paramètre.



Tri à bulle

Fonction Python tri_a_bulle( L ) qui retourne une liste L triée en utilisant l'algorithme de tri à bulle, L est une liste passée en paramètre.


Tri Rapide - quicksort -

Fonction Python tri_rapide(L) qui permet de trier une liste L en utilisant l'algorithme de tri rapide, L est une liste passée en paramètre.

Principe de Tri rapide

Le principe du tri rapide (en anglais quicksort) est de diviser la liste en deux sous listes telles que les éléments de la première soient inférieurs aux éléments de la seconde. On recommence jusqu'à avoir des sous-listes réduites à un seul élément.


Tri par fusion

Fonction Python tri_fusion(L) qui permet de trier une liste L en utilisant l'algorithme de tri par fusion, L est une liste passée en paramètre. Principe de Tri rapide Le principe du tri par fusion, comme le tri rapide, basé à nouveau d’un tri suivant le paradigme diviser pour régner dont le principe est le suivant:
  • On divise en deux moitiés la liste à trier.
  • On trie chacune d’entre elles.
  • On fusionne les deux moitiés obtenues pour reconstituer la liste triée.


Comparaison entre les tris: Insertion, sélection, à bulles, rapide et fusion

Programme Python qui compare la performance et la rapidité entre les tris déjà vus (Tri par sélection, par insertion, à bulles, rapide et fusion) en calculant le temps d'exécution de chaque tri sur une liste générée aléatoirement de taille 1000.