Recherche dichotomique et algorithmes de tri

La recherche dichotomique trouve une valeur dans un tableau trié en coupant à chaque étape la zone de recherche en deux ; les algorithmes de tri (par sélection, à bulles, par insertion) rangent les éléments d'un tableau dans l'ordre. Ce chapitre les présente en pseudo-code et en Python, avec leur trace pas à pas, et compare leur efficacité en comptant les comparaisons qu'ils effectuent.

Rappel : la recherche séquentielle

La recherche séquentielle examine les éléments un par un. Elle marche sur tout tableau, trié ou non, mais si la valeur est absente, elle examine tous les éléments : 1 000 comparaisons pour 1 000 éléments, un million pour un million. Quand le tableau est trié, on peut faire beaucoup mieux, comme tu le fais sans y penser pour trouver un mot dans un dictionnaire : on ouvre au milieu, et on sait de quel côté continuer.

La recherche dichotomique

On compare la valeur cherchée à l'élément du milieu de la zone de recherche :

• s'ils sont égaux, on a trouvé ;
• si la valeur cherchée est plus grande, elle ne peut être que dans la moitié droite : on y continue ;
• sinon, elle ne peut être que dans la moitié gauche.

La zone est délimitée par deux indices, deb et fin. À chaque tour, elle est divisée par deux. Si elle devient vide (deb > fin), la valeur est absente.

