Les algorithmes de tri et de recherche

Objectifs

À la fin de ce chapitre, l’élève doit être capable de :

• trier un tableau d’entiers ou de chaînes par ordre croissant ou décroissant, selon quatre méthodes ;
• dérouler à la main chacune de ces méthodes sur un petit tableau ;
• rechercher un élément dans un tableau, de façon séquentielle ou dichotomique ;
• choisir une méthode de recherche selon que le tableau est trié ou non ;
• comparer les méthodes de tri selon le travail qu’elles effectuent.

Plan du chapitre

1. Introduction
2. Vocabulaire et exemple du chapitre
3. Le tri à bulles
4. Le tri par sélection
5. La recherche d’un élément
6. Le tri par insertion
7. Le tri shell
8. Comparaison des quatre tris
9. Les erreurs les plus fréquentes
10. Retenons

Les parties 3, 4 et 5 sont des rappels de 3ᵉ année ; les parties 6 et 7 sont nouvelles en 4ᵉ année.

1. Introduction

Activité 1

Un lycée compte 1 000 candidats au baccalauréat de la session 2027. Leurs noms sont rangés dans un tableau. Un parent vient demander si le nom de sa fille figure dans la liste.

Questions

1. La liste est dans l’ordre des inscriptions. Combien de noms faut-il examiner, au pire, pour répondre ?
2. La liste est maintenant dans l’ordre alphabétique. On ouvre la liste en son milieu : que peut-on conclure en comparant le nom cherché au nom trouvé à cet endroit ?
3. En répétant ce procédé, combien de noms faut-il examiner, au pire ?

Réponse

Dans une liste en désordre, rien n’indique où se trouve le nom : il faut examiner les noms un par un, soit 1 000 noms au pire, lorsque le nom est absent ou placé en dernier.

Dans une liste triée, une seule comparaison avec le nom du milieu élimine la moitié de la liste : si le nom cherché vient avant dans l’alphabet, il ne peut se trouver que dans la première moitié, sinon dans la seconde. En répétant ce procédé, la partie restante est divisée par deux à chaque étape : 1 000, 500, 250, 125, 62, 31, 15, 7, 3, 1. Il suffit d’examiner 10 noms au pire.

Trier un tableau a donc un intérêt immédiat : cela rend la recherche beaucoup plus rapide. Ce chapitre étudie les deux questions ensemble : comment trier un tableau, et comment y rechercher un élément.

2. Vocabulaire et exemple du chapitre

2.1 Trier un tableau

Définition. Trier un tableau, c’est réorganiser ses éléments de façon qu’ils soient rangés dans un ordre donné : croissant, du plus petit au plus grand, ou décroissant, du plus grand au plus petit.

Toutes les méthodes de ce chapitre trient le tableau sur place : elles ne créent pas de second tableau, elles déplacent les éléments à l’intérieur du tableau lui-même. Le tableau est donc passé par référence (par adresse) à la procédure de tri : @T.

Pour décrire le travail d’une méthode, on utilise quatre mots.

La permutation de deux cases s’écrit toujours en trois affectations :

Aux ← T[i]
T[i] ← T[j]
T[j] ← Aux

Remarque importante. L’ordre des trois affectations est imposé. Écrire T[i] ← T[j] en premier effacerait définitivement l’ancienne valeur de T[i].

2.2 L’exemple du chapitre

Toutes les méthodes du chapitre sont déroulées sur le même tableau de 7 entiers, afin de pouvoir les comparer à la fin :

Après le tri par ordre croissant, il doit contenir :

Les modules du chapitre utilisent le type suivant :

TDNT

Pour chaque méthode, on comptera le nombre de parcours, de comparaisons et de permutations ou de décalages nécessaires pour trier ce tableau.

2.3 Trier des chaînes de caractères

Les chaînes se comparent avec les mêmes opérateurs que les nombres : <, >, =. La comparaison se fait caractère par caractère, de gauche à droite, selon le code ASCII : "Amine" < "Chaima" est vrai, puisque Ord("A") = 65 est inférieur à Ord("C") = 67.

Toutes les méthodes de ce chapitre s’appliquent donc sans modification à un tableau de chaînes : seul le type du tableau change.

