Problème — Fusion de k listes triées — exercice corrigé de NSI (terminale) (chapitre 6)

Problème — Fusion de

k

listes triées

Diviser pour régner · niveau 2

Énoncé

Problème — Fusion de $k$ listes triées.

On dispose de $k$ listes déjà triées. Construire une unique liste triée contenant tous leurs éléments, en réutilisant la fusion du tri fusion.

Corrigé

on fusionne les listes deux par deux de façon arborescente, exactement comme dans le tri fusion, ce qui est plus efficace que de fusionner les listes une à une.


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

def fusion_k_listes(listes):
    if len(listes) == 0:
        return []
    if len(listes) == 1:
        return listes[0]
    m = len(listes) // 2
    gauche = fusion_k_listes(listes[:m])   # diviser
    droite = fusion_k_listes(listes[m:])
    return fusion(gauche, droite)          # combiner

En notant $N$ le nombre total d'éléments, cette approche s'exécute en $O (N lo g k)$ , contre $O (N k)$ pour une fusion séquentielle naïve.