Aller au contenu

21 Exos Tris

Quelques fonctions utiles⚓︎

Échange de deux valeurs dans une liste⚓︎

É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.

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.

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]:
                # ... À compléter
        # ... À compléter
    return L

Complexité⚓︎

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

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.

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:
            # ... À compléter
            # ... À compléter
        # on insère l'élément à sa place
        L[j] = en_cours
    return L

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 ?

  2. Quelle est la complexité de l'algorithme de tri par sélection ?

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.

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]).
  2. À la fin du premier tour de la boucle while, où se trouve la plus grande valeur de tableau ?
  3. Quelle est la complexité de ce tri à bulle ?
  4. Le tri à bulle est-il stable ? en place ?

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.
  2. Quelle est la complexité du tri gnome au pire cas ?