Prérequis

Exercices

Tri insertion

Le tri insertion consiste à insérer au bon endroit le premier de la liste dans la queue récursivement triée de la liste.

  1. Implémenter le tri insertion

Tri pivot

Pour le tri pivot, on choisit un élément de la liste que l’on nomme pivot. On fabrique la liste des éléments inférieurs au pivot et la liste des éléments supérieurs. On trie chacune de ces listes et on raboute les morceaux pour obtenir une liste triée.

  1. Implémenter la fonction separe_aux.
  2. Étudier la complexité de cette fonction.
  3. Implémenter la fonction tri_pivot.
  4. Étudier la complexité de cette fonction en supposant les sous listes de taille moitié de la liste de départ.

Tri fusion

Le tri fusion se base sur l’idée de diviser la liste en deux moitiés, trier chaque moitiés pui fusionner les moitiés triées en une liste triée.

  1. Implémenter la fonction unzip qui prend une liste et fabrique d’une part la liste des éléments d’indice impair, d’autre part la liste des éléments d’indice pair. Le nom unzip vient de l’analogie avec une fermeture éclair : la liste initiale est la fermeture fermée, si on l’ouvre, on obtient d’un côté un élément sur deux, de l’autre côté les autres éléments.
  2. Calculer la complexité de cette fonction.
  3. Implémenter la fonction fusion qui prend deux listes triées et les fusionne en une seule liste triée.
  4. Calculer la complexité de cette fonction.
  5. Écrire la fonction tri_fusion qui réalise le tri en “unzippant” la liste, triant chacune des sous-listes obtenues puis fusionnant les listes triées.
  6. Calculer la complexité de ce tri.

Tri par arbres

On peut utiliser un arbre binaire de recherche pour trier une liste : on insère tous els éléments de la liste dans un abr. Puis on lit cet abr dans le bon ordre.

  1. Implémenter le tri par arbre