Diviser pour régner : le tri fusion

La méthode « diviser pour régner » résout un problème en trois temps :

1. Diviser le problème en sous-problèmes de même nature, plus petits ;
2. Résoudre chaque sous-problème, souvent par un appel récursif ;
3. Combiner les solutions des sous-problèmes en une solution du problème.

Le tri fusion l'applique au tri d'un tableau : on le coupe en deux moitiés, on trie chaque moitié, puis on fusionne les deux moitiés triées. La fusion parcourt les deux tableaux triés en parallèle et prend à chaque fois le plus petit des deux premiers éléments non encore pris :

def fusion(a, b):
    i = 0
    j = 0
    r = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i])
            i = i + 1
        else:
            r.append(b[j])
            j = j + 1
    return r + a[i:] + b[j:]

print(fusion([3, 8, 12], [5, 6, 20, 25]))

[3, 5, 6, 8, 12, 20, 25]

Quand l'un des deux tableaux est épuisé, la boucle s'arrête et on ajoute à la fin ce qui reste de l'autre, déjà trié : a[i:] désigne le tableau des éléments de a d'indices i à la fin (vide si i = len(a)), de même pour b[j:] ; le signe + met des tableaux bout à bout.

Le tri fusion, écrit à la suite de la fonction fusion : un tableau de longueur 0 ou 1 est déjà trié (cas de base) ; sinon, on coupe au milieu. t[:m] est le tableau des éléments d'indices 0 à m − 1, t[m:] celui des éléments d'indices m à la fin.

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

print(tri_fusion([38, 27, 43, 3, 9, 82, 10]))

[3, 9, 10, 27, 38, 43, 82]

Coût. On coupe en deux jusqu'à des tableaux d'un élément : il y a environ log₂ n niveaux de découpage, et à chaque niveau les fusions traitent en tout n éléments. Le coût est de l'ordre de n log₂ n dans tous les cas, contre n² dans le pire cas pour les tris par sélection et par insertion.

Comptons les comparaisons du tri fusion sur 1 000 nombres mélangés, et comparons au nombre n(n − 1)/2 de comparaisons du tri par sélection. La ligne global compteur (hors programme) permet seulement à la fonction fusion de modifier la variable compteur créée en dehors d'elle ; on ne s'en sert ici que pour compter. random.shuffle mélange le tableau, et random.seed(1) fixe ce mélange pour qu'il soit le même à chaque exécution :

import random

compteur = 0

def fusion(a, b):
    global compteur
    i = 0
    j = 0
    r = []
    while i < len(a) and j < len(b):
        compteur = compteur + 1
        if a[i] <= b[j]:
            r.append(a[i])
            i = i + 1
        else:
            r.append(b[j])
            j = j + 1
    return r + a[i:] + b[j:]

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

random.seed(1)
t = list(range(1000))
random.shuffle(t)
print(tri_fusion(t) == sorted(t), compteur)
print(1000 * 999 // 2)

True 8705
499500

Le tri est correct, avec 8 705 comparaisons (1 000 × log₂ 1 000 ≈ 9 966), contre 499 500.

Énoncé. Cette fonction fusionne deux tableaux triés et compte dans c les comparaisons. Quel nombre affiche-t-elle ?

def fusion(a, b):
    i = 0
    j = 0
    c = 0
    r = []
    while i < len(a) and j < len(b):
        c = c + 1
        if a[i] <= b[j]:
            r.append(a[i])
            i = i + 1
        else:
            r.append(b[j])
            j = j + 1
    return c
print(fusion([4, 15, 31], [9, 12, 40, 52]))

Méthode : suivre i, j et c tour par tour.

Après le tour 5, i = 3 = len(a) : le tableau a est épuisé, la boucle s'arrête. Il reste 40 et 52 dans b, mais ils ne sont plus comparés.

5

Tri fusion de [38, 27, 43, 3, 9, 82, 10] (coupure à m = len(t) // 2) :