duranton.net

Introduction :

Le tri par sélection est un algorithme de tri simple qui fonctionne en trouvant l'élément le plus petit (ou le plus grand, selon le tri) dans une liste non triée, puis en le plaçant au début.

Ce processus est répété pour le reste de la liste jusqu'à ce que tous les éléments soient triés. Bien qu'il soit facile à comprendre, cet algorithme n'est pas très efficace pour les grandes listes en raison de sa complexité en temps quadratique.

1. Trier

Trier des éléments dans un ordre croissant ou décroissant se produit souvent en informatique.

Par exemple :

On peut trier des scores
On peut trier une liste de personnes par ordre alphabétique.
On peut trier une liste de ville en fonction de sa population.

2. Exercice

Soit la liste de nombres suivants : 3;5;8;2;5;9;23;5;1;8;5;4;0;6;4;5;34;1;4

Trier par ordre croissant les nombres de cette liste.
Expliquer votre méthode.

3. Tri par sélection .

A copier dans le cahier.

Le tri par sélection est un algorithme de tri simple qui fonctionne en sélectionnant à chaque étape l'élément le plus petit (ou le plus grand) parmi les éléments non triés et en l'ajoutant à la partie triée de la liste.

L'algorithme de tri par sélection fonctionne comme suit :

Trouver l'élément le plus petit dans la liste non triée.
Échanger cet élément avec le premier élément de la liste non triée.
Répéter les étapes 1 et 2 pour le reste de la liste non triée.

4. Exercice :

A faire dans le cahier.

A la main :

Trier la liste [42, 17, 9, 87, 23, 56, 34, 71, 5, 91] en mettant une ligne par étape avec un algorithme de tri par sélection.

5. Exercice :

Compléter la fonction ci-dessous :

def tri_selection(tab):
    N = len(tab)
    for k in range(...):
        imin = ...
        for i in range(... , N):
            if tab[i] < ... :
                imin = i
        ... , tab[imin] = tab[imin] , ...

On pourra tester notre fonction sur la liste de l'exercice précédent.

6. Complexité du tri par sélection.

A copier dans le cahier.

La complexité du tri par sélection est \(\mathcal{O}\left(n^2\right)\).

Cela signifie que, globalement, si une liste est 2 fois plus longue, il sera 4 fois plus long de la trier. Si la taille d'une liste est multipliée par 10, il sera 100 fois plus long de la trier etc.

7. Exercice