TD 07 - Tris 2

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 insertion.

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

    1. Écrire l’algorithme de tri par comptage.

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

NoteRappel : Tri insertion

Principe : Insérer chaque élément à sa place dans la partie déjà triée.

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

Stabilité : Stable

NoteRappel : Tri par comptage

Principe : Compter les occurrences de chaque valeur, puis reconstituer le tableau trié.

Complexité : \(\Theta(n + k)\) où \(k\) est l’étendue des valeurs.

Prérequis : Les éléments doivent être des entiers dans un intervalle connu.

Stabilité : Peut être stable selon l’implémentation.

2 Au travail

2.1 Exercice 2 : Sentinelle

ImportantExplication

Dans le tri par insertion classique, pour insérer chaque élément dans la partie triée à gauche, il faut tester si l’indice bas du tableau est atteint pour éviter d’accéder à une position hors limite (\(j > 1\)).

En plaçant une sentinelle (le minimum du tableau en première position), on garantit qu’on ne sort jamais du tableau : celle-ci arrête naturellement la procédure d’insertion, ce qui simplifie le code et évite un test supplémentaire à chaque étape.

  1. Placement de la sentinelle

    Écrire un algorithme qui échange le minimum du tableau avec la première case du tableau.

  2. Insertion avec sentinelle

    Compléter votre algorithme pour qu’il opère un tri par insertion, en utilisant la sentinelle pour stopper la boucle interne sans test sur l’indice.

2.2 Exercice 3

Le but de l’exercice est de proposer plusieurs méthodes pour résoudre le problème suivant :

NoteSpécification du problème
Problème Comptage
Entrée un tableau d’entiers de taille \(n\)
Sortie Le nombre d’entiers différents contenus dans le tableau

Exemple : pour l’instance [2,0,-1,7,0,0,4,2] la sortie attendue est 5.

  1. Proposer un algorithme naïf reposant sur la méthode qui consiste à vérifier pour chaque élément du tableau si celui-ci est présent ailleurs. Quelle est sa complexité ?

  2. Quelle est la complexité d’un tri comparatif optimal ? On suppose maintenant disposer d’un tel algorithme de tri : TRI.

    Proposer un nouvel algorithme de résolution du problème de comptage. Quelle est sa complexité ?

  3. On restreint le problème à des tableaux dont les éléments sont des entiers compris entre 1 et 500. Proposer un algorithme encore plus efficace. Quelle est sa complexité ?

  4. Que peut-on modifier dans l’algorithme précédent si les éléments sont des entiers compris entre -249 et 250 ?

AstuceIndices
  • Question 1 : Complexité en \(O(n^2)\) avec deux boucles imbriquées
  • Question 2 : Un tri optimal est en \(O(n \log n)\). Après tri, compter les différents est linéaire
  • Question 3 : Utiliser un tableau de booléens ou de compteurs indexé par les valeurs
  • Question 4 : Décalage d’indice pour gérer les valeurs négatives