Exercices sur les tris efficaces⚓︎

Autour du tri fusion (1)

Cocher la ou les affirmations correctesSolution

Le tri fusion est un algorithme glouton
Lors de son fonctionnement, l'algorithme de tri fusion n'utilise pas de variables temporaires afin de stocker des valeurs
Si un tableau contient deux éléments égaux \(a\) et \(b\), \(a\) se trouvant initialement à gauche de \(b\), alors à l'issue du tri \(b\) sera à gauche de \(a\)
Le tri fusion est utilisé dans le tim-sort

Non, le tri fusion relève du modèle " Diviser pour régner", pas des algorithmes gloutons
C'est l'un des désavantages du tri fusion : il utiliser un espace mémoire supplémentaire égal à la taille du tableau
Oui. Cette propriété classe le tri fusion parmi les tris stables
En effet le tim-sort utilise le tri fusion et le tri par insertion

Autour du tri fusion (2)

Cocher la ou les affirmations correctesSolution

Si le tableau d'entrée est trié dans l'ordre croissant le tri fusion effectue moins de partages
Si le tableau d'entrée est trié dans l'ordre décroissant le tri fusion effectue moins de partages
Le tri fusion d'un tableau de \(10^6\) éléments nécessite \(20\) étapes de partages
Lorsque la taille du tableau double, le tri fusion doit effectuer \(2\) fois plus d'étapes de partage

L'état initial du tableau n'a pas d'effet sur le nombre de partages, seul sa longueur importe
Voir ci-dessus
En effet, \(2^{19} < 10^6 < 2^{20}\)
Lorsque la taille du tableau double il faut juste faire une étape de partage supplémentaire

Compter les inversions à l'aide du tri fusion

L'exercice « la fonction inversions » proposait de compter les inversions dans un tableau. La solution proposée était de coût quadratique.

Il est possible de répondre au problème plus efficacement en utilisant le tri fusion.

Remarque

La méthode proposée ici trie le tableau initial. Si l'on souhaite le conserver inchangé, il suffit d'appliquer la méthode à une copie du tableau.

Considérons l'exemple de la fusion de gauche = [3, 8, 15] et droite = [4, 5, 12] :

Le premier élément pioché est 3, il provient du sous-tableau de gauche et n'indique pas d'inversion car le 3 de gauche est bien situé avant toutes les valeurs de droite.
On pioche ensuite le 4 dans droite : cette valeur est inférieure aux deux valeurs restantes à gauche, 8 et 15. On peut compter deux inversions.
On pioche ensuite le 5 dans droite : cette valeur est elle aussi inférieure à 8 et 15. On peut ajouter deux inversions.
On pioche ensuite le 8 à gauche : pas d'inversion.
Le 12 provient de droite. Il reste un élément non lu dans gauche, on ajoute une inversion.
Enfin on pioche le 15 à gauche : pas d'inversion supplémentaire.

Au total on a donc \(2+2+1=5\) inversions dans le tableau [3, 8, 15, 4, 5, 12].

De façon générale, lors de la fusion des deux sous-tableaux, piocher une valeur dans droite indique que celle-ci est strictement inférieure à toutes les valeurs restantes dans gauche. On ajoute autant d'inversions.

Ce décompte doit se faire de façon récursive : combien d'inversions dans les fusions des tableaux de taille \(1\) ? Et combien dans les fusions des tableaux de taille \(2\) ? De taille \(4\)... ?

Compléter la fonction inversions afin qu'elle renvoie le nombre d'inversions du tableau en utilisant le tri fusion.

###

Solution

🐍 Script Python

def sous_tableau(tableau, debut, fin):
    nouveau = [None] * (fin - debut)
    for i in range(debut, fin):
        nouveau[i - debut] = tableau[i]
    return nouveau


def inversions(tableau, debut, fin):
    # Cas de base, tableau de longueur 1 ou moins
    if (fin - debut) < 2:
        return 0

    milieu = (fin + debut) // 2

    nb_inversions = 0
    # Tris récursifs des parties gauche et droite
    nb_inversions += inversions(tableau, debut, milieu)
    nb_inversions += inversions(tableau, milieu, fin)

    # Fusion
    gauche = sous_tableau(tableau, debut, milieu)
    droite = sous_tableau(tableau, milieu, fin)

    i_gauche = 0
    i_droite = 0
    i_tableau = debut

    # Il reste des éléments à gauche ET à droite
    while i_gauche < len(gauche) and i_droite < len(droite):
        if gauche[i_gauche] <= droite[i_droite]:
            tableau[i_tableau] = gauche[i_gauche]
            i_gauche += 1
        else:
            tableau[i_tableau] = droite[i_droite]
            i_droite += 1
            nb_inversions += len(gauche) - i_gauche
        i_tableau += 1

    # Il ne reste des éléments QUE à gauche
    while i_gauche < len(gauche):
        tableau[i_tableau] = gauche[i_gauche]
        i_gauche += 1
        i_tableau += 1

    # Il ne reste des éléments QUE à droite
    while i_droite < len(droite):
        tableau[i_tableau] = droite[i_droite]
        i_droite += 1
        i_tableau += 1

    return nb_inversions

