Segmentation d’une matrice | AlgorithmeFacile

📜 Bac 2025 Principale – Section Sciences de l’informatique

Exercice 3 (4,75 points)

Soit une matrice M de nl * nc entiers, la segmentation d’une ligne i de la matrice M par rapport à l’élément e de la première colonne de cette ligne (e = M[i, 0]) consiste à placer à gauche de l’élément e tous les éléments qui lui sont inférieurs ou égaux et à sa droite tous les éléments qui lui sont strictement supérieurs.

Exemple :

Matrice M initiale

6	-4	12	11	5	3
4	-2	5	1	10	9
34	12	11	4	29	-3
12	-3	5	4	42	13

Matrice M après segmentation

6	-4	3	6	12	11
4	-2	1	4	5	10
12	11	4	29	-3	34
-3	5	4	12	42	13

En effet :
• Dans la première ligne (ligne 0), e = 6 (M[0,0]). Les valeurs inférieures ou égales à e sont : 6, -4 et 3, tandis que les valeurs supérieures sont : 12 et 11. Ainsi 6, -4 et 3 sont placées à gauche de e = 6 et 12, 11 sont placées à sa droite.
• Dans la troisième ligne (ligne 2), e = 34 (M[2,0]). Les valeurs inférieures ou égales à e sont : 12, 11, 4, 29 et -3. Aucune valeur ne lui est supérieure. Ainsi 12, 11, 4, 29 et -3 sont placées à sa gauche.

Travail demandé :

Écrire un algorithme d’une procédure Segmenter(T, nc) qui permet de segmenter un tableau T à une dimension de nc entiers par rapport à sa première case (T[0]).
En faisant appel à la procédure Segmenter, écrire un algorithme d’une procédure Partitionner(M, nl, nc) qui permet de segmenter toutes les lignes de la matrice M par rapport à la première colonne (colonne 0).

N.B: T et M sont respectivement de type Tab et Mat. Le candidat n’est pas appelé à dresser le tableau de déclaration pour définir les types Tab et Mat.

🎬 Simulation Interactive sur la Matrice de l’Exemple

Visualisation pas à pas de l’exécution de la procédure Partitionner sur la matrice M (4 × 6) :

Pivot (M[i,0]) Élément comparé M[i,j] Éléments ≤ Pivot Éléments > Pivot

Cliquez sur « Démarrer » pour exécuter la simulation pas à pas.

Vitesse : 800ms

💡 Correction

1) Procédure Segmenter (@T: Tab, nc: Entier)

Procédure Segmenter(@T: Tab, nc: Entier)
DEBUT
  v ← T[0]
  p ← 0
  Pour i de 1 à nc - 1 Faire
      Si T[i] <= v Alors
          Aux ← T[i]
          Pour j de i à p (pas = -1) Faire
              T[j] ← T[j - 1]
          Fin Pour
          T[p] ← Aux
          p ← p + 1
      Fin Si
  Fin Pour
FIN

TDO (Table des Déclarations des Objets) :

Objet	Type / Nature
v, p, i, Aux, j	Entier

2) Procédure Partitionner (@M: Mat, nl, nc: Entier)

Procédure Partitionner(@M: Mat, nl, nc: Entier)
DEBUT
  Pour i de 0 à nl - 1 Faire
      Pour j de 0 à nc - 1 Faire
          T[j] ← M[i, j]
      Fin Pour
      Segmenter(T, nc)
      Pour j de 0 à nc - 1 Faire
          M[i, j] ← T[j]
      Fin Pour
  Fin Pour
FIN

TDO (Table des Déclarations des Objets) :

Objet	Type / Nature
i, j	Entier
Segmenter	Procédure