Exercices

Chapitre 3: Algorithmes de tri

1 Tri par sélection

Rappeler sans code le principe du tri par sélection.
Effectuer à la main un tri par sélection des listes suivantes en précisant l’état de la liste à chaque tour de boucle externe:
- [28, 2, 34, 12, 16]
- [1, 3, 7, 9, 16]
- [51, 12, 6, 5, 3]
Combien de tours de boucles a-t-il fallu au total (boucle interne et externe) dans chaque cas?

2 Tri par insertion

Rappeler sans code le principe du tri par insertion.
Effectuer à la main un tri par insertion des listes suivantes en précisant l’état de la liste à chaque tour de boucle:
- [28, 2, 34, 12, 16]
- [1, 3, 7, 9, 16]
- [51, 12, 6, 5, 3]
Combien de tours de boucles a-t-il fallu au total(boucle interne et externe) dans les deuxième et troisième cas?

3 Épreuve pratique: sujet n°28 session 2021

On considère l’algorithme de tri de tableau suivant : à chaque étape, on parcourt depuis le début du tableau tous les éléments non rangés et on place en dernière position le plus grand élément.

Exemple avec le tableau : t = [41, 55, 21, 18, 12, 6, 25]

Étape 1 : on parcourt tous les éléments du tableau, on permute le plus grand élément avec le dernier.

Le tableau devient t = [41, 25, 21, 18, 12, 6, 55]

Étape 2 : on parcourt tous les éléments sauf le dernier, on permute le plus grand élément trouvé avec l’avant-dernier.

Le tableau devient : t = [6, 25, 21, 18, 12, 41, 55]

Et ainsi de suite. Le code de la fonction tri_iteratif qui implémente cet algorithme est donné ci- dessous.

def tri_iteratif(tab):
    for k in range(..., 0 ,-1):
        imax = ...
        for i in range(0, ...):
            if tab[i] > ... :
                imax = i
        if tab[imax] > ... :
            ..., tab[imax] = tab[imax], ...
    return tab

Compléter le code qui doit donner :

>>> tri_iteratif([41, 55, 21, 18, 12, 6, 25])
[6, 12, 18, 21, 25, 41, 55]

On rappelle que l’instruction a, b = b, a échange les contenus de a et b.

4 Réécriture de la fonction de tri par sélection

Écrire une fonction indice_min(tab, i) qui renvoie l’indice du minimum du tableau compris entre l’indice i et la fin du tableau tab.

Par exemple l’appel indice_min([3,15,45,12,7,9], 2) renvoie 4.

Utiliser cette fonction indice_min pour réécrire la fonction tri_par_selection(tab) qui trie le tableau tab selon l’algorithme de tri par sélection.

def tri_par_selection(tab):
   for i in range(len(tab)):
      # appel de la fonction indice_min
      ...
      # permutation des valeurs pour placer 
      # le ième plus petit élément à l'indice i
      ...

Vérifier que la modification de tab s’effectue en place et donc que le tableau tab initial est écrasé par l’application de la fonction.
```
tab = [12, 5, 3, 7]
tri_par_selection(tab)
assert tab == [3, 5, 7, 12]
```

Modifier le code pour renvoyer un nouveau tableau trié sans modifier le tableau initial tab.

tab = [12, 5, 3, 7]
trié = tri_par_selection(tab)
assert tab == [12, 5, 3, 7]
assert trié == [3, 5, 7, 12]

5 Épreuve pratique: sujet n°11 session 2023

La fonction tri_insertion suivante prend en argument une liste tab et trie cette liste en utilisant la méthode du tri par insertion. Compléter cette fonction pour qu’elle réponde à la spécification demandée.

On rappelle le principe du tri par insertion : on considère les éléments à trier un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite… A chaque étape, le premier élément de la sous-liste non triée est placé dans la sous-liste des éléments déjà triés de sorte que cette sous-liste demeure triée.

Le principe du tri par insertion est donc d’insérer à la n-ième itération, le n-ième élément à la bonne place.

def tri_insertion(tab):
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[...]
        # la variable j sert à déterminer où placer la valeur à ranger
        j = ...
        # tant qu'on a pas trouvé la place de l'élément à insérer
        # on décale les valeurs du tableau vers la droite
        while j > ... and valeur_insertion < tab[...]:
            tab[j] = tab[j-1]
            j = ...
        tab[j] = ...

Exemples :

>>> liste = [9, 5, 8, 4, 0, 2, 7, 1, 10, 3, 6]
>>> tri_insertion(liste)
>>> liste
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

6 Un autre algorithme de tri: le tri à bulles

Sujet 43 de l’épreuve pratique 2023.

La fonction tri_bulles prend en paramètre une liste T d’entiers non triés et renvoie la liste triée par ordre croissant.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant la liste de gauche à droite et en échangeant au passage les éléments voisins mal ordonnés (si la valeur de l’élément d’indice i a une valeur strictement supérieure à celle de l’indice i + 1, ils sont échangés). Le tri place ensuite en avant-dernière position le plus grand élément de la liste privée de son dernier élément en procédant encore à des échanges d’éléments voisins. Ce principe est répété jusqu’à placer le minimum en première position.

Exemple : pour trier la liste [7, 9, 4, 3] :

première étape : 7 et 9 ne sont pas échangés, puis 9 et 4 sont échangés, puis 9 et 3 sont échangés, la liste est alors [7, 4, 3, 9]
deuxième étape : 7 et 4 sont échangés, puis 7 et 3 sont échangés, la liste est alors [4, 3, 7, 9]
troisième étape : 4 et 3 sont échangés, la liste est alors [3, 4, 7, 9]

Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.

def tri_bulles(T):
    '''
    Renvoie le tableau T trié par ordre croissant
    '''
    n = len(T)
    for i in range(...,...,-1):
        for j in range(i):
            if T[j] > T[...]:
                ... = T[j]
                T[j] = T[...]
                T[j+1] = temp
    return T

Exemples :

>>> tri_bulles([])
[]
>>> tri_bulles([7])
[7]
>>> tri_bulles([9, 3, 7, 2, 3, 1, 6])
[1, 2, 3, 3, 6, 7, 9]
>>> tri_bulles([9, 7, 4, 3])
[3, 4, 7, 9]