T7.1 Tri par sélection

7.1.1 Pourquoi étudier des algorithmes de tri ?

Autant ne pas le cacher, ces algorithmes sont déjà implémentés (quelque soit le langage) dans des fonctions très performantes.

En Python, on utilise la fonction sort():

>>> tab = [4, 8, 1, 2, 6]
>>> tab.sort()
>>> tab
[1, 2, 4, 6, 8]

Le meilleur de nos futurs algorithmes de tri sera moins efficace que celui de cette fonction sort()...
Malgré cela, il est essentiel de se confronter à l'élaboration manuelle d'un algorithme de tri:

• besoin pratique de trier;
• tri comme sous-programmes;
• utilisation de toutes les techniques informatiques.

Le tri par sélection est le premier des deux algorithmes de tri que nous allons étudier (nous étudierons aussi le tri par insertion).
Ces deux algorithmes ont pour particularité de :

• ne pas nécessiter la création d'une nouvelle liste. Ils modifient la liste à trier sur place.
• ne pas faire intervenir de fonctions complexes.

7.1.2 Principe du tri

On cherche à trier un tableau de \(n\) valeurs différentes, en général les entiers de \(0\) à \(n-1\).

• En partant de l'indice 0, on cherche l'indice du plus petit élément en parcourant le tableau;
• on l'échange avec l'élément d'indice 0;
• On recommence en partant de l'indice 1, puis 2, etc. jusqu'à ce que le tableau soit trié.

Exercice 1

ÉnoncéCorrection

On veut écrire une fonction tri_selection qui prend en paramètre une liste et qui trie cette liste par l'algorithme du tri par sélection.

1. Écrire un jeu de tests pour cette fonction.
2. Compléter puis tester la fonction ci-dessous.

def tri_selection(tab: list) -> None:
    n = len(tab)
    for i in range(...):
        indice_min = 
        for j in range( , ):
            if tab[j] < tab[indice_min]:
                ...
        #il reste à échanger les valeurs d'indice i et indice_min
        ...
        ...
        ...       

Exercice 2

ÉnoncéCorrection

On va s'intéresser au temps d'éxécution de ce tri, et plus particulièrement au lien entre la taille de la liste donnée en entrée et ce temps d'éxécution.

On définit donc :

• une fonction alea qui renvoie une liste de taille n créée aléatoirement;
• une fonction chrono qui prend en paramètre un entier n et qui renvoie le temps d'éxécution de la fonction tri_selection pour la liste construite à partir de la fonction alea.

1. Compléter les fonctions dont les extraits sont fournis ci-dessous.
2. Construire une liste (en compréhension si possible) des temps obtenus pour les valeurs de n suivantes : 10, 100, 1000, 10000.
3. Quel semble être le lien entre n et le temps d'éxécution?

import time
import random as rd

def alea(n):
    lst_alea = list(range(n))
    rd.shuffle(lst_alea)
    return lst_alea

def chrono(n):
    t0 = time.time()
    tri_selection(...)
    t1 = time.time()
    return 

tailles = [10, 100, 1000, 10000]
temps = [...]

1. On va visualiser tout ça...

import matplotlib.pyplot as plt

plt.plot(tailles, temps)
plt.show()