Les algorithmes avancés

1. Les algorithmes de tri

a. Définition

L’opération de tri permet d’ordonner les éléments d’un tableau en ordre croissant ou en ordre décroissant.

b. Tri par sélection

Soit le tableau T1 suivant, on demande de trier ses éléments en ordre croissant.

Principe

Le tri par sélection consiste à :

1. Chercher la valeur minimale à partir de la ième position
2. Permuter la valeur minimale trouvée avec la ième valeur du tableau
3. Refaire les étapes 2 et 3 pour i de 1 à n-1

Algorithme

DEF PROC Tri_Selection(var t : tab ; n:entier)
  Pour i de 1 à (n-1) Faire
    indmin ⟵ Fn Minimum(t, i, n)
    Si indmin ≠ i Alors
      Proc Permuter(t[i], t[indmin])
    Fin Si
  Fin Pour
Fin Tri_Selection

DEF FN Minimum(var t : tab ; d, f :entier):entier
  m ⟵ d
  Pour i de (d+1) à f Faire
    Si t[i] < t[m] Alors
      m ⟵ i
    Fin Si
  Fin Pour
  Minimum ⟵ m
Fin Minimum

DEF PROC Permuter(var a, b : entier)
  t ⟵ a
  a ⟵ b
  b ⟵ t
Fin Permuter

Activité 1

Écrire un programme qui saisit un tableau de N réels (avec 3 ≤ N ≤ 20). Il permet par la suite de mettre les éléments du tableau en ordre croissant en utilisant la méthode de tri par sélection, puis affiche le tableau.

P.P

Début PP
  Proc Saisir(n)
  Proc Remplir(t, n)
  Proc Tri_Selection(t, n)
  Proc Afficher(t, n)
Fin PP

Procédure Saisir

DEF Proc Saisir(var n : entier)
  Répéter
    Ecrire("Donner n [3, 20] : ")
    Lire(n)
  Jusqu’à (n dans [3..20])
Fin Saisir

Procédure Remplir

DEF Proc Remplir(var t : tab ; n : entier)
  Pour i de 1 à n Faire
    Ecrire("Donner t[", i, "] : ")
    Lire(t[i])
  Fin Pour
Fin Remplir

Procédure Afficher

DEF Proc Afficher(t : tab ; n : entier)
  Pour i de 1 à n Faire
    Ecrire(t[i])
  Fin Pour
Fin Remplir

c. Tri à bulles

Principe

1. Comparer deux éléments successifs du tableau
2. Permuter si les deux éléments ne sont pas dans le bon ordre
3. Refaire les étapes 1 et 2 (n-1) fois pour tous les éléments du tableau

Algorithme

DEF PROC Tri_Bulles(var t : tab ; n:entier)
  { étape 3 }
  Pour i de 1 à (n-1) Faire
    Pour j de 1 à (n-1) Faire
      { étape 1 }
      Si t[j] > t[j+1] Alors
        { étape 2 }
        Proc Permuter(t[j], t[j+1])
      Fin Si
    Fin Pour
  Fin Pour
Fin Tri_Bulles

d. Tri par insertion

Principe

1. Supposer que la première partie du tableau (pour les indices inférieurs à i) est triée
2. Sortir l’élément n° i du tableau (nommé k ⟵ t[i])
3. Comparer cet éléments k avec les éléments d’indices inférieur (j є [1, i-1])
4. Décaler toutes les valeurs supérieures à l’élément k (t[j] > k)
5. Insérer k après le première valeur qui lui est inférieure.

Algorithme

DEF PROC Tri_Insertion(var t : tab ; n:entier)
  { étape 1 }
  Pour i de 2 à n Faire
    { étape 2 }
    k ⟵ t[i]

    { étape 3 }
    j ⟵ i – 1
    Tantque (j > 0) et (t[j] > k) Faire
      { étape 5 }
      t[j+1] ⟵ t[j]
      j ⟵ j – 1
    Fin Tantque

    { étape 5 }
    t[j + 1] ⟵ k
  Fin Pour
Fin Tri_Insertion

2. Les algorithmes de recherche

a. Définition

Les algorithmes de recherche sont utilisés pour retrouver une valeur dans un tableau, le tableau peut être ordonné ou non.

b. Recherche Séquentielle

Principe

Parcourir le tableau à partir de la première valeur jusqu’à trouver la valeur recherchée ou parcourir tout le tableau. Si la valeur est retrouvée on retourne son indice dans le tableau ou on peut aussi retourner un booléen pour vérifier l’existence de l’élément.

Algorithme Recherche

DEF FN Recherche(val : entier ; t : tab ; n:entier):entier
  pos ⟵ -1
  i ⟵ 1
  Tantque (pos = -1) et (i ≤ n) Faire
    Si t[i] = val Alors
      pos ⟵ i
    Fin Si
    i ⟵ i + 1
  Fin Tantque
  Recherche ⟵ pos
Fin Recherche

Algorithme Existe

DEF FN Existe(val : entier ; t : tab ; n:entier):booléen
  trouve ⟵ faux
  i ⟵ 1
  Tantque (non trouve) et (i ≤ n) Faire
    trouve ⟵  t[i] = val 
    i ⟵ i + 1
  Fin Tantque
  Existe ⟵ trouve
Fin Existe

c. Recherche Dichotomique

Principe

La recherche dichotomique est opérée sur un tableau trié (ordonné), par exemple en ordre croissant.

On suppose que la variable d indique l’indice du premier élément du tableau et que f indique l’indice du dernier élément du tableau.

1. Calculer l’indice de l’élément m au centre : m ⟵ (d + f) div 2
2. Si t[m] est égale à la valeur recherchée l’algorithme se termine
3. Si t[m] est inférieur à la valeur recherchée on recherche dans la partie droite du tableau c’est-à-dire d ⟵ m + 1
4. Si t[m] est supérieur à la valeur recherchée on recherche dans la partie droite du tableau c’est-à-dire f ⟵ m – 1

Algorithme

DEF FN RechercheDicho(val : entier ; t : tab ; n:entier):entier
  pos ⟵ -1
  d ⟵ 1
  f ⟵ n
  Répéter
    m ⟵ (d + f) div 2
    Si t[m] = val Alors Pos ⟵ m
    Sinon Si t[m] < val Alors d ⟵ m + 1
    Sinon f ⟵ m – 1
    Fin Si
  Jusqu’à (pos ≠ 0) ou (f < d)
  Recherche ⟵ pos
Fin Recherche