TD 06 - Tris 1

1 Échauffement

1.1 Exercice 1

On considère un tableau \(T\) de \(n\) entiers (éventuellement avec des répétitions).

  1. Écrire l’algorithme de tri sélection.

  2. Tester votre algorithme sur l’exemple suivant : \(T = [2, 7, 5, 2, 7, 8, 5, 9]\)

  3. Écrire l’algorithme de tri à bulles.

    1. Tester votre algorithme sur l’exemple suivant : \(T = [2, 7, 5, 2, 7, 8, 5, 9]\)

    2. Tester votre algorithme sur l’exemple suivant : \(T = [2, 3, 5, 7, 8, 8, 9]\)

    3. Modifier votre algorithme pour que la complexité minimale soit en \(\Theta(n)\).

NoteRappel : Tri sélection

Principe : Chercher le minimum de la partie non triée et le placer en première position de cette partie.

Complexité : \(\Theta(n^2)\) dans tous les cas (meilleur, moyen, pire).

Stabilité : Non stable (peut modifier l’ordre relatif d’éléments égaux).

NoteRappel : Tri à bulles

Principe : Parcourir le tableau et échanger les éléments adjacents mal ordonnés.

Complexité : - Meilleur cas : \(\Theta(n)\) si tableau déjà trié (avec optimisation) - Pire cas : \(\Theta(n^2)\) si tableau trié en ordre inverse

Stabilité : Stable (conserve l’ordre relatif d’éléments égaux).

2 Au travail

2.1 Exercice 2 : Tri distance

On considère un tableau d’entiers T de taille n et un entier x. La distance d’un élément du tableau avec x est simplement la valeur absolue de la différence entre x et l’élément en question.

Exemple :

T = [3, 1, 5, 9, 4], x = 7
distance entre T[1] et x: |7 - 3| = 4
distance entre T[2] et x: |7 - 1| = 6
etc

  1. Écrire un algorithme MaxDistance(T,i,x) qui retourne l’indice de l’élément de T qui maximise la distance avec x parmi les éléments compris entre l’indice \(i\) et l’indice \(n\). Par exemple, avec les données précédentes MaxDistance(T,1,x) retournera 2 et MaxDistance(T,3,x) retournera 5.

  2. Écrire un algorithme de tri TriDistance(T,x) qui trie les éléments du tableau en fonction de leur distance à l’entier x, du plus éloigné au plus proche.

2.2 Exercice 3 : Tri cocktail

Le tri cocktail est une amélioration du tri à bulles visant à réduire le coût du pire cas en mélangeant les versions gauche-droite et droite-gauche. La complexité asymptotique n’est par contre pas modifiée.

  1. Rappeler quel est le pire cas du tri à bulles. Quel est le pire cas de la version de droite à gauche ?

  2. Proposer un algorithme de tri basé sur le tri à bulles alternant les parcours de droite à gauche puis de gauche à droite.

  3. Améliorer l’algorithme en tenant compte du dernier indice où une permutation a eu lieu.

AstucePrincipe du tri cocktail

Le tri cocktail (ou tri shaker) alterne les parcours : - Phase 1 : Du début vers la fin (fait remonter le max) - Phase 2 : De la fin vers le début (fait descendre le min)

Cela permet de traiter plus rapidement certains cas pathologiques du tri à bulles.

2.3 Exercice 4 : Tri en vague 🏠

Un tableau est dit trié en vague si chaque élément - hors éléments de début et de fin - est soit supérieur soit inférieur à ses deux voisins. Par exemple, le tableau [2,1,5,2,4,3] est trié en vague.

  1. Proposer un algorithme qui convertit un tableau trié en tableau trié en vague.

  2. Écrire un algorithme qui trie en vague un tableau quelconque. Est-il plus efficace de trier dans l’ordre un tableau quelconque puis de le trier en vague ou de le trier en vague directement ?

NoteExemples de tableaux triés en vague
  • [2,1,5,2,4,3] : 1 < 2 et 1 < 5 ✓, 5 > 1 et 5 > 2 ✓, 2 < 5 et 2 < 4 ✓
  • [2,4,1,3,0] : alternance pic/creux