Remarque importante. Les majuscules ont des codes plus petits que les minuscules : "amine" < "Yasmine" est faux, puisque Ord("a") = 97 est supérieur à Ord("Y") = 89. Pour trier des noms dans l’ordre alphabétique, ils doivent être écrits de la même façon, par exemple avec une majuscule initiale.

3. Le tri à bulles

3.1 Principe

On parcourt le tableau en comparant chaque élément à son voisin de droite ; s’ils sont dans le mauvais ordre, on les permute. À la fin d’un parcours, le plus grand élément rencontré est arrivé en dernière position, comme une bulle qui remonte à la surface. On recommence les parcours tant qu’un parcours a produit au moins une permutation.

Premier parcours sur l’exemple du chapitre

Après ce premier parcours, le plus grand élément, 9, occupe la dernière case.

3.2 Méthode 1 : répéter tant qu’il y a des permutations

Procédure Tri_Bulles (@T : Tab, n : Entier)
DEBUT
    Répéter
        Permut ← Faux
        Pour i de 0 à n - 2 Faire
            Si T[i] > T[i + 1] Alors
                Aux ← T[i]
                T[i] ← T[i + 1]
                T[i + 1] ← Aux
                Permut ← Vrai
            FinSi
        Fin Pour
    Jusqu'à Non(Permut)
FIN

TDOL

La variable Permut est un drapeau : elle passe à Vrai dès qu’une permutation a lieu. Un parcours qui la laisse à Faux prouve que le tableau est trié.

Trace sur l’exemple du chapitre : état du tableau à la fin de chaque parcours.

Le parcours 5 ne produit aucune permutation : Permut reste à Faux et le tri s’arrête. Bilan : 5 parcours, 30 comparaisons, 11 permutations.

3.3 Méthode 2 : la forme de référence en 4ᵉ année

La méthode 1 compare à chaque parcours tout le tableau, y compris la fin, qui est déjà en place : après le parcours 1, la case 6 contient définitivement 9 ; après le parcours 2, les cases 5 et 6 contiennent définitivement 8 et 9. La méthode 2 réduit la zone parcourue d’une case à chaque fois, en décrémentant n après chaque parcours : n représente alors le nombre de cases qui restent à trier.

Procédure Tri_Bulles (@T : Tab, n : Entier)
DEBUT
    Répéter
        Permut ← Faux
        Pour i de 0 à n - 2 Faire
            Si T[i] > T[i + 1] Alors
                Aux ← T[i]
                T[i] ← T[i + 1]
                T[i + 1] ← Aux
                Permut ← Vrai
            FinSi
        Fin Pour
        n ← n - 1
    Jusqu'à Non(Permut) Ou (n = 1)
FIN

TDOL

Trace sur l’exemple du chapitre. Les cases entre crochets sont celles que le parcours a placées définitivement : elles ne seront plus parcourues.

Bilan : 5 parcours, 20 comparaisons, 11 permutations. Les permutations sont les mêmes que dans la méthode 1 ; seules les comparaisons inutiles ont disparu : 20 au lieu de 30.

Remarque importante. Le paramètre n est passé par valeur : la procédure travaille sur une copie de n. La décrémenter ne modifie pas la variable n du programme appelant, qui garde la taille du tableau ; seul le tableau T, passé par référence (par adresse), est modifié.

Remarque importante. La condition d’arrêt est une disjonction : on s’arrête si plus rien ne permute, ou s’il ne reste qu’une case à trier. Sans Ou (n = 1), un tableau qui permute jusqu’au dernier parcours utile en ferait un de plus, vide, avec la borne n - 2 = -1.

En Python

def Tri_Bulles(T, n):
    Permut = True
    while Permut and n > 1:
        Permut = False
        for i in range(n - 1):
            if T[i] > T[i + 1]:
                Aux = T[i]
                T[i] = T[i + 1]
                T[i + 1] = Aux
                Permut = True
        n = n - 1

4. Le tri par sélection

4.1 Principe

On sélectionne le plus petit élément du tableau et on le place dans la première case, par une permutation. Puis on sélectionne le plus petit des éléments restants et on le place dans la deuxième case, et ainsi de suite jusqu’à l’avant-dernière case. La dernière case contient alors forcément le plus grand élément.

