Le tri par comptage stable, et le tri par base

Les tris · niveau 3 (difficile)

Énoncé

Implémenter le tri par comptage stable par positions cumulées et l'utiliser pour réaliser un tri par base de nombres inférieurs à 1000.

Corrigé

def tri_comptage_stable(fiches: list, cle, k: int) -> list:
    effectifs = [0] * k
    for f in fiches:
        effectifs[cle(f)] += 1
    # Cumul des positions pour trouver l'indice de départ de chaque clé
    debut = [0] * k
    for v in range(1, k):
        debut[v] = debut[v - 1] + effectifs[v - 1]
    r = [None] * len(fiches)
    for f in fiches:
        r[debut[cle(f)]] = f
        debut[cle(f)] += 1
    return r

def tri_par_base(t: list) -> list:
    # passes successives stables sur les unités, dizaines et centaines
    r = tri_comptage_stable(t, lambda x: x % 10, 10)
    r = tri_comptage_stable(r, lambda x: (x // 10) % 10, 10)
    return tri_comptage_stable(r, lambda x: x // 100, 10)

Énoncé

Corrigé

Exercices semblables