Fonction sorted

Algo 02

Résumé du cours

Algorithme diviser pour régner

Remarque

Le principe de l’algorithme de diviser pour régner consiste à découper un gros problème, difficile à résoudre, en petits problèmes plus simples.

Le tri fusion est un exemple d’algorithme de diviser pour régner.

diviser diviser Obtenir de petits problèmes

diviser diviser Résoudre les petits problèmes: une liste d’un élément est triée.

diviser diviser Trier

diviser diviser Et remonter

def tri_fusion(tab: list, deb: int, fin: int) -> None:
    if deb < fin:
        milieu = (deb+fin)//2
        tri_fusion(tab, deb, milieu)
        tri_fusion(tab, milieu+1, fin)
        fusionner(tab, deb, fin)
def fusionner(tab: list, deb: int, fin: int) -> None:
    res = []
    milieu = (deb+fin)//2
    i = deb
    j = milieu+1
    while i <= milieu and j <= fin:
        if tab[i] < tab[j]:
            res.append(tab[i])
            i += 1
        else:
            res.append(tab[j])
            j += 1
        
    # ajout fin de tab
    for i1 in range(i, milieu+1):
        res.append(tab[i1])        
    for j1 in range(j, fin+1):
        res.append(tab[j1])
        
    # remplacement tab par res
    for k in range(fin-deb+1):
        tab[deb+k] = res[k]

Complexité

  • La complexité du découpage en sous-listes (fonction tri_fusion) est logarithmique.
  • La complexité de la fusion (fonction fusionner) est linéaire.
Remarque

L’algorithme de tri fusion a une complexité: $$n\times\log_2(n)$$