4.2 Algorithme

Procédure Tri_Selection (@T : Tab, n : Entier)
DEBUT
    Pour i de 0 à n - 2 Faire
        posmin ← i
        Pour j de i + 1 à n - 1 Faire
            Si T[j] < T[posmin] Alors
                posmin ← j
            FinSi
        Fin Pour
        Si posmin ≠ i Alors
            Aux ← T[i]
            T[i] ← T[posmin]
            T[posmin] ← Aux
        FinSi
    Fin Pour
FIN

TDOL

La boucle intérieure est la recherche de la position du minimum, déjà rencontrée avec la fonction pos_min_tab, mais limitée à la partie du tableau qui commence en i.

4.3 Trace sur l’exemple du chapitre

Les cases entre crochets sont définitivement placées.

Bilan : 6 parcours, 21 comparaisons, 3 permutations. Le tri par sélection fait toujours le même nombre de comparaisons, quel que soit l’ordre de départ, mais très peu de permutations : au plus une par parcours.

En Python

def Tri_Selection(T, n):
    for i in range(n - 1):
        posmin = i
        for j in range(i + 1, n):
            if T[j] < T[posmin]:
                posmin = j
        if posmin != i:
            Aux = T[i]
            T[i] = T[posmin]
            T[posmin] = Aux

5. La recherche d’un élément

5.1 La recherche séquentielle

On examine les éléments un par un, du premier au dernier, jusqu’à trouver l’élément cherché ou atteindre la fin du tableau. Cette méthode s’applique à n’importe quel tableau, trié ou non.

Elle s’écrit de quatre façons, toutes correctes : deux avec la boucle Tant que, deux avec la boucle Répéter … Jusqu'à.

Méthode 1 : avec un drapeau

Fonction Recherche_sequentielle (T : Tab, n, x : Entier) : Booléen
DEBUT
    Trouve ← Faux
    i ← 0
    Tant que (i < n) Et (Non(Trouve)) Faire
        Si T[i] = x Alors
            Trouve ← Vrai
        Sinon
            i ← i + 1
        FinSi
    Fin Tant que
    Retourner Trouve
FIN

TDOL

Méthode 2 : la condition dans la boucle

Fonction Recherche_sequentielle (T : Tab, n, x : Entier) : Booléen
DEBUT
    i ← 0
    Tant que (i < n) Et (T[i] ≠ x) Faire
        i ← i + 1
    Fin Tant que
    Retourner i < n
FIN

TDOL

Dans la méthode 2, la boucle s’arrête pour l’une des deux raisons de sa condition. Si elle s’arrête parce que T[i] = x, alors i < n ; si elle s’arrête parce que i = n, l’élément est absent. La fonction retourne donc le résultat de la comparaison i < n.

**Méthode 3 : Répéter avec un drapeau**

Fonction Recherche_sequentielle (T : Tab, n, x : Entier) : Booléen
DEBUT
    Trouve ← Faux
    i ← 0
    Répéter
        Si T[i] = x Alors
            Trouve ← Vrai
        Sinon
            i ← i + 1
        FinSi
    Jusqu'à (Trouve) Ou (i = n)
    Retourner Trouve
FIN

TDOL

**Méthode 4 : Répéter avec la condition d’arrêt**

Fonction Recherche_sequentielle (T : Tab, n, x : Entier) : Booléen
DEBUT
    i ← -1
    Répéter
        i ← i + 1
    Jusqu'à (T[i] = x) Ou (i = n - 1)
    Retourner T[i] = x
FIN

TDOL

Dans la méthode 4, i vaut au plus n - 1 à la sortie de la boucle : on ne peut donc pas retourner i < n, qui serait toujours vrai. On retourne le résultat du test T[i] = x. Lorsque x est le dernier élément, les deux conditions d’arrêt sont vraies en même temps, et c’est encore ce test qui donne la bonne réponse : sur l’exemple du chapitre, la recherche de 3 et la recherche de 4 s’arrêtent toutes deux en i = 6, la première retourne Vrai, la seconde Faux.

Remarque importante. La boucle Répéter exécute son corps au moins une fois : les méthodes 3 et 4 lisent T[0] avant tout test. Elles supposent donc que le tableau contient au moins un élément, n ≥ 1. Les méthodes 1 et 2, avec Tant que, fonctionnent aussi sur un tableau vide : c’est pourquoi on les préfère.

