Aller au contenu

TP - Tri par Insertion

Ce TP a pour objectif de vous faire programmer de différentes façons l'algorithme de tri par insertion.

Téléchargez, enregistrez et complétez le fichier TPG03.20.py dans le répertoire [G03_Algo_Tri] préalablement créé dans votre répertoire personnel.

Consignes communes à chaque partie

Le programme principal devra contenir un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()
Chacune des fonctions devra passer les tests proposés.
Il faudra aussi ajouter vos propres tests dans le « main » afin de vous entraîner à en réaliser.
Par exemple, en cherchant à trier le tableau suivant :
fruits = ['poire', 'pomme', 'abricot', 'kiwi', 'orange', 'noix', 'noisette', 'cerise', 'brugnon', 'nectarine', 'prune', 'groseille', 'framboise']

Une aide

Vous pouvez programmer des fonctions supplémentaires, déjà étudiées en classe et qui peuvent vous aider à programmer les fonctions de ce TP.

TPG03.21 : Tri (croissant) par insertion

  1. Complétez la définition de la fonction inserer_crois() qui prend en paramètres un tableau tab et un entier i compris entre 0 et le dernier indice du tableau. Les éléments de tab situés entre les indices 0 et i-1 sont déjà triés par ordre croissant.
    Cette fonction modifie par effet de bord le contenu du tableau tab de sorte que tab[..i] soit trié après l'exécution de inserer_crois(tab, i).

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def inserer_crois(tab, i):
        """
        tab – list, tableau d'entiers tel que tab[0..i-1] est trié par
                    ordre croissant
        i – int, entier compris entre 0 et len(tab)-1
        Sortie: None – le tableau tab est tel que tab[0..i] est trié par
                ordre croissant (effet de bord)
        >>> A = [2, 4, 5, 1, 4, -2]
        >>> inserer_crois(A, 3)
        >>> A
        [1, 2, 4, 5, 4, -2]
        >>> inserer_crois(A, 4)
        >>> A
        [1, 2, 4, 4, 5, -2]
        >>> inserer_crois(A, 3)
        >>> A
        [1, 2, 4, 4, 5, -2]
        """
    

    Il faudra que le programme lève l'erreur suivante :

    >>> inserer_crois([2, 6, 3, 9, 4, 42], 15)
    AssertionError: paramètre i out of range
    
  2. Complétez la définition de la fonction tri_insertion_crois() qui prend en paramètre un tableau . Cette fonction agit par effet de bord et trie les éléments du tableau par ordre croissant.

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    def tri_insertion_crois(tab):
        """
        tab – list, tableau d'éléments comparables
        Sortie: None – Les éléments de tab sont triés par ordre croissant
                (effet de bord)
        >>> A = [5, 7, 2, 8, 1, 2, 5, 4]
        >>> tri_insertion_crois(A)
        >>> A
        [1, 2, 2, 4, 5, 5, 7, 8]
        """
    

TPG03.22 : Tri (décroissant) par insertion

  1. Complétez la définition de la fonction inserer_decrois() qui prend en paramètres un tableau tab et un entier i compris entre 0 et le dernier indice du tableau. Les éléments de tab situés entre les indices 0 et i-1 sont déjà triés par ordre décroissant.
    Cette fonction modifie par effet de bord le contenu du tableau tab de sorte que tab[..i] soit trié après l'exécution de inserer_decrois(tab, i).

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def inserer_decrois(tab, i):
        """
        tab – list, tableau d'entiers tel que tab[0..i-1] est trié par
                    ordre décroissant
        i – int, entier compris entre 0 et len(tab)-1
        Sortie: None – le tableau tab est tel que tab[0..i] est trié par
                ordre décroissant (effet de bord)
        >>> A = [5, 4, 2, 1, 4, 8]
        >>> inserer_decrois(A, 3)
        >>> A
        [5, 4, 2, 1, 4, 8]
        >>> inserer_decrois(A, 4)
        >>> A
        [5, 4, 4, 2, 1, 8]
        >>> inserer_decrois(A, 5)
        >>> A
        [8, 5, 4, 4, 2, 1]
        """
    

    Il faudra que le programme lève l'erreur suivante :

    >>> inserer_decrois([2, 6, 3, 9, 4, 42], -2)
    AssertionError: paramètre i out of range
    
  2. Complétez la définition de la fonction tri_insertion_decrois() qui prend en paramètre un tableau . Cette fonction agit par effet de bord et range les éléments du tableau par ordre décroissant.

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    def tri_insertion_decrois(tab):
        """
        tab – list, tableau d'éléments comparables
        Sortie: None – Les éléments de tab sont triés par ordre décroissant
                (effet de bord)
        >>> A = [5, 7, 2, 8, 1, 2, 5, 4]
        >>> tri_insertion_decrois(A)
        >>> A
        [8, 7, 5, 5, 4, 2, 2, 1]
        """