Tri fusion avec des « sentinelles »

On considère dans cet exercice des tableaux non vides contenant des nombres entiers.

Il est possible d'alléger le fonctionnement de l'étape de fusion du tri fusion en ajoutant une « sentinelle » à la fin des tableaux gauche et droite (dans les faits on crée de nouveaux tableaux gauche_etendu et droite_etendu contenant les valeurs initiales suivies de la sentinelle).

Remarque

En algorithmique, une sentinelle est une valeur particulière dont la présence ou l'absence sert de critère d'arrêt à une boucle.

Cette sentinelle doit avoir une valeur strictement supérieure à celle du maximum du tableau initial. Ce faisant on peut alléger la fusion en ne faisant qu'une seule boucle :

📋 Pseudo-code

Tant que i_gauche est différent de longueur(gauche) OU i_différent est différent de longueur(droite):
    Si gauche[i_gauche] <= droite[i_droite]:
        Copier gauche[i_gauche] à la position i_tableau dans tableau
        i_gauche augmente de 1
    Sinon :
        Copier droite[i_droite] à la position i_tableau dans tableau
        i_droite augmente de 1
    i_tableau augmente de 1

Observons le comportement de cette méthode dans un exemple. On souhaite fusionner les tableaux gauche = [3, 9] et droite = [2, 5, 6].

La valeur maximale de ces deux tableaux est 9. On va donc ajouter la valeur 9 + 1 = 10 à la fin de chaque tableau. On obtient : gauche_etendu = [3, 9, 10] et droite_etendu = [2, 5, 6, 10].

Dès lors la fusion va se dérouler classiquement en copiant successivement les valeurs 2, 3, 5, 6 et 9. À ce stade, on aura i_gauche == len(gauche) et i_droite == len(droite). Les seuls éléments restant dans chaque sous-tableau sont les valeurs sentinelles : la fusion est donc terminée.

Compléter les fonctions sous_tableau et tri_fusion ci-dessous afin de mettre en œuvre cette méthode.

Les fonctions tri_fusion et fusion prennent désormais un argument supplémentaire : la valeur de la sentinelle à utiliser.

Astuce (1)

Si milieu est l'indice du « milieu » d'un tableau alors tableau[:milieu] renvoie la première moitié de ce tableau, tableau[milieu:] la seconde.

Astuce (2)

Il est possible d'« additionner » deux listes en faisant liste_1 + liste_2. Ainsi [3, 9] + [10] renvoie [3, 9, 10].

###

def fusion(gauche, droite, sentinelle):bksl-nl """bksl-nl Fusionne gauche et droitebksl-nl Les tableaux initiaux sont triésbksl-nl Le tableau résultat l'est aussibksl-nl """bksl-nl taillepy-undgauche = len(gauche)bksl-nl taillepy-unddroite = len(droite)bksl-nlbksl-nl gauchepy-undetendu = ...bksl-nl droitepy-undetendu = ...bksl-nlbksl-nl nouveau = [None] py-str (...)bksl-nlbksl-nl ipy-undnouveau = 0bksl-nl ipy-undgauche = 0bksl-nl ipy-unddroite = 0bksl-nlbksl-nl # Il reste des éléments à gauche ET à droitebksl-nl while ...:bksl-nl if gauchepy-undetendu[ipy-undgauche] <= droitepy-undetendu[ipy-unddroite]:bksl-nl nouveau[ipy-undnouveau] = gauchepy-undetendu[ipy-undgauche]bksl-nl ipy-undgauche += 1bksl-nl else:bksl-nl nouveau[ipy-undnouveau] = droitepy-undetendu[ipy-unddroite]bksl-nl ipy-unddroite += 1bksl-nl ipy-undnouveau += 1bksl-nlbksl-nl return nouveaubksl-nlbksl-nlbksl-nldef tripy-undfusion(tableau, sentinelle):bksl-nl """bksl-nl Trie tableau à l'aide du tri fusionbksl-nl Renvoie un nouveau tableau triébksl-nl """bksl-nl taille = len(tableau)bksl-nl # Cas de base, tableau de longueur 1 ou moinsbksl-nl if taille < 2:bksl-nl return tableaubksl-nlbksl-nl milieu = taille // 2bksl-nlbksl-nl # Tris récursifs des parties gauche et droitebksl-nl gauche = tripy-undfusion(..., ...)bksl-nl droite = tripy-undfusion(..., ...)bksl-nlbksl-nl return fusion(gauche, droite, ...)bksl-nlbksl-nlbksl-nltableau = [3, 1, 2]bksl-nlsentinelle = max(tableau) + 1bksl-nlassert tripy-undfusion(tableau, sentinelle) == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableau = [1, 2, 3, 4]bksl-nlsentinelle = max(tableau) + 1bksl-nlassert tripy-undfusion(tableau, sentinelle) == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableau = [-2, -5]bksl-nlsentinelle = max(tableau) + 1bksl-nlassert tripy-undfusion(tableau, sentinelle) == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nlprint("Bravo !")bksl-nlbksl-nl