Fonction RechercheDicho(t : tableau d'entiers, x : entier) : entier
// Précondition : t est trié dans l'ordre croissant
// Renvoie l'indice de x dans t, ou -1 si x est absent
    deb ← 0
    fin ← longueur(t) - 1
    TantQue deb ≤ fin Faire
        milieu ← (deb + fin) DIV 2
        Si t[milieu] = x Alors
            Retourner milieu
        SinonSi t[milieu] < x Alors
            deb ← milieu + 1
        Sinon
            fin ← milieu - 1
        FinSi
    FinTantQue
    Retourner -1
FinFonction

def recherche_dicho(t, x):
    """Indice de x dans la liste triée t, ou -1 si x est absent."""
    deb = 0
    fin = len(t) - 1
    while deb <= fin:
        milieu = (deb + fin) // 2
        if t[milieu] == x:
            return milieu
        elif t[milieu] < x:
            deb = milieu + 1
        else:
            fin = milieu - 1
    return -1


t = [3, 8, 15, 23, 42, 56, 91]
print(recherche_dicho(t, 42), recherche_dicho(t, 10))

4 -1

Trace de la recherche de 42 dans [3, 8, 15, 23, 42, 56, 91] :

Combien de comparaisons ? Chaque tour divise la zone par deux. Partant de n éléments, il faut au plus environ log₂(n) + 1 tours : 4 pour 8 éléments, 10 pour 1 000, 20 pour un million. La recherche séquentielle en ferait respectivement 8, 1 000 et 1 000 000 dans le pire cas. C'est la différence entre un algorithme utilisable et un algorithme inutilisable sur de gros volumes, et c'est le principe des index des bases de données.

En Python, les entiers n'ont pas de limite, donc (deb + fin) // 2 est toujours juste. Dans les langages à entiers de taille fixe (C, Java, C#), la somme deb + fin peut déborder sur un tableau gigantesque ; on écrit alors deb + (fin - deb) / 2, qui donne le même milieu sans dépassement.

Pourquoi trier ?

Trier, c'est ranger les éléments d'un tableau dans l'ordre croissant (ou décroissant). Un tableau trié permet la recherche dichotomique, rend le minimum et le maximum immédiats (premier et dernier éléments), regroupe les doublons côte à côte, et s'affiche dans un ordre lisible. Le programme cite le « tri itératif » parmi les thèmes d'exercices : les trois tris qui suivent en sont les exemples classiques. Tous utilisent deux boucles imbriquées.

Le tri par sélection

À chaque étape, on sélectionne le plus petit élément de la partie non triée et on l'échange avec le premier élément de cette partie. La partie triée grandit d'une case par étape, à gauche.

Procédure TriSelection(E/S t : tableau d'entiers)
    n ← longueur(t)
    Pour i de 0 à n - 2 Faire
        // recherche de l'indice du minimum entre i et n - 1
        i_min ← i
        Pour j de i + 1 à n - 1 Faire
            Si t[j] < t[i_min] Alors
                i_min ← j
            FinSi
        FinPour
        // échange de t[i] et t[i_min]
        temp ← t[i]
        t[i] ← t[i_min]
        t[i_min] ← temp
    FinPour
FinProcédure

def tri_selection(t):
    """Trie la liste t sur place, dans l'ordre croissant."""
    n = len(t)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            if t[j] < t[i_min]:
                i_min = j
        t[i], t[i_min] = t[i_min], t[i]


notes = [29, 10, 14, 37, 13]
tri_selection(notes)
print(notes)

[10, 13, 14, 29, 37]

Trace sur [29, 10, 14, 37, 13] :

La boucle externe s'arrête à n - 2 : quand les n − 1 premiers éléments sont à leur place, le dernier l'est forcément. Le tri par sélection fait toujours le même nombre de comparaisons, n(n − 1)/2, même si le tableau est déjà trié : 10 pour 5 éléments, 4 950 pour 100. En revanche, il fait au plus n − 1 échanges.

Le tri à bulles

On parcourt le tableau en comparant chaque élément à son voisin de droite et en les échangeant s'ils sont dans le désordre. À la fin d'un parcours, le plus grand élément est arrivé au bout, comme une bulle qui remonte. On recommence sur la partie restante.

Une amélioration simple : si un parcours ne fait aucun échange, le tableau est trié et on peut s'arrêter. Un booléen echange le mémorise.

Procédure TriBulles(E/S t : tableau d'entiers)
    n ← longueur(t)
    i ← 0
    echange ← VRAI
    TantQue i < n - 1 ET echange Faire
        echange ← FAUX
        Pour j de 0 à n - 2 - i Faire
            Si t[j] > t[j + 1] Alors
                temp ← t[j]
                t[j] ← t[j + 1]
                t[j + 1] ← temp
                echange ← VRAI
            FinSi
        FinPour
        i ← i + 1
    FinTantQue
FinProcédure

def tri_bulles(t):
    """Trie la liste t sur place ; s'arrête dès qu'un parcours ne change rien."""
    n = len(t)
    for i in range(n - 1):
        echange = False
        for j in range(n - 1 - i):
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]
                echange = True
        if not echange:
            break


notes = [29, 10, 14, 37, 13]
tri_bulles(notes)
print(notes)

Détail du premier parcours sur [29, 10, 14, 37, 13] :

Les parcours suivants donnent 10, 14, 13, 29, 37, puis 10, 13, 14, 29, 37, puis un dernier parcours sans échange qui arrête l'algorithme. La borne n - 2 - i du pseudo-code (range(n - 1 - i) en Python) évite de recomparer la fin, déjà triée.

Dans le pire cas (tableau trié à l'envers), le tri à bulles fait n(n − 1)/2 comparaisons et autant d'échanges : c'est le plus lent des trois. Mais sur un tableau déjà trié, la version avec drapeau ne fait qu'un parcours : n − 1 comparaisons.

Le tri par insertion

C'est le tri que tu fais avec des cartes à jouer : tu prends les cartes une par une et tu insères chacune à sa place parmi celles déjà rangées dans ta main. Pour insérer, on décale vers la droite les éléments plus grands que la carte, puis on la pose dans le trou.

Procédure TriInsertion(E/S t : tableau d'entiers)
    Pour i de 1 à longueur(t) - 1 Faire
        cle ← t[i]
        j ← i - 1
        TantQue j ≥ 0 ET t[j] > cle Faire
            t[j + 1] ← t[j]      // décalage vers la droite
            j ← j - 1
        FinTantQue
        t[j + 1] ← cle
    FinPour
FinProcédure

def tri_insertion(t):
    """Trie la liste t sur place, par insertion."""
    for i in range(1, len(t)):
        cle = t[i]
        j = i - 1
        while j >= 0 and t[j] > cle:
            t[j + 1] = t[j]
            j = j - 1
        t[j + 1] = cle


notes = [29, 10, 14, 37, 13]
tri_insertion(notes)
print(notes)

Remarque l'ordre des conditions du TantQue : j ≥ 0 est testé avant t[j] > cle. Grâce à l'évaluation partielle, quand j vaut −1, t[j] n'est pas évalué. En Python, t[-1] ne lèverait même pas d'erreur (c'est le dernier élément) : l'algorithme serait faux en silence.

Le tri par insertion fait n(n − 1)/2 comparaisons dans le pire cas, mais seulement n − 1 sur un tableau déjà trié : c'est le meilleur des trois sur des données presque triées, un cas fréquent (une liste triée à laquelle on ajoute quelques éléments).

Comparer les trois tris

Le programme demande de « s'interroger sur l'efficacité d'un algorithme ». Le plus simple est de compter les opérations significatives, ici les comparaisons entre éléments, sur des tableaux de taille croissante.

n(n − 1)/2 vaut 45 pour n = 10, 4 950 pour 100 et 499 500 pour 1 000 : multiplier la taille par 10 multiplie le travail par 100 environ. Pour un million d'éléments, cela ferait environ 500 milliards de comparaisons. C'est pourquoi les langages utilisent des tris plus élaborés : celui de Python (sorted, sort) fait de l'ordre de n × log₂(n) comparaisons, soit environ 20 millions pour un million d'éléments. Le chapitre 12 donne le vocabulaire de la complexité.

On peut vérifier ces chiffres en instrumentant le code : on ajoute un compteur qui augmente à chaque comparaison.

def comparaisons_selection(t):
    t = t.copy()   # on ne modifie pas la liste reçue
    nb = 0
    n = len(t)
    for i in range(n - 1):
        i_min = i
        for j in range(i + 1, n):
            nb = nb + 1
            if t[j] < t[i_min]:
                i_min = j
        t[i], t[i_min] = t[i_min], t[i]
    return nb


for n in [10, 100, 1000]:
    print(n, comparaisons_selection(list(range(n, 0, -1))))

10 45
100 4950
1000 499500

Trier avec Python

En dehors des exercices où l'on te demande l'algorithme, utilise les tris de Python :

notes = [29, 10, 14, 37, 13]
print(sorted(notes))                 # nouvelle liste triée, notes inchangée
print(sorted(notes, reverse=True))   # ordre décroissant
notes.sort()                         # trie la liste elle-même
print(notes)

def prix(article):
    return article[1]

articles = [("clavier", 25.0), ("écran", 149.0), ("souris", 12.5)]
print(sorted(articles, key=prix))    # trié selon le prix

[10, 13, 14, 29, 37]
[37, 29, 14, 13, 10]
[10, 13, 14, 29, 37]
[('souris', 12.5), ('clavier', 25.0), ('écran', 149.0)]

sorted renvoie une nouvelle liste ; sort modifie la liste et renvoie None (écrire notes = notes.sort() perd la liste). Le paramètre key reçoit une fonction qui donne, pour chaque élément, la valeur selon laquelle trier : ici la colonne du prix d'un tableau à colonnes de types différents.

Exercices

def recherche(t, x):
    deb, fin = 0, len(t) - 1
    while deb <= fin:
        milieu = (deb + fin) // 2
        if t[milieu] == x:
            return milieu
        elif t[milieu] < x:
            deb = milieu
        else:
            fin = milieu - 1
    return -1

def tri_selection_decroissant(t):
    n = len(t)
    for i in range(n - 1):
        i_max = i
        for j in range(i + 1, n):
            if t[j] > t[i_max]:
                i_max = j
        t[i], t[i_max] = t[i_max], t[i]


t = [12, 40, 7, 25]
tri_selection_decroissant(t)
print(t)

noms = ["Hugo", "Inès", "Léa", "Malik"]
notes = [9, 14, 17, 11]
for i in range(1, len(notes)):
    cle_note = notes[i]
    cle_nom = noms[i]
    j = i - 1
    while j >= 0 and notes[j] < cle_note:
        notes[j + 1] = notes[j]
        noms[j + 1] = noms[j]
        j = j - 1
    notes[j + 1] = cle_note
    noms[j + 1] = cle_nom
print(noms, notes)

def fusion(a, b):
    resultat = []
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            resultat.append(a[i])
            i = i + 1
        else:
            resultat.append(b[j])
            j = j + 1
    # l'un des deux tableaux est épuisé : on recopie le reste de l'autre
    while i < len(a):
        resultat.append(a[i])
        i = i + 1
    while j < len(b):
        resultat.append(b[j])
        j = j + 1
    return resultat


print(fusion([3, 8, 15, 20], [1, 9, 10, 25, 30]))