Exercices d'entraînement Tri par insertion

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.62.py, ProgG03.63.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.61

Illustrez sur votre cahier le tri par insertion croissant avec le tableau suivant :

tab =

8

1

7

2

4

3

1

6

Une solution

tab =

8

1

7

2

4

3

1

6

tab =

8

1

7

2

4

3

1

6

tab =

1

8

7

2

4

3

1

6

tab =

1

7

8

2

4

3

1

6

tab =

1

2

7

8

4

3

1

6

tab =

1

2

4

7

8

3

1

6

tab =

1

2

3

4

7

8

1

6

tab =

1

1

2

3

4

7

8

6

tab =

1

1

2

3

4

6

7

8

ProgG03.62 - Tri de moyennes

Les notes d'un élève sont regroupées dans un t-uplet.
Les notes de la classe sont regroupées dans un tableau de notes d'élèves.
On souhaite trier les résultats des élèves selon l'ordre croissant des moyennes.

1. Étude d'un exemple
   Voici les notes de quatre élèves, chaque élève ayant reçu trois notes :

   Notes = [ (8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12) ]
   

   L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...
   Anticipez le résultat de l'exécution des instructions suivantes :

   >>> Notes[0]
   
   >>> Notes[3]
   

   Une réponse

   >>> Notes[0]
   (8, 12, 9)
   >>> Notes[3]
   (10, 11, 12)
   

2. Copiez/collez et complétez la définition de la fonction moyenne() qui prend en paramètre un tuple de nombres et qui renvoie la moyenne des valeurs de ce tuple.

   def moyenne(uplet):
       """
       uplet – tuple, t-uplet de nombres (int ou float)
       Sortie: float – moyenne des nombres de uplet
       >>> moyenne( (8, 12, 9) )
       9.666666666666666
       >>> moyenne( (10, 11, 12) )
       11.0
       """
   

   Une solution

   def moyenne(uplet):
       """
       uplet – tuple, t-uplet de nombres (int ou float)
       Sortie: float – moyenne des nombres de uplet
       >>> moyenne( (8, 12, 9) )
       9.666666666666666
       >>> moyenne( (10, 11, 12) )
       11.0
       """
       somme = 0
       n = len(uplet)
       for elt in uplet:
           somme += elt
       return somme/n
   

3. Copiez, collez et modifiez les instructions de la fonction inserer_tuple() de sorte que la fonction tri_insertion_tuple() tri un tableau de t-uplets par ordre croissant des moyennes de ces t-uplets.

   def inserer_tuple(tab, i):
       """
       tab – list, tableau de tuples de nombres tel que tab[0..i-1] est trié
                   par ordre croissant des moyennes de ces tuples
       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 des moyennes de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12) ]
       >>> inserer_tuple(Notes, 1)
       >>> Notes
       [(8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12)]
       >>> inserer_tuple(Notes, 2)
       >>> Notes
       [(8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12)]
       """
       assert 0 <= i < len(tab), "paramètre i out of range"
       temp = tab[i]
       while (i>0) and (tab[i-1]>temp):
           tab[i] = tab[i-1]
           i = i-1
       tab[i] = temp
   
   
   def tri_insertion_tuple(tab):
       """
       tab – list, tableau de tuples de nombres
       Sortie: None – Les éléments de tab sont triés par ordre croissant
               des moyennes des tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12) ]
       >>> tri_insertion_tuple(Notes)
       >>> Notes
       [(8, 12, 9), (10, 11, 12), (2, 18, 15), (14, 13, 17)]
       """
       for i in range(1, len(tab)):
           inserer_tuple(tab, i)
   

   Une solution

   Au lieu de comparer les valeurs des t-uplets pour décider du décalage à droite, on compare leur moyenne :

   def inserer_tuple(tab, i):
       """
       tab – list, tableau de tuples de nombres tel que tab[0..i-1] est trié
                   par ordre croissant des moyennes de ces tuples
       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 des moyennes de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12) ]
       >>> inserer_tuple(Notes, 1)
       >>> Notes
       [(8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12)]
       >>> inserer_tuple(Notes, 2)
       >>> Notes
       [(8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12)]
       """
       assert 0 <= i < len(tab), "paramètre i out of range"
       temp = tab[i]
       moy_temp = moyenne(temp)
       while (i>0) and (moyenne(tab[i-1])>moy_temp):
           tab[i] = tab[i-1]
           i = i-1
       tab[i] = temp
   

ProgG03.63 - Tri par colonne

Les notes d'un élève sont regroupées dans un t-uplet.
Les notes de la classe sont regroupées dans un tableau de notes d'élèves.
On souhaite trier les résultats des élèves selon l'ordre croissant des moyennes.