Solution

🐍 Script Python

def fusion(gauche, droite, sentinelle):
    """
    Fusionne gauche et droite
    Les tableaux initiaux sont triés
    Le tableau résultat l'est aussi
    """
    taille_gauche = len(gauche)
    taille_droite = len(droite)

    gauche_etendu = gauche + [sentinelle]

    droite_etendu = droite + [sentinelle]

    nouveau = [None] * (taille_gauche + taille_droite)

    i_nouveau = 0
    i_gauche = 0
    i_droite = 0

    # Il reste des éléments à gauche ET à droite
    while i_gauche != taille_gauche or i_droite != taille_droite:
        if gauche_etendu[i_gauche] <= droite_etendu[i_droite]:
            nouveau[i_nouveau] = gauche_etendu[i_gauche]
            i_gauche += 1
        else:
            nouveau[i_nouveau] = droite_etendu[i_droite]
            i_droite += 1
        i_nouveau += 1

    return nouveau


def tri_fusion(tableau, sentinelle):
    """
    Trie tableau à l'aide du tri fusion
    Renvoie un nouveau tableau trié
    """
    taille = len(tableau)
    # Cas de base, tableau de longueur 1 ou moins
    if taille < 2:
        return tableau

    milieu = taille // 2

    # Tris récursifs des parties gauche et droite
    gauche = tri_fusion(tableau[:milieu], sentinelle)
    droite = tri_fusion(tableau[milieu:], sentinelle)

    return fusion(gauche, droite, sentinelle)

Les appels de la fonction de tri fusion doivent donc désormais contenir la valeur de la sentinelle :

🐍 Script Python

tableau = [307, 198, 203, -500]
resultat = tri_fusion(tableau, max(tableau) + 1)

Python offre aussi une solution alternative à l'aide de l'objet float('inf'). Ce nombre flottant est en effet strictement supérieur à n'importe quel nombre entier int manipulé par Python. Il est possible d'utiliser ce valeur comme sentinelle. On alors simplement passer une valeur par défaut au paramètre sentinelle :

🐍 Script Python

def tri_fusion(tableau, sentinelle=float('inf')):
    pass

Partition et tri rapide

La méthode de partition utilisé dans le tri rapide présentée dans ce cours est dite « méthode de Lomuto » (Nico Lomuto est un chercheur ayant, entre autres choses, participé à la création du langage Ada).

Il en existe une seconde proposée par C.A.R. Hoare, l'inventeur du tri. Cette méthode permet de limiter le nombre d'échanges de valeurs.

L'idée est la suivante :

On cherche toujours à placer au début de la zone à trier les valeurs inférieures ou égales au pivot, à la fin les valeurs strictement supérieures ;
Le pivot est la valeur située au début de la zone du tableau à trier. On le laisse à cette position intiale ;
On crée deux variables gauche (initialisée à l'indice du début de la zone à trier) et droite (initialisée à l'indice de la fin de la zone à trier) ;
Tant que gauche est strictement inférieur à droite :
- Incrémenter gauche tant qu'elle est strictement inférieure à l'indice de la fin de la zone à trier et que tableau[gauche] <= pivot ;
- Décrémenter droite tant qu'elle est supérieure ou égale à gauche et que tableau[droite] > pivot ;
- Si gauche est strictement inférieur à droite, échanger les éléments d'indices gauche et droite.

Cette boucle étant terminée :

On échange le pivot et l'élément d'indice droite ;
On trie récursivement les sous-tableaux allant entre les indices debut inclus et droite exclus (premier tableau) et droite + 1 inclus et fin exclus (second tableau).

Compléter la fonction tri_rapide_hoare prenant en argument un tableau ainsi que deux entiers debut et fin et triant le tableau entre les indices debut (inclus) et fin (exclu) à l'aide du tri rapide et utilisant la partition de Hoare.

###

Solution

🐍 Script Python

def tri_rapide_hoare(tableau, debut, fin):
    if debut >= fin:
        return

    pivot = tableau[debut]
    gauche = debut
    droite = fin - 1

    while gauche < droite:
        while gauche < fin and tableau[gauche] <= pivot:
            gauche += 1
        while droite >= gauche and tableau[droite] > pivot:
            droite -= 1
        if gauche < droite:
            tableau[gauche], tableau[droite] = tableau[droite], tableau[gauche]

    tableau[debut], tableau[droite] = tableau[droite], tableau[debut]
    # Appels récursifs
    tri_rapide_hoare(tableau, debut, droite)
    tri_rapide_hoare(tableau, droite + 1, fin)

Complément

On pourra lire cette page qui précise les différences entre ces deux méthodes.