Algorithmes de tri

Introduction

Dans ce TP, on cherche à implémenter des algorithmes qui permettent de trier un tableau. On considérera que tous les tableaux sont non vides (sinon il n'y a rien à trier !). On peut trier un tableau de deux manières différentes : soit par ordre croissant, soit par ordre décroissant : lorsque l'on dira "le tableau est trié" dans ce TP, on sous-entendra qu'il est trié par ordre croissant. On commence par écrire le code de certaines fonctions qui seront utiles par la suite.

Écrire le code de la fonction genere_tableau prend en arguments un entier n et deux entiers x_min et x_max et qui renvoie un tableau de n entiers tirés au hasard compris entre x_min et x_max inclus.

On utilisera pour cela la fonction randint du module random, dont on donne un exemple d'utilisation ci-dessous. randint(x, y) renvoie un entier choisi aléatoirement entre x et y inclus.

from random import randint

print(randint(-5, 5))
print(randint(-5, 5))
print(randint(-5, 5))

 

⚙️ Résultat

3
-5
1

def genere_tableau(n, x_min, x_max):
    """ int, int, int -> [int]
    Renvoie un tableau d'entiers tirés au hasard parmi [x_min, x_max] """
    pass

Écrire le code de la fonction est_trie qui prend en argument un tableau tab et qui renvoie True si le tableau est trié par ordre croissant, False sinon.

Pour cela, on parcourera tous les éléments du tableau les uns après les autres : si on trouve un élément d'indice i tel que l'élément d'indice i + 1 lui est inférieur, alors cela signifie que le tableau n'est pas trié par ordre croissant. Au contraire, si on ne trouve pas un tel élément, cela signifie que le tableau est trié par ordre croissant.

def est_trie(tab):
    """ [int] -> bool
    Renvoie True si tab est trié par ordre croissant, False sinon """
    pass

Écrire le code de la fonction echange qui prend en argument un tableau tab et deux indices i et j compatibles avec la taille du tableau. Cette fonction modifie tab en place et échange la position des éléments d'indice i et j dans tab.

def echange(tab, i, j):
    """ [int], int, int -> None
    Échange les éléments d'indice i et j dans tab """
    pass

Tri par insertion

On cherche à implémenter l'algorithme du tri par insertion. L'idée de cette algorithme est la suivante :

• on maintient une zone triée d'éléments tous situés au début du tableau. Initialement cette zone est vide et contient 0 élément.

  

• tant que tous les éléments du tableau ne se trouvent pas dans la zone triée :

  • on choisit un élément en dehors de cette zone triée (habituellement l'élément du tableau qui se situe juste après le dernier élément de la zone triée) ;

  • on l'insère dans la zone triée en réalisant des échanges successifs avec l'élément précédent dans le tableau. On réalise ces échanges tant que le nouvel élément n'est pas le premier élément du tableau et si le nouvel élément est plus petit que l'élément qui le précède.

    

Après chaque insertion dans la zone triée du tableau, celle-ci est constituée d'un élément de plus. Si n est la taille du tableau et que l'on réalise n insertions, alors à l'issue de cet algorithme le tableau est complètement trié.

1. Jouer au jeu du tri par insertion à l'adresse :

   https://www.advanced-ict.info/interactive/insertion_sort.html

   Vous ne devez pas faire d'erreur. 2. Compléter le code de la fonction tri_insertion qui prend en argument un tableau tab et qui le trie en place à l'aide de l'algorithme du tri par insertion.

def tri_insertion(tab):
    """ [int] -> None
    Trie le tableau en place. """
    # Si le tableau est vide il n'y a rien à faire.
    if len(tab) == 0:
        return
    zone_triee = 0
    # Tant qu'il y a des éléments à trier dans le tableau
    while ...:
        pos_nouveau = zone_triee
        nouveau_elem = tab[zone_triee]
        # On échange le nouvel élément avec
        # l'élément du tableau qui se trouve
        # à sa gauche tant que cela est nécessaire 
        while ...:
            echange(tab, ..., ...)
            pos_nouveau = ... # on met à jour la position du nouvel élément
        # Il y a un élément de plus dans la zone triée
        zone_triee = ...

Tri à bulle

On cherche à implémenter l'algorithme du tri à bulles. L'idée de cet algorithme est la suivante. Si $n$ est le nombre d'éléments du tableau, on réalise $n$ passages : on parcourt le tableau de gauche à droite. Si deux éléments consécutifs ne sont pas rangés dans l'ordre croissant, alors on échange leurs positions.

À la fin du premier passage le plus grand élément du tableau se trouve à la fin du tableau : il est correctement placé. À la fin du deuxième passage, le deuxième plus grand élément se trouve à l'avant dernière position du tableau : il est correctement placé. De même, à la fin du $n$-ième passage le plus petit élément se trouve au début du tableau : il est correctement placé.

1. Jouer au jeu du tri à bulle à l'adresse :

   https://www.advanced-ict.info/interactive/bubble_sort.html

   Vous ne devez pas faire d'erreur. 2. Compléter le code de la fonction tri_bulles qui prend en argument un tableau tab et qui le trie en place à l'aide de l'algorithme du tri à bulles.

def tri_bulles(tab):
    """ [int] -> None
    Trie le tableau en place.  """
    if len(tab) == 0:
        return
    for passage in range(...):
        for i in range(...):
            # si deux éléments consécutifs ne sont
            # pas bien ordonnés, on échange leur position
            if ...:
                echange(...)

Tri par sélection

On cherche à implémenter l'algorithme du tri par sélection, qui présente un fonctionnement similaire au tri à bulle : plutôt que d'échanger deux éléments consécutifs, on fait directement remonter le maximum "au bon endroit". Ainsi, on réalise $n$ passages, et, lors du $i$-ième passage, on calcule le maximum parmi les $n - i + 1$ premiers éléments du tableau. On échange ce maximum avec le $(n - i + 1)$-ième élément du tableau.

1. Écrire le code de la fonction maximum_parmi qui prend en argument un tableau tab et un entier i qui renvoie l'indice du plus grand élément de tab parmi les i premiers éléments de tab.
2. Compléter le code de la fonction tri_selection qui prend en argument un tableau tab et qui le trie en place à l'aide de l'algorithme du tri par sélection.

def maximum_parmi(tab, i):
    """ [int], int -> int
    Renvoie l'indice du maximum parmi les n-i+1 premiers éléments de tab """
    pass

def tri_selection(tab):
    """ [int] -> None """
    for i in range(...):
        i_maxi = ...
        echange(...)

 

tab = [9, 5, 6, 4, -3, 0, 8, 1]
tri_selection(tab)
print(tab)

⚙️ Résultat

[-3, 0, 1, 4, 5, 6, 8, 9]