TD 09 - Rangements

1 Drapeau Hollandais

1.1 Exercice 1

On considère un tableau \(T\) d’entiers de taille \(n\). Écrire un algorithme RangerMod3(T) de complexité \(\Theta(n)\) qui range les multiples de 3 au début du tableau, suivis des nombres dont le reste vaut 1 modulo 3 et enfin ceux dont le reste vaut 2 modulo 3.

NoteAlgorithme du drapeau hollandais

Le problème du drapeau hollandais (Dutch National Flag) a été proposé par Dijkstra. Il s’agit de trier un tableau contenant trois valeurs distinctes en un seul parcours.

Principe : Utiliser trois pointeurs pour diviser le tableau en trois zones : - Zone des éléments de type 0 (à gauche) - Zone des éléments de type 1 (au milieu) - Zone des éléments de type 2 (à droite)

Complexité : \(\Theta(n)\) en temps, \(O(1)\) en espace.

2 Rangement binaire

2.1 Exercice 2

On fait l’appel dans le cours en amphi de UE21. Chacun des \(n\) étudiants a un numéro entre 1 et \(n\) (tous différents bien sûr). On note dans un tableau “Présent” ou “Absent” dans la case correspondante.

  1. Écrire un algorithme Ranger(T) de complexité \(\Theta(n)\) qui trie le tableau T en mettant tous les Absents en premier. On pourra utiliser la fonction Echanger(T,i,j) vue en cours.

    Par exemple l’algorithme modifiera le tableau [Absent,Présent,Absent,Absent,Présent,Absent] en [Absent,Absent,Absent,Absent,Présent,Présent].

  2. Écrire un algorithme Appel(T) de complexité \(O(\log(n))\) qui prend en entrée un tableau déjà trié et renvoie le nombre de Présents dans le tableau.

    Par exemple pour l’entrée [Absent,Absent,Absent,Absent,Présent,Présent] l’algorithme renverra 2.

AstuceIndices
  • Question 1 : Utiliser deux pointeurs (début et fin) qui se rapprochent
  • Question 2 : Recherche dichotomique de la première occurrence de “Présent”

3 En plus

3.1 Exercice 3 : Drapeau Mauricien 🏠

On considère un tableau contenant des couleurs parmi les suivantes : rouge, bleu, jaune et vert.

Ce tableau est mélangé et peut contenir plusieurs occurrences de chaque couleur.

L’objectif est de trier ce tableau en respectant l’ordre officiel du drapeau de Maurice : rouge, bleu, jaune, vert.

Exemple :

  • Entrée : [vert, rouge, jaune, bleu, vert, bleu, rouge, jaune]
  • Sortie attendue : [rouge, rouge, bleu, bleu, jaune, jaune, vert, vert]

Proposer un algorithme de complexité \(\Theta(n)\).

AstuceIndice

Généralisation du drapeau hollandais à 4 couleurs. Utiliser 4 zones ou faire plusieurs passes.

Méthode 1 : Tri par comptage (compter chaque couleur puis reconstruire)

Méthode 2 : Extension du drapeau hollandais avec 4 pointeurs

ImportantRappel : Complexité linéaire

Un algorithme de tri en \(\Theta(n)\) est possible seulement si : - Le nombre de valeurs distinctes est fixe (petit) - Les valeurs sont dans un intervalle borné connu

Ces tris sont appelés tris non comparatifs (tri par comptage, tri par base, etc.)