Aller au contenu

21 Exos Tris Correction

Quelques fonctions utiles⚓︎

Écrire une fonction echanger() qui prend en paramètres une liste L et deux entiers i et j et qui renvoie la liste L où les éléments d’indice i et j ont été échangés.

En utilisant une variable temporaire :

🐍 Script Python
def echanger(L, i, j):
    val_temporaire = L[j]
    L[j] = L[i]
    L[i] = val_temporaire
    return L

assert echanger([21, 22, 23, 24, 25, 26], 1, 3) == [21, 24, 23, 22, 25, 26]

En Python, on peut utiliser une syntaxe spécifique :

🐍 Script Python
def echanger(L, i, j):
    L[i], L[j] = L[j], L[i]
    return L

assert echanger([21, 22, 23, 24, 25, 26], 1, 3) == [21, 24, 23, 22, 25, 26]

Vérifier qu’une liste est bien triée⚓︎

Une liste L est bien triée si et seulement si :

pour tous \(i,j \in \left[0,\dots,n-1\right]\), \(i < j \implies L[i] < L[j]\)

Écrire une fonction est_triee() qui prend en paramètre une liste L et renvoie le booléen True si la liste est triée, False sinon.

On l'a fait dans la fiche "Dichotomie et parcours séquentiel".

🐍 Script Python
import doctest

def est_triee(liste):
    """
    Entrée : liste - liste d'entiers (list)

    Sortie : booléen - True si liste est triée en ordre croissant, False sinon.

    Exemples
    >>> est_triee([2, 6, 8, 9])
    True
    >>> est_triee([])
    True
    >>> est_triee([2, 3, 4, 1])
    False
    """
    for indice in range(len(liste)-1):
        if liste[indice + 1] < liste[indice]:
            return False
    return True

print(doctest.testmod())

Exercice 1 : Tri par sélection⚓︎

Programme⚓︎

Compléter le code python du tri par selection.

🐍 Script Python
def tri_selection(L):
    '''Prend en argument une liste et la retourne triée'''
    assert type(L) is list, "Fournir un type list en argument !"
    for i in range(len(L) - 1):
        indice_du_min = i # l'indice temporaire du plus petit élément
        for j in range(i + 1, len(L)):
            # parcours de la liste partielle à la recherche de l'indice du plus petit élément de la sous-liste
            if L[j] < L[indice_du_min]:
                indice_du_min = j
        L = echanger(L, i, indice_du_min)
    return L

print(tri_selection([24, 1, 7, 34, 5, 3, 27, 31, 18]))
assert est_triee(tri_selection([24, 1, 7, 34, 5, 3, 27, 31, 18]))

Complexité⚓︎

Quelle est la complexité de l'algorithme de tri par sélection dans le pire des cas ?

La boucle for principale est exécutée \(n\) fois, avec à chaque fois une boucle secondaire qui sera exécutée \(n-1\) fois, puis \(n-2\) fois, puis ... jusqu'à \(1\) fois.

On a donc une complexité quadratique en \(\mathcal{O}(n^2)\).

Sélection externe⚓︎

Au lieu de modifier le contenu de la liste pour la trier (et de faire un tri en place), on peut aussi renvoyer le résultat du tri dans une nouvelle liste (le tri n’est plus “en place” dans ce cas). Écrire une fonction tri_sélection_externe qui réalise cette idée avec le tri par sélection.

🐍 Script Python
def tri_selection_externe(L):
    '''Prend en argument une liste et retourne une nouvelle liste avec les mêmes éléments mais triée'''
    assert type(L) is list, "Fournir un type list en argument !"
    n = len(L)
    Lcopie = L.copy()
    L2 = []
    for i in range(n):
        indice_du_min = 0 # l'indice temporaire du plus petit élément
        for j in range(len(Lcopie)):
            # parcours de la liste partielle à la recherche de l'indice du plus petit élément de la sous-liste
            if Lcopie[j] < Lcopie[indice_du_min]:
                indice_du_min = j
        L2.append(Lcopie[indice_du_min])
        del Lcopie[indice_du_min]
    return L2

L3 = tri_selection_externe([24, 1, 7, 34, 5, 3, 27, 31, 18])
print(L3)
assert est_triee(L3)

Exercice 2 : Tri par insertion⚓︎

Programme⚓︎

Compléter le code python du tri par insertion.

🐍 Script Python
def tri_insertion(L):
    """
    Entrée : une liste d'éléments int ou float, ou str
    Sortie : la liste constituée des même éléments, triée par ordre croissant
    """
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        # décalage des éléments de la liste
        while j > 0 and L[j - 1] > en_cours:
            L[j] = L[j - 1]
            j -= 1 
        # on insère l'élément à sa place
        L[j] = en_cours
    return L

L3 = tri_insertion([24, 1, 7, 34, 5, 3, 27, 31, 18])
print(L3)
assert est_triee(L3)

Complexité⚓︎

  1. Que se passe passe-t-il lorsque le tri par insertion est appliqué à un tableau qui se présente en ordre décroissant ?
    C'est le pire des cas, puisque chaque boucle et chaque condition sera exécutée.

  2. Quelle est la complexité de l'algorithme de tri par sélection ?
    La boucle for principale est exécutée \(n\) fois, avec à chaque fois une boucle secondaire qui, dans le pire des cas, sera exécutée \(1\) fois, puis \(2\) fois, puis ... \(n-1\) fois.

