Aller au contenu

Tris de coûts linéaires⚓︎

Hors du programme de NSI

Les tris abordés dans cette partie ne font pas partie du programme de NSI (ni en Première, ni en Terminale).

Les différents algorithmes de tri abordés précédemment (par sélection, insertion, à bulle, fusion et rapide) sont tous des tris par comparaison : afin de trier le tableaux, ces algorithmes doivent comparer des éléments deux à deux.

On peut montrer que le coût de tels algorithmes ne peut pas descendre sous une certaine borne (les tris fusion et rapide atteignent cette borne dans certain cas, les tris par sélection, insertion et à bulles jamais).

Il existe toutefois des algorithmes de tris moins coûteux, plus rapides donc. Ils ne s'appuient toutefois pas sur les comparaisons d'éléments. Ces algorithmes profitent plutôt de particularités des tableaux à trier.

Nous allons en étudier deux dans cette partie, le tri par dénombrement et le tri du drapeau hollandais.

Tri par dénombrement⚓︎

Le tri par dénombrement en bref

On l'utilise dans le cadre des tableaux d'entiers positifs ou nuls.

On compte le nombre d'apparitions de chaque valeur entre 0 et le maximum du tableau (inclus l'un et l'autre) puis on trie le tableau initial en lisant ces apparitions dans l'ordre croissant

On se restreint aux tableaux de nombres entiers positifs ou nuls.

Les étapes du tri par dénombrement 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 x donne le nombre d'apparitions de x dans le tableau initial,

  • parcourir le tableau des effectifs et écrire autant de fois que nécessaire chaque indice dans le tableau initial.

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 3 fois dans nombres ;

  • On parcourt effectifs :

    • à l'indice 0 on trouve la valeur 3 : on écrit trois fois 0 dans le tableau,
    • à l'indice 1 on trouve la valeur 0 : on n'écrit aucun 1 dans le tableau,
    • à l'indice 2 on trouve la valeur 3 : on écrit trois fois 2,
    • à l'indice 3 on trouve la valeur 4 : on écrit quatre fois 3 ;

  • Le tableau est désormais trié : [0, 0, 0, 2, 2, 2, 3, 3, 3, 3].

Vous devez écrire deux fonctions :

  • maximum prend en argument un tableau et renvoie la valeur maximale de celui-ci,

  • tri_denombrement prend en argument un tableau entiers et le trie en utilisant le tri par dénombrement.

###

