Aller au contenu

Exercices d'entraînement Tri par sélection☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

  • Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
  • Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
  • Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
  • Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
  • Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?
Rappels
  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [G03_Algo_Tri] avec le nom donné à l'exercice : ProgG03.53.py, ProgG03.54.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Exercice G03.51☘

Illustrez sur votre cahier le tri par sélection du minimum avec le tableau suivant :

tab = 8 1 7 2 4 3 1 6
Une solution

Étape n°0 : tab = 8 1 7 2 4 3 1 6 indice du minimum : 1

Étape n°1 : tab = 1 8 7 2 4 3 1 6 indice du minimum : 6

Étape n°2 : tab = 1 1 7 2 4 3 8 6 indice du minimum : 3

Étape n°3 : tab = 1 1 2 7 4 3 8 6 indice du minimum : 5

Étape n°4 : tab = 1 1 2 3 4 7 8 6 indice du minimum : 4

Étape n°5 : tab = 1 1 2 3 4 7 8 6 indice du minimum : 7

Étape n°6 : tab = 1 1 2 3 4 6 8 7 indice du minimum : 7

Étape n°7 : tab = 1 1 2 3 4 6 7 8

Exercice G03.52☘

On veut trier, comme avec les cartes de l'activité d'introduction, le tableau :

main = 4 2 7 1 8 5 3

Pour cela, on initialise un tableau vide, nommé tas, et on pose, au fur et à mesure, à la fin du tableau tas, le plus petit élément qu'on a sélectionné dans le tableau main.

  • Au départ le tableau tas est vide.
    On recherche la plus petite carte de la main :
 main = 4 2 7 1 8 5 3
  tas =
  • On enlève cette carte de la main, on la place sur le tas.
    On reconstruit la main avec les cartes restantes et on recherche la plus petite carte de ces cartes :
main = 4 2 7 8 5 3
  tas = 1
  • On enlève cette carte de la main, on la place sur le tas.
    On reconstruit la main avec les cartes restantes puis on sélectionne la plus petite de ces cartes :
main = 4 7 8 5 3
  tas = 1 2
  • On recommence :
main = 4 7 8 5
  tas = 1 2 3
  • Puis :
main = 7 8 5
  tas = 1 2 3 4
  • Puis :
main = 7 8
  tas = 1 2 3 4 5
  • Puis :
main = 8
  tas = 1 2 3 4 5 7
  • On s'arrête lorsque la main est vide, le tas est trié :
main =
  tas = 1 2 3 4 5 7 8

A vous !☘

Illustrez de même, sur votre cahier, ce tri avec la main suivante :

main = 8 1 7 2 4 3 1 6
Une solution

• main = 8 1 7 2 4 3 1 6
     tas =

• main = 8 7 2 4 3 1 6
     tas = 1

• main = 8 7 2 4 3 6
     tas = 1 1

• main = 8 7 4 3 6
     tas = 1 1 2

• main = 8 7 4 6
     tas = 1 1 2 3

• main = 8 7 6
     tas = 1 1 2 3 4

• main = 8 7
     tas = 1 1 2 3 4 6

• main = 8
     tas = 1 1 2 3 4 6 7

• main =
     tas = 1 1 2 3 4 6 7 8

ProgG03.53 - Reconstruire un tableau☘

Copiez/collez et complétez le corps de la fonction reconstruit() en respectant ses spécifications. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def reconstruit(tab, k):
    """
    tab – list, tableau d'éléments
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: list – NOUVEAU tableau constitué des éléments de tab privé de
            celui d'indice k, c'est-à-dire la réunion de tab[..k-1] et tab[k+1..]
    >>> tab = [2, -2, 5, 1, 2, 1]
    >>> reconstruit(tab, 2)
    [2, -2, 1, 2, 1]
    """

Attention

L'appel suivant doit générer des erreurs : 

