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]
    """