1. Étude d'un exemple
   Voici les notes de quatre élèves, chaque élève ayant reçu trois notes :

   Notes = [ (8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12) ]
   

   L'élève 0 a pour notes 8, 12 et 9, l'élève 1 a pour notes 2, 18 et 15, etc...
   Anticipez le résultat de l'exécution des instructions suivantes :

   >>> Notes[0][1]
   
   >>> Notes[2][2]
   
   >>> Notes[3][0]
   

   Une réponse

   Le premier indice correspond au numéro du t-uplet dans le tableau Notes.
   Le second indice indique le numéro de la note dans le t-uplet.

   >>> Notes[0][1]         # note d'indice 1 du premier t-uplet
   12
   
   >>> Notes[2][2]         # note d'indice 2 du troisième t-uplet
   17
   
   >>> Notes[3][0]         # note d'indice 0 du dernier t-uplet
   10
   

2. Copiez, collez et complétez les instructions des fonctions inserer_par_colonne() et tri_insertion_par_colonne() pour que cette dernière fonction tri un tableau de t-uplets par ordre croissant du « numéro de colonne » passé en paramètre.

   Exemple

   >>> notes = [(8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12)]
   >>> tri_insertion_par_colonne(notes, 0)         # tri suivant la première note
   >>> notes 
   [(2, 18, 15), (8, 12, 9), (10, 11, 12), (14, 13, 17)]
   
   >>> tri_insertion_par_colonne(notes, 1)         # tri suivant la seconde note
   >>> notes
   [(10, 11, 12), (8, 12, 9), (14, 13, 17), (2, 18, 15)]
   

   def inserer_par_colonne(tab, colonne, i):
       """
       tab – list, tableau de tuples de nombres tel que tab[0..i-1] est trié
                   par ordre croissant des valeurs d'indice colonne de ces tuples
       colonne – int, entier compris entre 0 et len(tab[0])-1
       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 des valeurs d'indice colonne de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12) ]
       >>> inserer_par_colonne(Notes, 0, 2)
       >>> Notes
       [(2, 18, 15), (8, 12, 9), (14, 13, 17), (10, 11, 12)]
       >>> inserer_par_colonne(Notes, 1, 1)
       >>> Notes
       [(8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12)]
       """
       pass
   
   
   def tri_insertion_par_colonne(tab, colonne):
       """
       tab – list, tableau de tuples de nombres
       colonne – int, entier compris entre 0 et len(tab[0])-1
       Sortie: None – Les éléments de tab sont triés par ordre croissant
               des valeurs d'indice colonne de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12) ]
       >>> tri_insertion_par_colonne(Notes, 2)
       >>> Notes
       [(8, 12, 9), (10, 11, 12), (2, 18, 15), (14, 13, 17)]
       """
       pass
   

   Une solution

   def inserer_par_colonne(tab, colonne, i):
       """
       tab – list, tableau de tuples de nombres tel que tab[0..i-1] est trié
                   par ordre croissant des valeurs d'indice colonne de ces tuples
       colonne – int, entier compris entre 0 et len(tab[0])-1
       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 des valeurs d'indice colonne de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (14, 13, 17), (2, 18, 15), (10, 11, 12) ]
       >>> inserer_par_colonne(Notes, 0, 2)
       >>> Notes
       [(2, 18, 15), (8, 12, 9), (14, 13, 17), (10, 11, 12)]
       >>> inserer_par_colonne(Notes, 1, 1)
       >>> Notes
       [(8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12)]
       """
       assert 0 <= i < len(tab), "paramètre i out of range"
       temp = tab[i]
       critere = temp[colonne]
       while (i>0) and (tab[i-1][colonne]>critere):
           tab[i] = tab[i-1]
           i = i-1
       tab[i] = temp
   
   
   def tri_insertion_par_colonne(tab, colonne):
       """
       tab – list, tableau de tuples de nombres
       colonne – int, entier compris entre 0 et len(tab[0])-1
       Sortie: None – Les éléments de tab sont triés par ordre croissant
               des valeurs d'indice colonne de ces tuples (effet de bord)
       >>> Notes = [ (8, 12, 9), (2, 18, 15), (14, 13, 17), (10, 11, 12) ]
       >>> tri_insertion_par_colonne(Notes, 2)
       >>> Notes
       [(8, 12, 9), (10, 11, 12), (2, 18, 15), (14, 13, 17)]
       """
       for i in range(1, len(tab)):
           inserer_par_colonne(tab, colonne, i)
   

Exercice G03.64

On veut trier, comme un joueur de cartes, le tableau :

paquet =

4

2

7

1

8

5

3

Pour cela, on initialise un tableau vide, nommé main.
Ensuite, on prend, au fur et à mesure, une carte dans le paquet que l'on insère ensuite dans le tableau main.

• Au départ le tableau main est vide :

paquet =

4