>>> reconstruit([3, 1, 7, 4], 5)
AssertionError: tab index out of range

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def reconstruit(tab, k):
    """
    tab – list, tableau d'éléments
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: list – NOUVEAU tableau constitué des éléments de tab privé de
            celui d'indice k, c'est-à-dire la réunion de tab[..k-1] et tab[k+1..]
    >>> tab = [2, -2, 5, 1, 2, 1]
    >>> reconstruit(tab, 2)
    [2, -2, 1, 2, 1]
    """
    assert 0 <= k < len(tab), "tab index out of range"
    result = []
    for i in range(k):
        result.append(tab[i])
    for i in range(k+1, len(tab)):
        result.append(tab[i])
    return result
Une autre solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def reconstruit(tab, k):
    """
    tab – list, tableau d'éléments
    k – int, entier compris entre 0 et len(tab)-1
    Sortie: list – NOUVEAU tableau constitué des éléments de tab privé de
            celui d'indice k, c'est-à-dire la réunion de tab[..k-1] et tab[k-1..]
    >>> tab = [2, -2, 5, 1, 2, 1]
    >>> reconstruit(tab, 2)
    [2, -2, 1, 2, 1]
    """
    assert 0 <= k < len(tab), "tab index out of range"
    return [tab[i] for i in range(len(tab)) if i != k]

ProgG03.54 - Tri par sélection dans un nouveau tableau☘

L'algorithme est similaire à celui du tri DANS le tableau initial :

T ← []

Pour i variant de 0 à n-1 :
    Rechercher l'indice du plus petit élément de tab
    Retirer cet élément de tab
    Placer cet élément à la fin de T   

Renvoyer T

Il reste à définir ce que signifie cette instruction Retirer par un nouvel algorithme :

tab est un tableau dans lequel on souhaite retirer l'élément d'indice k.

temp = tab[k]
tab ← tab[..k-1] + tab[k+1..]
Renvoyer temp

Copiez/collez et complétez le corps de la fonction tri_selection_nouveau() en respectant ses spécifications. 

1
2
3
4
5
6
7
8
9
def tri_selection_nouveau(tab):
    """
    tab – list, tableau d'éléments comparables
    Sortie: list – tableau contenant les mêmes éléments que
            ceux de tab, mais triés par ordre croissant
    >>> T = [5, 7, 2, 8, 1, 2, 5, 4]
    >>> tri_selection_nouveau(T)
    [1, 2, 2, 4, 5, 5, 7, 8]
    """
Une piste

N'oubliez pas que vous avez défini une fonction dans l'exercice précédent.

Une autre piste

N'oubliez pas de rechercher l'indice du plus petit élément du tableau, peut-être à l'aide d'une nouvelle fonction...

Une solution

On définit une fonction de recherche de l'indice du minimum d'un tableau et on fait appel à la fonction reconstruit() définie dans l'exercice précédent. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def indice_du_minimum(tab):
    """
    tab – list, tableau d'éléments comparables
    Sortie: int – indice du plus petit élément de tab
    >>> T = [5, 7, 2, 8, 1, 2, 5, 4]
    >>> indice_du_minimum(T)
    4
    """
    assert len(tab) != 0, "Le tableau est vide"
    mini = tab[0]
    indice_mini = 0
    for i in range(len(tab)):
        if tab[i] < mini:
            mini = tab[i]
            indice_mini = i
    return indice_mini


def tri_selection_nouveau(tab):
    """
    tab – list, tableau d'éléments comparables
    Sortie: list – tableau contenant les mêmes éléments que
            ceux de tab, mais triés par ordre croissant
    >>> T = [5, 7, 2, 8, 1, 2, 5, 4]
    >>> tri_selection_nouveau(T)
    [1, 2, 2, 4, 5, 5, 7, 8]
    """
    result = []
    n = len(tab)
    for i in range(n):
        indice_mini = indice_du_minimum(tab)
        temp = tab[indice_mini]
        tab = reconstruit(tab, indice_mini)
        result.append(temp)
    return result