Écrire top k(table, colonne, k) qui rend les k plus grandes lignes…

On répète $k$ fois la recherche du maximum du chapitre 7, en retirant à chaque fois l'élu.

def top_k(table, colonne, k):
    """Les k lignes de plus grande valeur, par ordre décroissant.

    Précondition  : 0 <= k ; si k > len(table), rend toute la table.
    Postcondition : le résultat est décroissant sur la colonne.
    """
    reste = list(table)          # copie : on ne détruit pas la table
    res = []
    for _ in range(k):
        if len(reste) == 0:
            break
        m = 0
        for i in range(1, len(reste)):
            if reste[i][colonne] > reste[m][colonne]:
                m = i
        res.append(reste.pop(m))
    return res

[l["nom"] for l in top_k(eleves, "moyenne", 2)]     # ['Sofia', 'Nour']

La validation. On compare à la voie évidente — trier puis découper — sur $400$ tables tirées au hasard, tailles et $k$ compris :

a = top_k(t, "v", k)
b = sorted(t, key=lambda l: l["v"], reverse=True)[:k]
assert [l["v"] for l in a] == [l["v"] for l in b]

$400$ cas passent.

Le coût, et le point de bascule. top_k fait $k$ parcours, soit environ $kn$ comparaisons ; le tri en fait de l'ordre de $n{\log }_{2}n$. Pour $k=3$ :

L'écart se creuse : à $n=100000$, le tri fait cinq fois le travail. Mais l'avantage s'inverse dès que $k$ dépasse ${\log }_{2}n$ — soit $17$ pour $n=100000$. Le bon algorithme dépend de $k$, pas seulement de $n$.