Trace sur l’exemple du chapitre, T = 6 2 8 5 1 9 3.

Recherche de 5

Recherche de 4

La recherche de 5 s’arrête en i = 3 et retourne Vrai, après 4 comparaisons. La recherche de 4 parcourt tout le tableau et retourne Faux, après 7 comparaisons. Une recherche sans succès examine toujours tous les éléments.

En Python

Python n’a pas de boucle Répéter … Jusqu'à : on traduit les méthodes écrites avec Tant que. Voici la méthode 2.

def Recherche_sequentielle(T, n, x):
    i = 0
    while (i < n) and (T[i] != x):
        i = i + 1
    return i < n

5.2 La recherche dichotomique

Lorsque le tableau est trié, on compare l’élément cherché à l’élément du milieu de la zone de recherche. Selon le résultat, on poursuit la recherche dans la moitié gauche ou dans la moitié droite, et l’on recommence. La zone de recherche, délimitée par les indices d et f, est divisée par deux à chaque tour.

Fonction Recherche_dichotomique (T : Tab, n, x : Entier) : Booléen
DEBUT
    d ← 0
    f ← n - 1
    Trouve ← Faux
    Tant que (d ≤ f) Et (Non(Trouve)) Faire
        Milieu ← (d + f) Div 2
        Si T[Milieu] = x Alors
            Trouve ← Vrai
        Sinon Si T[Milieu] > x Alors
            f ← Milieu - 1
        Sinon
            d ← Milieu + 1
        FinSi
    Fin Tant que
    Retourner Trouve
FIN

TDOL

La recherche dichotomique s’écrit aussi avec la boucle Répéter … Jusqu'à. La condition d’arrêt réunit les deux raisons de s’arrêter : l’élément est trouvé, ou la zone de recherche est vide.

Fonction Recherche_dichotomique (T : Tab, n, x : Entier) : Booléen
DEBUT
    d ← 0
    f ← n - 1
    Trouve ← Faux
    Répéter
        Milieu ← (d + f) Div 2
        Si T[Milieu] = x Alors
            Trouve ← Vrai
        Sinon Si T[Milieu] > x Alors
            f ← Milieu - 1
        Sinon
            d ← Milieu + 1
        FinSi
    Jusqu'à (Trouve) Ou (d > f)
    Retourner Trouve
FIN

Le TDOL est le même. Comme pour la recherche séquentielle, cette forme suppose n ≥ 1 : sur un tableau vide, le premier tour lirait T[0], qui n’existe pas.

Trace sur le tableau trié de l’exemple

Sur ce tableau de 7 éléments, la dichotomie conclut toujours en 3 tours au plus, contre 7 pour la recherche séquentielle. L’écart grandit avec la taille : 10 tours au plus pour 1 000 éléments, 20 tours au plus pour un million.

5.3 La condition indispensable : un tableau trié

Remarque importante. La recherche dichotomique ne s’applique qu’à un tableau trié. Sur un tableau non trié, elle ne signale aucune erreur : elle donne simplement une réponse fausse.

Exemple. On applique la recherche dichotomique au tableau non trié de l’exemple du chapitre, pour chercher 1.

La fonction retourne Faux, alors que 1 se trouve en T[4]. Au premier tour, la comparaison 5 > 1 a éliminé toute la moitié droite, parce qu’elle supposait que les éléments situés après 5 sont plus grands que 5. Sur ce tableau, la dichotomie déclare absents 4 des 7 éléments présents : 6, 8, 1 et 3.

C’est la raison d’être du couple tri et recherche : on trie une fois, puis chaque recherche est rapide.

En Python

def Recherche_dichotomique(T, n, x):
    d = 0
    f = n - 1
    Trouve = False
    while (d <= f) and (not Trouve):
        Milieu = (d + f) // 2
        if T[Milieu] == x:
            Trouve = True
        elif T[Milieu] > x:
            f = Milieu - 1
        else:
            d = Milieu + 1
    return Trouve

6. Le tri par insertion

6.1 Principe

C’est la méthode du joueur de cartes qui range sa main : il prend les cartes une par une et insère chacune à sa place parmi celles qu’il tient déjà, qui sont rangées.