def maximum(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nldef tripy-unddenombrement(entiers):bksl-nl ...bksl-nlbksl-nlbksl-nlnombres = [4, 5, 4, 2]bksl-nltripy-unddenombrement(nombres)bksl-nlassert nombres == [2, 4, 4, 5], "Erreur avec [4, 5, 4, 2]"bksl-nlbksl-nlnombres = [3, 8, 7, 3, 5]bksl-nltripy-unddenombrement(nombres)bksl-nlassert nombres == [3, 3, 5, 7, 8], "Erreur avec [3, 8, 7, 3, 5] "bksl-nlbksl-nlnombres = [1, 2, 3, 4, 5]bksl-nltripy-unddenombrement(nombres)bksl-nlassert nombres == [1, 2, 3, 4, 5], "Erreur avec [1, 2, 3, 4, 5]"bksl-nlbksl-nlnombres = [5, 4, 3, 2, 1]bksl-nltripy-unddenombrement(nombres)bksl-nlassert nombres == [1, 2, 3, 4, 5], "Erreur avec [5, 4, 3, 2, 1] "bksl-nlbksl-nlnombres = []bksl-nltripy-unddenombrement(nombres)bksl-nlassert nombres == [], "Erreur avec []"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def maximum(tableau):
    maxi = 0
    for x in tableau:
        if x > maxi:
            maxi = x
    return maxi


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

    effectifs = [0] * (maxi + 1)

    for x in entiers:
        effectifs[x] += 1

    i = 0
    for x in range(maxi + 1):
        for _ in range(effectifs[x]):
            entiers[i] = x
            i += 1

On pourrait aussi utiliser max(nombres)

Tri du drapeau hollandais⚓︎

Le tri du drapeau hollandais en bref

On l'utilise dans le cadre des tableaux ne contenant que trois valeurs distinctes (petite, moyenne et grande).

Il a pour avantage d'être de coût linéaire et de trier le tableau en un seul passage.

On partage le tableau en quatre zones :

  • les petites valeurs,
  • puis les valeurs moyennes,
  • puis les valeurs pas encore triées,
  • enfin les grandes valeurs.

Schéma

Schéma

L'algorithme s'arrête lorsque la zone des valeurs à trier est vide.

On souhaite trier un tableau ne contenant que trois valeurs a, b et c répétées un nombre quelconque de fois. On souhaite trier ce tableau afin de placer au début les a suivis des b et enfin des c.

Par exemple, avec nombres = [2, 0, 2, 1, 2, 1] on a a = 0, b = 1 et c = 2. Le tableau trié est [0, 1, 1, 2, 2, 2].

Dans ce cas de figure, on peut utiliser le tri du drapeau hollandais.

Remarque

Ce tri a été inventé par Edsger Dijkstra qui était de nationalité néelandaise.

Il a donné son nom à l'algorithme en référence aux trois couleurs du drapeau néerlandais : Rouge, Blanc, Bleu.

Drapeau hollandais

L'idée est de maintenir quatre zones dans le tableau :

  • la première ne contient que des a,
  • la deuxième que des b,
  • la troisième des valeurs pas encore triées,
  • enfin la dernière zone ne contient que des c.

Ces zones sont délimitées par les bornes suivantes (toutes incluses):

  1. de l'indice 0 à prochain_a - 1,
  2. de prochain_a à actuel,
  3. de actuel + 1 à prochain_c,
  4. de prochain_c + 1 à len(tableau) - 1

Les quatre zones Les quatre zones

L'algorithme fonctionne ainsi :

  • Les variables prochain_a et actuel sont initialisées à 0,

  • La variable prochain_c est initialisée à len(tableau) - 1,

  • On répète les actions suivantes tant que la zone des valeurs restant à trier est non vide :

    • On lit l'élément à l'indice actuel :

      • Si c'est un a, on le rajoute à la fin de la zone des a en échangeant les éléments d'indices prochain_a et actuel (étape 3 sur les figures),
      • Si c'est un b, on la laisse à sa position (étape 2 et 6),
      • Si c'est un c, on la place à la position précédant le début de la zone des c en échangeant les éléments d'indices prochain_c et actuel (étape 1, 4 et 5),
      • Dans tous les cas, on prend soin de mettre à jour les différents indices afin de refléter les nouvelles étendues des zones.

Les figures ci-dessous illustrent le tri du tableau [2, 0, 2, 1, 2, 1] :

  • Étape 1

    Étape 1 Étape 1

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.

  • Étape 2

    Étape 2 Étape 2

    On lit un 1 : on le laisse à cette position.

    actuel est incrémenté.

  • Étape 3

    Étape 3 Étape 3

    On lit un 0 : on le place à la fin de la zone des a.

    prochain_a et actuel sont incrémentés.

  • Étape 4

    Étape 4 Étape 4

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.

  • Étape 5

    Étape 5 Étape 5

    On lit un 2 : on le place au début de la zone des c.

    prochain_c est décrémenté.

  • Étape 6

    Étape 6 Étape 6

    On lit un 1 : on le laisse à cette position.

  • Étape 7

    Étape 7 Étape 7

    actuel est strictement supérieur à prochain_c.

    L'algorithme se termine.

Vous devez écrire la fonction tri_drapeau qui prend en argument un tableau ainsi que les trois valeurs distinctes le composant a, b et c et le trie en place en positionnant les a au début suivis des b et enfin des c.

###

def tripy-unddrapeau(tableau, a, b, c):bksl-nl prochainpy-unda = 0bksl-nl actuel = 0bksl-nl prochainpy-undc = len(tableau) - 1bksl-nlbksl-nl while ... <= ...:bksl-nl if tableau[...] == a:bksl-nl tableau[...], tableau[...] = tableau[...], tableau[...]bksl-nl prochainpy-unda = ...bksl-nl actuel = ...bksl-nl elif tableau[...] == b:bksl-nl actuel = ...bksl-nl else:bksl-nl tableau[...], tableau[...] = tableau[...], tableau[...]bksl-nl prochainpy-undc =...bksl-nlbksl-nlbksl-nl# Testsbksl-nlentiers = [2, 0, 2, 1, 2, 1]bksl-nla, b, c = 0, 1, 2bksl-nltripy-unddrapeau(entiers, a, b, c)bksl-nlassert entiers == [0, 1, 1, 2, 2, 2]bksl-nlbksl-nlneveux = ["Fifi", "Loulou", "Riri", "Riri", "Fifi"]bksl-nla, b, c = "Riri", "Fifi", "Loulou"bksl-nltripy-unddrapeau(neveux, a, b, c)bksl-nlassert neveux == ["Riri", "Riri", "Fifi", "Fifi", "Loulou"]bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution
🐍 Script Python
def tri_drapeau(tableau, a, b, c):
    prochain_a = 0
    actuel = 0
    prochain_c = len(tableau) - 1

    while actuel <= prochain_c:
        if tableau[actuel] == a:
            tableau[prochain_a], tableau[actuel] = tableau[actuel], tableau[prochain_a]
            prochain_a = prochain_a + 1
            actuel = actuel + 1
        elif tableau[actuel] == b:
            actuel = actuel + 1
        else:
            tableau[prochain_c], tableau[actuel] = tableau[actuel], tableau[prochain_c]
            prochain_c = prochain_c - 1