On a donc une complexité quadratique en \(\mathcal{O}(n^2)\).

Insertion externe⚓︎

Au lieu de modifier le contenu de la liste pour la trier, on peut aussi renvoyer le résultat du tri dans une nouvelle liste (le tri n’est plus “en place” dans ce cas). Écrire une fonction tri_insertion_externe qui réalise cette idée avec le tri par insertion.

🐍 Script Python
def tri_insertion_externe(L):
    """
    Entrée : une liste d'éléments int ou float, ou str
    Sortie : la liste constituée des même éléments, triée par ordre croissant
    """
    L2 = [L[0]]
    for i in range(1, len(L)):
        en_cours = L[i]
        j = i
        # décalage des éléments de la liste
        while j > 0 and L2[j - 1] > en_cours:
            j -= 1 
        # on insère l'élément à sa place
        L2.insert(j, en_cours)
    return L2

L3 = tri_insertion_externe([24, 1, 7, 34, 5, 3, 27, 31, 18])
print(L3)
assert est_triee(L3)

Exercice 3 : Tri bulle⚓︎

Voici l’algorithme du tri à bulle implémenté en Python.

🐍 Script Python
def triBulle(liste):
    for i in range(len(liste)):
        for j in range(0, len(liste) - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
    return liste

  1. Écrire la trace de l’appel de tri_bulle([5,3,1]).
    tri_bulle([5,3,1]) :
    len(liste) vaut \(3\)
    i = 0 :
    len(liste) - i - 1 vaut \(2\)
    j = 0 :
    si liste[j] > liste[j + 1] revient à liste[0] > liste[1], dans notre cas 5 > 3 ?
    ce qui est vrai, donc on fait l'échange : liste[j], liste[j+1] = liste[j+1], liste[j]
    On a donc maintenant la liste L = [3, 5, 1]
    j = 1 :
    si liste[j] > liste[j + 1] revient à liste[1] > liste[2], dans notre cas 5 > 1 ?
    ce qui est vrai, donc on fait l'échange : liste[j], liste[j+1] = liste[j+1], liste[j]
    On a donc maintenant la liste L = [3, 1, 5]

    i = 1 :
    len(liste) - i - 1 vaut \(1\)
    j = 0 :
    si liste[j] > liste[j + 1] revient à liste[0] > liste[1], dans notre cas 3 > 1 ?
    ce qui est vrai, donc on fait l'échange : liste[j], liste[j+1] = liste[j+1], liste[j]
    On a donc maintenant la liste L = [1, 3, 5]

    i = 2 :
    len(liste) - i - 1 vaut \(0\)
    Il n'y a plus rien à faire.

  2. À la fin du premier tour de la boucle while, où se trouve la plus grande valeur de tableau ?
    A la fin du premier tour de boucle while la plus grande valeur a été échangée, puis échangée, jusqu'à finir à la fin de la liste. C'est pour cela que le tri s'appelle tri à bulle : ce sont comme des bulles qui remontent à la surface...

  3. Quelle est la complexité de ce tri à bulle ?
    On a \(1 + 2 + ... + n-1\) tours de boucle.
    Le tri est de complexité quadratique.

  4. Le tri à bulle est-il stable ? en place ?
    Le tri est stable car il est fait sur la liste de départ par échanges successifs.
    Le tri est en place car un échange n'est fait que quand la valeur devant est strictement supérieure à la valeur suivante.

Exercice 4 : Tri Gnome⚓︎

Cet algorithme a été d’abord proposé en 2000, sous le nom de « tri stupide », par le Dr. Hamid Sarbazi-Azad (Professeur à l’université de Sharif, une des plus grandes universités d’Iran) puis redécouvert plus tard par Dick Grune (le premier développeur de CVS) qui l’appela « gnome sort » (parce qu’il parait que c’est la méthode qu’utilisent les nains de jardin hollandais pour trier une rangée de pots de fleurs).

L’algorithme est similaire au tri par insertion, sauf que, au lieu d'insérer directement l’élément à sa bonne place, l’algorithme effectue une série de permutations, comme dans un tri bulle.

Méthode. Dans le tri gnome, on commence par le début du tableau, on compare deux éléments consécutifs (i et i + 1) : s’ils sont dans l’ordre on se déplace d’un cran vers la fin du tableau (incrémente) ou on s’arrête si la fin est atteinte ; sinon, on les permute et on se déplace d’un cran vers le début du tableau (décrémente) ou si on est au début du tableau alors on se déplace d’un cran vers la fin (incrémente).

  1. Écrire une implémentation en python de ce tri.

    🐍 Script Python
    def tri_insertion(L):
    """
    Entrée : une liste d'éléments int ou float, ou str
    Sortie : la liste constituée des même éléments, triée par ordre croissant
    """
    for i in range(1, len(L)):
        j = i
        # décalage des éléments de la liste
        while j > 0 and L[j - 1] > L[j]:
            L[j - 1], L[j] = L[j], L[j - 1]
            j -= 1
    return L

  2. Quelle est la complexité du tri gnome au pire cas ?
    C'est le même principe que le tri par insertion, avec juste un peu plus d'affectation pour les échanges / décalages, la complexité est donc également quadratique.