Au début de l’étape i, la partie gauche du tableau, de T[0] à T[i - 1], est déjà triée. On retire T[i] dans une variable aux, on décale d’une case vers la droite tous les éléments de la partie triée qui sont plus grands que aux, puis on dépose aux dans la case libérée.

6.2 Algorithme

Procédure Tri_Insertion (@T : Tab, n : Entier)
DEBUT
    Pour i de 1 à n - 1 Faire
        aux ← T[i]
        j ← i
        Tant que (j > 0) Et (T[j - 1] > aux) Faire
            T[j] ← T[j - 1]
            j ← j - 1
        Fin Tant que
        T[j] ← aux
    Fin Pour
FIN

TDOL

Remarque importante. Le tri par insertion ne permute pas : il décale. La valeur à insérer est mise de côté dans aux avant les décalages, qui écrasent la case T[i], puis elle est déposée une seule fois, dans T[j].

La boucle Pour commence à 1 : une partie triée d’un seul élément, T[0], est triée par définition. La boucle Tant que s’arrête dès que l’on rencontre un élément inférieur ou égal à aux, ou que l’on atteint le début du tableau.

6.3 Trace sur l’exemple du chapitre

La case entre crochets est celle où aux vient d’être déposé.

**Détail de l’étape i = 3** : aux ← 5, la partie triée est 2 6 8.

Bilan : 6 parcours, 15 comparaisons, 11 décalages.

En Python

def Tri_Insertion(T, n):
    for i in range(1, n):
        aux = T[i]
        j = i
        while j > 0 and T[j - 1] > aux:
            T[j] = T[j - 1]
            j = j - 1
        T[j] = aux

7. Le tri shell

7.1 Principe

Le tri par insertion ne déplace un élément que d’une case à la fois. À l’étape i = 4 de l’exemple, le 1 a dû traverser quatre cases, au prix de quatre décalages, pour aller de T[4] à T[0].

Le tri shell, du nom de son inventeur Donald Shell, corrige ce défaut. C’est un tri par insertion qui compare d’abord des éléments distants de p cases, appelé le pas, pour déplacer rapidement les éléments loin de leur position. Le pas est ensuite réduit, jusqu’à 1 : le dernier parcours utile est alors un tri par insertion ordinaire, mais sur un tableau presque trié.

7.2 Algorithme

Procédure Tri_Shell (@T : Tab, n : Entier)
DEBUT
    p ← 1
    Tant que p < n Faire
        p ← 3 * p + 1
    Fin Tant que
    Tant que p ≥ 1 Faire
        p ← p Div 3
        Pour i de p à n - 1 Faire
            aux ← T[i]
            j ← i
            Tant que (j ≥ p) Et (T[j - p] > aux) Faire
                T[j] ← T[j - p]
                j ← j - p
            Fin Tant que
            T[j] ← aux
        Fin Pour
    Fin Tant que
FIN

TDOL

Comparé au tri par insertion, le corps de la boucle Pour est le même, où le pas 1 est remplacé par le pas p : j - 1 devient j - p, et j > 0 devient j ≥ p.

7.3 Le calcul du pas

Le pas ne dépend que de n. La première boucle parcourt la suite 1, 4, 13, 40, 121, …, où chaque terme vaut 3p + 1, et s’arrête sur le premier terme qui atteint ou dépasse n. La seconde boucle redescend cette suite par divisions entières par 3, avant chaque parcours.

**Pour n = 7**

La seconde boucle applique ensuite les pas 13 Div 3 = 4, puis 4 Div 3 = 1, puis 1 Div 3 = 0.

7.4 Trace sur l’exemple du chapitre

Parcours de pas 4. Les éléments comparés sont distants de 4 cases : T[0] et T[4], T[1] et T[5], T[2] et T[6].

Les cases entre crochets sont celles que le parcours a modifiées. Après le seul parcours de pas 4, le 1 a sauté directement de T[4] à T[0], et le 3 de T[6] à T[2] : il ne reste qu’une paire mal ordonnée, 9 et 8. Le parcours de pas 1 la corrige par un seul décalage.

Bilan : 3 parcours, 17 comparaisons, 3 décalages, contre 11 décalages pour le tri par insertion.

