Tri par dénombrement⚓︎

Dans cet exercice on s'interdit d'utiliser max, sort et sorted

On souhaite dans cet exercice trier des tableaux de nombres entiers positifs ou nuls.

Pour ce faire on utilise l'algorithme du tri par dénombrement.

Les étapes sont les suivantes :

déterminer la valeur maximale dans le tableau,
regrouper dans un autre tableau le nombre d'apparitions de chaque valeur entre 0 et le maximum déterminé à l'étape précédente. Dans ce tableau d'effectifs, la valeur à l'indice i donnera le nombre d'apparitions de i dans le tableau initial,
parcourir le tableau des effectifs et ajouter autant de fois que nécessaire chaque indice dans le tableau de nombres triés.

Exemple

On souhaite trier le tableau nombres = [3, 3, 2, 0, 3, 0, 2, 0, 2, 3] :

La valeur maximale est 3
Le tableau des effectifs vaut :

🐍 Script Python

# indice     0  1  2  3
effectifs = [3, 0, 3, 4]

Le 3 à l'indice 2 signifie que le nombre 2 apparaît trois fois dans nombres.

On parcourt effectifs :
- à l'indice 0 on trouve la valeur 3 : on insère trois fois 0 dans le tableau nombres_tries,
- à l'indice 1 on trouve la valeur 0 : on n'effectue pas d'insertion,
- à l'indice 2 on trouve la valeur 3 : on insère trois fois 2 dans nombres_tries,
- à l'indice 3 on trouve la valeur 4 : on insère quatre fois 3 dans nombres_tries.
On obtient le tableau [0, 0, 0, 2, 2, 2, 3, 3, 3, 3].

Vous devez écrire deux fonctions :

maximum prend en argument un tableau de nombres nombres et renvoie la valeur maximale dans celui-ci,
tri_denombrement prend en argument un tableau de nombres nombres et renvoie un tableau contenant les mêmes valeurs triées dans l'ordre croissant.

Exemples

🐍 Console Python

>>> nombres = [4, 5, 4, 2]
>>> tri_denombrement(nombres)
[2, 4, 4, 5]
>>> nombres = [5, 4, 3, 2, 1]
>>> tri_denombrement(nombres)
[1, 2, 3, 4, 5]
>>> nombres = []
>>> tri_denombrement(nombres)
[]

∞/∞

def maximum(nombres):bksl-nl ...bksl-nlbksl-nlbksl-nldef tripy-unddenombrement(nombres):bksl-nl maxi = ...bksl-nlbksl-nl effectifs = [0] py-str (maxi + 1)bksl-nlbksl-nl for nb in nombres:bksl-nl ...bksl-nlbksl-nl # On crée une nouvelle listebksl-nl # pour stocker les nombres triésbksl-nl nombrespy-undtries = []bksl-nl for n in range(maxi + 1):bksl-nl for i in ...:bksl-nl ...bksl-nlbksl-nl return nombrespy-undtriesbksl-nlbksl-nlbksl-nl# Testsbksl-nlliste = [4, 5, 4, 2]bksl-nltripy-unddenombrement(liste)bksl-nlassert liste == [2, 4, 4, 5]bksl-nlliste = [3, 8, 7, 3, 5]bksl-nltripy-unddenombrement(liste)bksl-nlassert liste == [3, 3, 5, 7, 8]bksl-nlliste = [1, 2, 3, 4, 5]bksl-nltripy-unddenombrement(liste)bksl-nlassert liste == [1, 2, 3, 4, 5]bksl-nlliste = [5, 4, 3, 2, 1]bksl-nltripy-unddenombrement(liste)bksl-nlassert liste == [1, 2, 3, 4, 5]bksl-nlliste = []bksl-nltripy-unddenombrement(liste)bksl-nlassert liste == []bksl-nlbksl-nldef maximum(nombres):bksl-nl maxi = 0bksl-nl for nb in nombres:bksl-nl if nb > maxi:bksl-nl maxi = nbbksl-nl return maxibksl-nlbksl-nlbksl-nldef tripy-unddenombrement(nombres):bksl-nl maxi = maximum(nombres)bksl-nlbksl-nl effectifs = [0] py-str (maxi + 1)bksl-nlbksl-nl for nb in nombres:bksl-nl effectifs[nb] += 1bksl-nlbksl-nl nombrespy-undtries = []bksl-nl for n in range(maxi + 1):bksl-nl for i in range(effectifs[n]):bksl-nl nombrespy-undtries.append(n)bksl-nlbksl-nl return nombrespy-undtriesbksl-nlbksl-nlbksl-nl# Testsbksl-nlnombres = [4, 5, 4, 2]bksl-nlassert tripy-unddenombrement(nombres) == [2, 4, 4, 5]bksl-nlnombres = [3, 8, 7, 3, 5]bksl-nlassert tripy-unddenombrement(nombres) == [3, 3, 5, 7, 8]bksl-nlnombres = [1, 2, 3, 4, 5]bksl-nlassert tripy-unddenombrement(nombres) == [1, 2, 3, 4, 5]bksl-nlnombres = [5, 4, 3, 2, 1]bksl-nlassert tripy-unddenombrement(nombres) == [1, 2, 3, 4, 5]bksl-nlnombres = []bksl-nlassert tripy-unddenombrement(nombres) == []bksl-nlbksl-nl# Tests supplémentairesbksl-nlnombres = [4, 4, 4]bksl-nlassert tripy-unddenombrement(nombres) == [4, 4, 4]bksl-nlnombres = [k for k in range(100, -1, -1)]bksl-nlassert tripy-unddenombrement(nombres) == list(range(101))bksl-nlnombres = [1, 2]py-str10bksl-nlassert tripy-unddenombrement(nombres) == [1]py-str10+[2]py-str10bksl-nlnombres = [10py-strpy-str3, 0]bksl-nlassert tripy-unddenombrement(nombres) == [0, 10py-strpy-str3]bksl-nlbksl-nl

