Aller au contenu

TP - Tri par Sélection☘

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

Téléchargez, enregistrez et complétez le fichier TPG03.10.py dans le dossie [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.11 : Tri par sélection du minimum☘

  1. Complétez la définition de la fonction selectionne_indice_mini() qui prend en paramètres un tableau tab et un entier i compris entre 0 et le dernier indice du tableau. Cette fonction renvoie l'indice du plus petit élément du sous-tableau tab[i..].

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def selectionne_indice_mini(tab, i):
    """
    tab – list, tableau de n éléments munis d'une relation d'ordre
    i – int, entier compris entre 0 et n-1
    Sortie: int – indice du minimum de tab[i..]
    >>> T = [2, -2, 5, 1, 2, 1]
    >>> selectionne_indice_mini(T, 0)
    1
    >>> selectionne_indice_mini(T, 4)
    5
    """

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

    >>> selectionne_indice_mini([2, 6, 3, 9, 4, 42], 15)
AssertionError: paramètre i out of range

  2. Complétez la définition de la fonction tri_selection_mini() 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_selection_mini(tab):
    """
    tab – list, tableau d'entiers
    Sortie: None – Les éléments de tab sont triés par ordre croissant
            (fonction à effet de bord)
    >>> T = [5, 7, 2, 8, 1, 2, 5, 4]
    >>> tri_selection_mini(T)
    >>> T
    [1, 2, 2, 4, 5, 5, 7, 8]
    """

TPG03.12 : Tri par sélection du maximum☘

  1. Complétez la définition de la fonction selectionne_indice_maxi() qui prend en paramètres un tableau tab et un entier i compris entre 0 et le dernier indice du tableau. Cette fonction renvoie l'indice du plus grand élément du sous-tableau tab[..i].

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def selectionne_indice_maxi(tab, i):
    """
    tab – list, tableau de n éléments munis d'une relation d'ordre
    i – int, entier compris entre 0 et n-1
    Sortie: int – indice du maximum de tab[..i]
    >>> T = [2, -2, 5, 1, 2, 1]
    >>> selectionne_indice_maxi(T, 1)
    0
    >>> selectionne_indice_maxi(T, 5)
    2
    """

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

    >>> selectionne_indice_maxi([2, 6, 3, 9, 4, 42], -3)
AssertionError: paramètre i out of range

  2. Complétez la définition de la fonction tri_selection_maxi() 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_selection_maxi(tab):
    """
    tab – list, tableau d'entiers
    Sortie: None – Les éléments de tab sont triés par ordre croissant
            (fonction à effet de bord)
    >>> T = [5, 7, 2, 8, 1, 2, 5, 4]
    >>> tri_selection_maxi(T)
    >>> T
    [1, 2, 2, 4, 5, 5, 7, 8]
    """

TPG03.13 : Une autre sélection du minimum☘

Il n'est pas nécessaire de faire appel à une variable indice_mini pour réaliser un tri par sélection. Voici un autre algorithme pouvant convenir :

  • On compare la valeur de tab[0] avec celle de tab[1], puis celle de tab[2] … jusqu'à celle de tab[n-1].

  • A chaque fois que la valeur de tab[i] est inférieure à celle de tab[0], on échange les valeurs de tab[0] et tab[i].

  • Une fois tout le tableau parcouru, tab[0] contient forcément la valeur minimum de ce tableau.

  • Complétez la définition de la fonction selectionne() qui prend en paramètres un tableau tab et un entier i compris entre 0 et le dernier indice du tableau. Cette fonction à effet de bord place le minimum de tab[i] à l'indice i selon l'algorithme décrit ci-dessus.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def selectionne(tab, i):
    """
    tab – list, tableau de n éléments munis d'une relation d'ordre
    i – int, entier compris entre 0 et n-1
    Sortie: None – le minimum de tab[i..] est positionné à l'indice i
    >>> T = [2, -2, 5, 1, 2, 1]
    >>> selectionne(T, 0)
    >>> T
    [-2, 2, 5, 1, 2, 1]
    >>> selectionne(T, 4)
    >>> T
    [-2, 2, 5, 1, 1, 2]
    """

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

    >>> selectionne([2, 6, 3, 9, 4, 42], 6)
AssertionError: paramètre i out of range

  • Complétez la définition de la fonction tri_selection() qui prend en paramètre un tableau . Cette fonction agit par effet de bord et trie les éléments du tableau par ordre croissant en appliquant successivement l'algorithme présenté en introduction pour chaque élément du tableau.

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