Le parcours de pas 0. Le dernier parcours s’exécute avec p = 0. La condition T[j - 0] > aux compare alors chaque élément à lui-même : elle est fausse d’emblée, et le tableau n’est pas modifié. Ce parcours coûte 7 comparaisons sur les 17 ; il est inutile, mais on le laisse s’exécuter pour garder l’algorithme simple.

7.5 Pourquoi le pas 3p + 1 ?

Le principe du tri shell fonctionne avec toute suite de pas qui se termine par 1. Mais toutes les suites ne se valent pas. La suite 3p + 1 est celle retenue dans ce cours, pour deux raisons :

• elle se calcule à partir de n seul, par deux boucles très courtes ;
• deux pas successifs, p et 3p + 1, ne sont jamais multiples l’un de l’autre, puisque (3p + 1) Mod p = 1 dès que p > 1 : un parcours ne se contente pas de refaire les comparaisons du précédent.

Une suite plus naturelle en apparence, qui divise le pas par 2 en partant de n Div 2, a un défaut : lorsque n est une puissance de 2, tous ses pas sont pairs sauf le dernier, et les éléments des cases paires ne sont jamais comparés à ceux des cases impaires avant le dernier parcours.

En Python

def Tri_Shell(T, n):
    p = 1
    while p < n:
        p = 3 * p + 1
    while p >= 1:
        p = p // 3
        for i in range(p, n):
            aux = T[i]
            j = i
            while j >= p and T[j - p] > aux:
                T[j] = T[j - p]
                j = j - p
            T[j] = aux

8. Comparaison des quatre tris

8.1 Bilan sur l’exemple du chapitre

Tableau de départ : 6 2 8 5 1 9 3.

8.2 Trier par ordre décroissant

Chacune des quatre méthodes trie par ordre décroissant en inversant la comparaison entre éléments, et rien d’autre :

Les comparaisons sur les indices, comme j > 0 ou i < n, ne changent pas.

Application résolue 1 — La liste d’appel

À la rentrée 2027, un professeur saisit les prénoms des élèves de son groupe dans l’ordre où ils se sont inscrits. Il veut obtenir la liste dans l’ordre alphabétique, retrouver rapidement un élève, et afficher les élèves dont le prénom commence par une lettre donnée.

Les prénoms sont rangés dans un tableau T de n chaînes de caractères, déclaré ainsi :

Exemple : n = 8.

Travail demandé

1. Écrire l’algorithme de la procédure Trier(T, n) qui trie le tableau T par ordre alphabétique, selon la méthode du tri par insertion.
2. Écrire l’algorithme de la fonction Position(T, n, p) qui retourne la position du prénom p dans le tableau T trié, ou -1 si ce prénom n’y figure pas. La recherche est dichotomique.
3. Écrire l’algorithme de la procédure Afficher_Initiale(T, n, c) qui affiche, à raison d’un prénom par ligne, les prénoms du tableau T trié qui commencent par la lettre c. Le parcours s’arrête dès que les prénoms suivants ne peuvent plus commencer par c.

N.B. Le tableau T est déjà rempli. On suppose que les prénoms sont distincts et commencent tous par une majuscule suivie de minuscules : le candidat n’est pas appelé à les vérifier.

Procédure Trier (@T : TabCh, n : Entier)
DEBUT
    Pour i de 1 à n - 1 Faire
        aux ← T[i]
        j ← i
        Tant que (j > 0) Et (T[j - 1] > aux) Faire
            T[j] ← T[j - 1]
            j ← j - 1
        Fin Tant que
        T[j] ← aux
    Fin Pour
FIN

Fonction Position (T : TabCh, n : Entier, p : Chaîne de caractères) : Entier
DEBUT
    d ← 0
    f ← n - 1
    pos ← -1
    Tant que (d ≤ f) Et (pos = -1) Faire
        Milieu ← (d + f) Div 2
        Si T[Milieu] = p Alors
            pos ← Milieu
        Sinon Si T[Milieu] > p Alors
            f ← Milieu - 1
        Sinon
            d ← Milieu + 1
        FinSi
    Fin Tant que
    Retourner pos
FIN