2

7

1

8

5

3

main =

• On enlève la première carte du paquet.
  On place cette carte dans la main :

paquet =

2

7

1

8

5

3

main =

4

• On enlève la (nouvelle) première carte du paquet.
  Puis on insère cette carte à sa place dans la main :

paquet =

7

1

8

5

3

main =

2

4

• On recommence :

paquet =

1

8

5

3

main =

2

4

7

• Puis :

paquet =

8

5

3

main =

1

2

4

7

• Puis :

paquet =

5

3

main =

1

2

4

7

8

• Puis :

paquet =

3

main =

1

2

4

5

7

8

• On s'arrête lorsque le paquet est vide, la main est triée :

paquet =

main =

1

2

3

4

5

7

8

A vous !

Illustrez de même, sur votre cahier, ce tri avec le paquet de cartes suivant :

paquet =

8

1

7

2

4

3

1

6

Une solution

• paquet =

8

1

7

2

4

3

1

6

main =

• paquet =

1

7

2

4

3

1

6

main =

8

• paquet =

7

2

4

3

1

6

main =

1

8

• paquet =

2

4

3

1

6

main =

1

7

8

• paquet =

4

3

1

6

main =

1

2

7

8

• paquet =

3

1

6

main =

1

2

4

7

8

• paquet =

1

6

main =

1

2

3

4

7

8

• paquet =

6

main =

1

1

2

3

4

7

8

• paquet =

main =

1

1

2

3

4

6

7

8

ProgG03.65 - Tri par insertion dans un nouveau tableau

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

T ← [tab[0]]

Pour i variant de 1 à n-1 :
    T ← T dans lequel tab[i] a été inséré

Renvoyer T   

Il reste à définir ce que signifie cette instruction a été inséré par un nouvel algorithme :

T est un tableau trié (par ordre croissant) ayant i éléments.
A partir de ce tableau, on construit un nouveau tableau ayant les i éléments de T ainsi qu'un élément elt supplémentaire de sorte que ce nouveau tableau soit lui aussi trié.

indice ← 0
result ← []
Tant que (indice ≤ i) et ( T[indice] < elt ):
    Placer T[indice] dans result
Fin Tant que

Placer elt dans result
Placer le reste des éléments de T dans result

Renvoyer result

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

   def inserer_element(tab, valeur):
       """
       tab – list, tableau d'éléments comparables triés par ordre croissant
       valeur – de même type que les éléments de tab
       Sortie: list – tableau contenant la valeur ainsi que les éléments de tab.
               Les éléments de ce tableau sont triés par ordre croissant
       >>> inserer_element([2, 3, 5, 6, 8], 3)
       [2, 3, 3, 5, 6, 8]
       >>> inserer_element([2, 3, 5, 6, 8], 1)
       [1, 2, 3, 5, 6, 8]
       >>> inserer_element([2, 3, 5, 6, 8], 9)
       [2, 3, 5, 6, 8, 9]
       """
   

   Une solution

   def inserer_element(tab, valeur):
       """
       tab – list, tableau d'éléments comparables triés par ordre croissant
       valeur – de même type que les éléments de tab
       Sortie: list – tableau contenant la valeur ainsi que les éléments de tab.
               Les éléments de ce tableau sont triés par ordre croissant
       >>> inserer_element([2, 3, 5, 6, 8], 3)
       [2, 3, 3, 5, 6, 8]
       >>> inserer_element([2, 3, 5, 6, 8], 1)
       [1, 2, 3, 5, 6, 8]
       >>> inserer_element([2, 3, 5, 6, 8], 9)
       [2, 3, 5, 6, 8, 9]
       """
       result = []
       indice = 0
       while indice < len(tab) and tab[indice] < valeur:
           result.append(tab[indice])
           indice = indice+1
       result.append(valeur)
   
       while indice < len(tab):
           result.append(tab[indice])
           indice = indice+1
       return result
   

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

   def tri_insertion_nouveau(tab):
       """
       tab – list, tableau d'éléments comparables
       Sortie: list – tableau contenant les mêmes éléments que tab,
               mais triés par ordre croissant
       >>> tri_insertion_nouveau([5, 7, 2, 8, 1, 2, 5, 4])
       [1, 2, 2, 4, 5, 5, 7, 8]
       """
   

   Une solution

   def tri_insertion_nouveau(tab):
       """
       tab – list, tableau d'éléments comparables
       Sortie: list – tableau contenant les mêmes éléments que tab,
               mais triés par ordre croissant
       >>> tri_insertion_nouveau([5, 7, 2, 8, 1, 2, 5, 4])
       [1, 2, 2, 4, 5, 5, 7, 8]
       """
       T = [tab[0]]
       for i in range(1, len(tab)):
           T = inserer_element(T, tab[i])
       return T