Commentaires⚓︎

Il s'agit d'un tri original car de complexité linéaire. Avantageux sur ce point, il l'est moins sur les deux point suivants :

cet algorithme ne s'applique qu'aux valeurs entières positives ou nulles,
il nécessite de créer un tableau annexe contenant les effectifs ce qui peut consommer de la mémoire.

La fonction maximum est classique : on initialise le maximum à 0 puis on lit l'ensemble des valeurs.

Pour la fonction tri_denombrement :

on commence par chercher la valeur maximale
on crée ensuite le tableau effectifs contenant maximum + 1 fois le nombre 0
on lit ensuite l'ensemble des valeurs de nombres et on incrémente la cellule effectifs[nb] correspondante
on crée une liste vide nombres_tries
on remplit cette liste vide :
- on parcourt tous les entiers n entre 0 et maxi (inclus),
- pour chacun d'entre eux, on ajoute autant de fois que nécessaire leur valeur dans nombres_tries,
- le nombre d'ajout à faire est donné par l'effectif du nombre : effectif[n].

Comme on a créé une nouvelle liste pour stocker les valeurs triées, on la renvoie à la fin.

Remarques :

Avec Python, il est possible à l'aide de enumerate de parcourir une liste en récupérant à chaque itération les couples (indice, valeur). En utilisant cette technique le boucle principale deviendrait :

🐍 Script Python

for n, eff in enumerate(effectifs):
    for _ in range(eff):
        nombres_tries.append(n)

Une version en place du tri va réécrire les valeurs triées directement dans la liste de départ. Pour ce faire, il faut garder trace de l'indice où l'on doit écrire la prochaine valeur :

🐍 Script Python

def tri_denombrement(nombres):
    maxi = maximum(nombres)

    effectifs = [0] * (maxi + 1)

    for nb in nombres:
        effectifs[nb] += 1

    indice_insertion = 0
    for n in range(maxi + 1):
        for _ in range(effectifs[n]):
            nombres[indice_insertion] = n
            indice_insertion += 1

On utilise ici une version de l'algorithme utilisant un tableau (une liste avec Python) pour stocker les effectifs. Comme mentionné plus haut cette approche est peu efficace dans certains cas en termes d'utilisation de la mémoire. On pourrait de façon plus efficace utiliser un dictionnaire Python.

Dans ce cas, il est inutile de rechercher le maximum et le code devient :

🐍 Script Python

def tri_denombrement_dico(nombres):
    effectifs = {}
    for nb in nombres:
        if nb in effectifs :
            effectifs[nb] += 1
        else :
            effectifs[nb] = 1

    nombres_tries = []
    for n in effectifs:
        for i in range(effectifs[n]):
            nombres_tries.append(n)

    return nombres_tries