Procédure Afficher_Initiale (T : TabCh, n : Entier, c : Caractère)
DEBUT
    i ← 0
    Tant que (i < n) Et (T[i][0] < c) Faire
        i ← i + 1
    Fin Tant que
    Tant que (i < n) Et (T[i][0] = c) Faire
        Écrire_nl(T[i])
        i ← i + 1
    Fin Tant que
FIN

Rami
Rania

Application résolue 2 — Le concours de programmation

Le club d’informatique d’un lycée organise en 2027 un concours de programmation. Les scores des équipes, des entiers positifs, sont rangés dans un tableau S de n entiers. Le jury veut afficher le classement du meilleur au moins bon score, ajouter le score d’une équipe arrivée en retard sans refaire le tri, et vérifier si un score donné a été obtenu.

Exemple : n = 6.

Travail demandé

1. Écrire l’algorithme de la procédure Trier_Decroissant(S, n) qui trie le tableau S par ordre décroissant, selon la méthode du tri shell.
2. Écrire l’algorithme de la procédure Inserer(S, n, x) qui insère le score x dans le tableau S trié par ordre décroissant, de façon qu’il reste trié, et met à jour n.
3. Écrire l’algorithme de la fonction Existe(S, n, x) qui vérifie, par une recherche dichotomique, si le score x figure dans le tableau S trié par ordre décroissant.

N.B. Le tableau S est déjà rempli ; il est déclaré de type Tab. On suppose que S contient moins de 20 scores avant l’insertion : le candidat n’est pas appelé à le vérifier.

Procédure Trier_Decroissant (@S : Tab, n : Entier)
DEBUT
    p ← 1
    Tant que p < n Faire
        p ← 3 * p + 1
    Fin Tant que
    Tant que p ≥ 1 Faire
        p ← p Div 3
        Pour i de p à n - 1 Faire
            aux ← S[i]
            j ← i
            Tant que (j ≥ p) Et (S[j - p] < aux) Faire
                S[j] ← S[j - p]
                j ← j - p
            Fin Tant que
            S[j] ← aux
        Fin Pour
    Fin Tant que
FIN

Procédure Inserer (@S : Tab, @n : Entier, x : Entier)
DEBUT
    j ← n
    Tant que (j > 0) Et (S[j - 1] < x) Faire
        S[j] ← S[j - 1]
        j ← j - 1
    Fin Tant que
    S[j] ← x
    n ← n + 1
FIN

Fonction Existe (S : Tab, n, x : Entier) : Booléen
DEBUT
    d ← 0
    f ← n - 1
    Trouve ← Faux
    Tant que (d ≤ f) Et (Non(Trouve)) Faire
        Milieu ← (d + f) Div 2
        Si S[Milieu] = x Alors
            Trouve ← Vrai
        Sinon Si S[Milieu] < x Alors
            f ← Milieu - 1
        Sinon
            d ← Milieu + 1
        FinSi
    Fin Tant que
    Retourner Trouve
FIN

9. Les erreurs les plus fréquentes

Les erreurs suivantes sont relevées sur les algorithmes du cours. Chaque résultat a été obtenu en exécutant l’algorithme erroné sur l’exemple du chapitre, 6 2 8 5 1 9 3.

10. Retenons

Trier. Trier un tableau, c’est ranger ses éléments dans l’ordre croissant ou décroissant. Les tris du chapitre travaillent sur place : le tableau est passé par référence (par adresse), @T.

Quatre méthodes. Bulles : permuter les voisins mal ordonnés. Sélection : placer le minimum des éléments restants. Insertion : insérer chaque élément dans la partie triée. Shell : insertion avec un pas décroissant 3p + 1, jusqu’à 1.

Bulles en 4ᵉ année. La forme de référence réduit la zone parcourue par n ← n - 1, n étant passé par valeur, et s’arrête par Jusqu'à Non(Permut) Ou (n = 1).

Rechercher. La recherche séquentielle s’applique à tout tableau. La recherche dichotomique exige un tableau trié ; elle divise la zone de recherche par deux à chaque tour.

Décroissant. On inverse la comparaison entre éléments, jamais les comparaisons sur les indices.

Teste tes connaissances

Un quiz corrigé question par question, puis des flashcards pour mémoriser les notions du chapitre.