Algo Selection

Identification

Infoforall

10 - tri par sélection


Nous avons vu également comment programmer un tri avec le tri par insertion qui est le tri usuel qu'on réalise lorsqu'on joue aux cartes.

Imaginons qu'on veuille trier les cartes suivantes de la plus petite à la plus grande. 

Images dans le domaine public issues de https://publicdomainvectors.org
2 de Coeur 8 de Coeur 9 de Coeur 4 de Coeur

On vérifie qu'on n'a pas à bouger le 2, puis le 8, puis le 9 mais on voit que le 4 pose problème par rapport au 9.

vide vide vide 4 de Coeur
2 de Coeur 8 de Coeur 9 de Coeur vide

Du coup, on bouge le 9. Puis, on bouge le 8. Enfin, on voit qu'on a pas besoin de bouger le 2.

vide vide vide 4 de Coeur
2 de Coeur vide 8 de Coeur 9 de Coeur

Et voilà : il ne reste plus qu'à mettre le 4 entre le 2 et le 8.

2 de Coeur 4 de Coeur 8 de Coeur 9 de Coeur

Cette manière de trier n'est cependant pas très efficace :

  • dans le pire des cas (liste triée à l'envers) : Θ(n2).
    • sa complexité est en n2
    • on dira que le coût est quadratique.
  • dans le meilleur des cas (liste déjà triée) : Θ(n).
    • sa complexité est en n
    • on dira que son coût est linéaire

Python permet de trier les tableaux ou les dictionnaires plus efficacement avec la méthode sort ou la fonction native sorted. Voir la partie FAQ pour un rappel. Du coup, il n'utilise pas le tri par insertion... En effet, il existe de nombreuses façons de trier les choses.

Nous allons voir aujourd'hui une nouvelle façon de trier : le tri par sélection. Je spoile : nous verrons qu'il n'est pas efficace non plus. Le programme de Terminale permettra par contre de rencontrer des algorithmes bien plus efficace !

Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...

Prérequis : les activités suivantes

  • Algorithme : parcours séquentiel d'un tableau,
  • Algorithme : Tri par insertion,
  • Algorithme : Preuve du tri par insertion

Evaluation ✎ : questions 16-17-18

1 - Tri par sélection de cartes par un humain

Comme pour le tri par insertion, le principe du tri par sélection est de faire deux listes : une liste des éléments déja triés et une liste des éléments pas encore triés. On ne rajoutera qu'un élément à la fois dans la liste des éléments triés.

Prenons le cas de l'introduction : on a au départ une liste triée vide (en orange) et une liste non triée à priori contenant 4 cartes (sans couleur).

2 de Coeur 8 de Coeur 9 de Coeur 4 de Coeur
Images dans le domaine public issues de https://publicdomainvectors.org

Le principe est simple :

  • On lit les cartes une par une et on cherche la carte la plus petite parmi les cartes non encore triées. On lit 2, 8, 9 et 4. On trouve 2 ici en indice 0.
  • On la sélectionne et on l'inverse avec celle qui est en première postion (ici, on laisse en réalite le 2 en place du coup).
  • 2 de Coeur vide vide vide
    vide 8 de Coeur 9 de Coeur 4 de Coeur
  • On a maintenant deux listes : une liste triée de un élément et une liste non triée contenant les autres cartes.
  • 2 de Coeur 8 de Coeur 9 de Coeur 4 de Coeur
  • On regarde donc quelle est la carte la plus petite à placer en deuxième position parmi les cartes non triées 8, 9 et 4.
  • 2 de Coeur vide vide 4 de Coeur
    vide 8 de Coeur 9 de Coeur vide
  • On la sélectionne et on l'inverse avec la carte qui est en deuxième position (on intervertit donc le 8 et le 4).
  • On a maintenant deux listes : une liste triée de 2 éléments et une liste contenant les 2 autres cartes non encore traitées.
  • 2 de Coeur 4 de Coeur 9 de Coeur 8 de Coeur
  • ... on continue jusqu'à ce que le paquet rouge des cartes non encore triées soit vide ...

On voit donc qu'on va avoir besoin de deux fonctions :

  • Une fonction permetttant de trouver le plus petit élément dans un tableau entre deux indices
  • Une fonction permettant d'intervertir les éléments placés à deux indices connus.

2 - Principe du tri par sélection dans un tableau

Imaginons que vous ayez à trier ce tableau de nombres entiers [90, 60, 20, 50, 80].

Recherche du premier minimum

Nous allons commencer par lire un par un les valeurs de l'index 0 à l'index final pour trouver la plus petite valeur. Au début, on considère donc que 60 est le minimum et on va lire les autres valeurs une par une pour voir si il y a mieux.

Index 00 01 02 03 04
Elément 60 90 20 50 80
Min

On trouve 20 au final après avoir lue les cases de 0 à 4.

Index 00 01 02 03 04
Elément 60 90 20 50 80
Min

Il suffit alors d'intervertir les contenus des valeurs des index 0 et 2.

Index 00 01 02 03 04
Elément 20 90 60 50 80

On obtient alors un sous-tableau de 1 élément trié et un sous-tableau de 4 éléments non triés.

Index 00 01 02 03 04
Elément 20 90 60 50 80
Trié

Etape 2 : on cherche à trouver le minimum suivant pour le placer sur l'index 1. Au début, on considère donc que le minimum vaut 90 et on lit les valeurs des indices 2 et plus pour voir si on trouve plus petit.

Index 00 01 02 03 04
Elément 20 90 60 50 80
Trié Min

En cherchant un par un, on trouve que le plus petit est 50.

Index 00 01 02 03 04
Elément 20 90 60 50 80
Trié Min

On intervertit donc les contenus des index 1 et 3.

Index 00 01 02 03 04
Elément 20 50 60 90 80
Trié Min

On obtient donc un sous-tableau de 2 éléments triés et un sous-tableau de 3 éléments non triés.

Index 00 01 02 03 04
Elément 20 50 60 90 80
Trié Trié

Etape suivante : on rajoute l'élément suivant

On prend 60 comme minimum suivant et on ne trouve pas mieux plus loin. On garde donc le 60.

Index 00 01 02 03 04
Elément 20 50 60 90 80
Trié Trié Trié

Etape suivante : on rajoute l'élément suivant

On prend 90 comme minimum suivant et on trouve 80 plus loin : on intervertit donc les deux valeurs aux index 3 et 4.

Index 00 01 02 03 04
Elément 20 50 60 80 90
Trié Trié Trié Trié

Dernière étape : on rajoute le dernier élément

On prend 90 comme minimum suivant et comme il est le dernier élément, c'est forçément le plus petit de ceux qui restent !

Index 00 01 02 03 04
Elément 20 50 60 80 90
Trié Trié Trié Trié Trié

Voici une animation permettant de comprendre cela avec des différentes valeurs.

01° Utiliser l'animation avec des valeurs au hasard, des tableaux déjà triés ou triés dans le mauvais sens. Voyez-vous une différence de temps de traitement ?

Tri par sélection du plus petit au plus grand

Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
Elément 60 89 15 56 82 1 86 97 24 86 75 6 14 69 98 31 37 89 91 56

...CORRECTION...

Et non. Aucune différence de temps.

Que la liste soit aléatoire, bien triée ou mal triée, c'est long...

3 - Algorithme du tri par sélection

Dans la partie 1, vous avez vu le principe, réalisable par un humain.

Dans la partie 2, nous avons vu qu'il fallait parvenir à travailler sur les cases une par une si on veut parvenir à faire réaliser ce tri par un ordinateur.

Nous allons maintenant voir comment convertir chaque action décrite en Français en version algorithme.

Algorithme de tri par sélection

But : trier sur place un tableau initialement non trié.

(ici par odre croissant)

Description des entrées / sortie

  • ENTREES :
    • tableau : un tableau contenant au moins deux éléments.
    • (optionnelle selon les langages d'implémentation): longueur, le nombre d'éléments dans le tableau
  • SORTIE : aucune. Le tableau est trié sur place. On modifie directement tableau.

Exemple :

Prenons tableau = [13, 18, 89, 1024, 45, -12, 18]

Initialement le tableau contient donc cela :

Index 0 1 2 3 4 5 6
Elément 13 18 89 1024 45 -12 18

Après le tri, le tableau contiendra cela :

Index 0 1 2 3 4 5 6
Elément -12 13 18 18 45 89 1024

En Français

  • Pour chaque index debut du tableau
    • On cherche l'index index_min contenant le plus petit élément dans le sous-tableau [index debut ; index final].
    • On intervertit les contenus des index debut et index_min.

Algorithme

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

02° Pourquoi pourrait-on dire que cet algorithme décrit une procédure ?

...CORRECTION...

Cet algorithme ne renvoie rien (vide): il modifie juste le tableau en place.

C'est la définition même d'une procédure : on agit mais on ne revoit rien vers le programme qui a fait appel à ce bout de code.

En Python, cela revient à renvoyer None puisque les vrais procédures n'existent pas.

4 - Tri par insertion en Python

Nous allons maintenant transcrire cet algorithme en Python. Cela nous permettra de revoir quelques notions et connaissances fondamentales.

03° Les tableaux de Python (type list pour nous) sont-ils des structures de données mutables ?

Citer deux structures de données mutables en Python et deux structures non mutables en Python.

...CORRECTION...

Les tableaux (le type list) sont mutables en Python : on peut modifier leurs contenus et garder la même adresse mémoire pour le tableau.

Les types list et dict sont mutables.

>>> tableau = [1, 10, 100] >>> tableau[0] 1 >>> tableau[0] = 2 >>> tableau [2, 10, 100] >>> type(tableau) <class 'list'> >>> type(tableau) == list True
>>> dictionnaire = {'a':1, 'b':10, 'c':100} >>> dictionnaire['a'] 1 >>> dictionnaire['a'] = 2 >>> dictionnaire {'a': 2, 'b': 10, 'c': 100} >>> type(dictionnaire) <class 'dict'> >>> type(dictionnaire) == dict True

Les types str et tuple sont non mutables.

>>> p_uplet = (1, 10, 100) >>> p_uplet[0] 1 >>> p_uplet[0] = 2 TypeError: 'tuple' object does not support item assignment >>> p_uplet (1, 10, 100) >>> type(p_uplet) <class 'tuple'> >>> type(p_uplet) == tuple True
>>> texte = "Bonjour" >>> texte[0] 'B' >>> texte[0] = 'M' TypeError: 'str' object does not support item assignment >>> texte 'Bonjour' >>> type(texte) <class 'str'> >>> type(texte) == str True

04° Que va-afficher le court programme suivant ? A quoi correspondent les trois arguments envoyés ?

1 2
for x in range(5, 11, 2) : print(x)

...CORRECTION...

5 7 9

Pourquoi ?

Le premier argument (optionnel) correspond à la valeur de départ. Si on ne fournit qu'un seul argument, la valeur de départ est prise à 0 par défaut. Ainsi range(10) revient à avoir taper range(0, 10).

Le deuxième argument correspond à la borne extrême exclue de l'intervalle. Ainsi range(0, 10) veut dire de commencer à 0 et de finir à ... 9.

Le troisième argument envoyé correspond au pas entre chaque variation. Si on ne fournit pas, c'est qu'il vaut 1. Ainsi range(10) veut dire range(0, 10, 1).

Ici, on commence donc à 5, on augmente de 2 en 2 et la borne limite exlue est 11. Donc 5, 7, 9 et c'est tout.

En résumé, trois possibilités de fournir un ensemble avec range :

  • range(borne_extreme_exclue)
  • range(valeur_initiale, borne_extreme_exclue)
  • range(valeur_initiale, borne_extreme_exclue, pas)

05° Compléter la fonction minimum pour qu'elle renvoie bien l'index du plus petit élément du tableau transmis en cherchant à partir de l'index 0. Tester votre fonction dans le Shell à l'aide de deux-trois appels de tests.

1 2 3 4 5 6 7 8 9 10 11 12
def minimum(tableau) : '''Renvoie l'index de la valeur minimale trouvée dans le tableau :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10, 20, -50, 100, 20, 12]) 2 ''' return 0

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
def minimum(tableau) : '''Renvoie l'index de la valeur minimale trouvée dans le tableau :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10, 20, -50, 100, 20, 12]) 2 ''' index_minimum = 0 # Au début, on prend le premier élément, l'index 0 for index in range(1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index return index_minimum

06° Compléter la fonction minimum pour qu'elle renvoie bien l'index du plus petit élément du tableau transmis en cherchant à partir d'un index égal au paramètre debut.

Un appel minimum(toto, 10) veut donc dire de renvoyer l'index du minimum trouvé dans le tableau toto à partir de l'index 10.

Tester votre fonction dans le Shell à l'aide de deux-trois appels de tests.

1 2 3 4 5 6 7 8 9 10 11 12 13
def minimum(tableau, debut) : '''Renvoie l'index de la valeur minimale trouvé dans le sous-tableau commençant à l'index début :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param debut(int) :: un index valide pour le tableau :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 ''' return 0

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
def minimum(tableau, debut) : '''Renvoie l'index de la valeur minimale trouvé dans le sous-tableau commençant à l'index début :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param debut(int) :: un index valide pour le tableau :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10, 20,-50, 100, 20, 12], 3) 5 ''' index_minimum = debut # Au début, on prend le premier élément, l'index debut, pas 0 ! for index in range(debut+1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index return index_minimum

07° Ecrire le prototype (pas le corps du code) d'une fonction intervertir qui doit modifier sur place un tableau en intervertissant les valeurs contenues sur deux index qui transmet en argument. Il faudra transmettre le tableau également.

Placer les demandes de types des paramètres dans la documentation de la fonction.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' return None

08° Idem mais en utilisant la méthode du typing.

1 2
def greeting(name: str) -> str: return 'Hello ' + name

...CORRECTION...

1 2 3 4 5 6
def intervertir(tableau:list, a:int, b:int) -> None : '''Procédure qui intervertit les valeurs stockées aux index a et b .. Effet de bord :: le tableau est modifié par effet de bord ''' return None

On remarquera que cette notation est plus courte mais qu'elle ne vaut pas une documentation avec quelques mots.

09° Compléter la fonction pour qu'elle réalise la tâche demandée en modifiant le tableau par effet de bord.

1 2 3 4 5 6 7 8 9 10 11
def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' return None

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11 12 13
def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' temp = tableau[a] tableau[a] = tableau[b] tableau[b] = temp

10° Pourquoi ne trouve-t-on pas de return None dans la correction alors que la postcondition impose de renvoyer None ?

...CORRECTION...

Tout simplement car si on ne place aucun return, on ne renvoie ... rien. Donc, c'est comme si on avait placé return None.

11° Voici deux façons de créer un tableau de nombres aléatoires compris dans [0; 100].

1 2 3 4 5 6 7
import random as rd serie1 = [rd.randint(0, 100) for x in range(20)] serie2 = [] for x in range(20) : serie2.append(rd.randint(0,100))

Question : associer les tableaux serie1 puis serie2 au nom de leur méthode de création. Choisir parmi

  • Extension
  • Compression
  • Compréhension
  • Rédaction

...CORRECTION...

serie1 est créé par COMPREHENSION.

serie2 est créé par EXTENSION.

12° Rajouter ces variables dans votre programme et vérifier leurs contenus après l'avoir lancé.

...CORRECTION...

Vous devez obtenir quelque chose de ce type :

>>> serie1 [48, 98, 39, 92, 93, 18, 74, 8, 41, 55, 48, 3, 70, 12, 97, 62, 48, 30, 64, 63] >>> serie2 [36, 99, 70, 33, 28, 92, 59, 26, 37, 46, 18, 13, 100, 51, 65, 80, 3, 81, 5, 86]

Revenons maintenant à notre problème de tri par sélection.

Algorithme de tri par sélection

    debut est l'index (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      index_minminimum(tableau, debut)

      on cherche l'index de la plus petite valeur présente dans la partie non triée (index debut et plus)

      intervertir(tableau, debut, index_min)

      on intervertit les valeurs situées aux index debut et index_min

    Fin POUR

    Renvoyer VIDE (∅)

13° Finaliser cet algorithme en créant la fonction tri_selection qui ne possède qu'un paramètre : le tableau à trier.

Tester ensuite votre code avec un test de ce type :

>>> serie1 [93, 55, 35, 58, 61, 44, 66, 55, 51, 3, 46, 11, 87, 35, 73, 27, 76, 51, 97, 61] >>> tri_selection(serie1) >>> serie1 [3, 11, 27, 35, 35, 44, 46, 51, 51, 55, 55, 58, 61, 61, 66, 73, 76, 87, 93, 97]

...CORRECTION...

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 36 37 38 39 40 41 42 43 44 45 46
import random as rd serie1 = [rd.randint(0, 100) for x in range(20)] def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' temp = tableau[a] tableau[a] = tableau[b] tableau[b] = temp def minimum(tableau, debut) : '''Renvoie l'index de la valeur minimale trouvé dans le sous-tableau commençant à l'index début :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param debut(int) :: un index valide pour le tableau :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 ''' index_minimum = debut # Au début, on prend le premier élément, l'index debut, pas 0 ! for index in range(debut+1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index return index_minimum def tri_selection(tableau) : '''Trie le tableau sur place en utilisant le tri par sélection :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(None) :: "procédure" ''' for debut in range(len(tableau)) : index_min = minimum(tableau, debut) intervertir(tableau, debut, index_min)

14° Utiliser cette version qui permet d'afficher les différentes étapes. Il faut appuyer sur ENTREE pour obtenir l'étape suivante.

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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
import random as rd serie1 = [rd.randint(0, 100) for x in range(20)] def intervertir(tableau, a, b) : '''Procédure qui intervertit les valeurs stockées aux index a et b :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param a(int) :: un index valide pour le tableau :: param b(int) :: un index autre valide pour le tableau :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord ''' temp = tableau[a] tableau[a] = tableau[b] tableau[b] = temp def minimum(tableau, debut) : '''Renvoie l'index de la valeur minimale trouvé dans le sous-tableau commençant à l'index début :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: param debut(int) :: un index valide pour le tableau :: return(int) :: renvoie l'index de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 ''' index_minimum = debut # Au début, on prend le premier élément, l'index debut, pas 0 ! for index in range(debut+1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index return index_minimum def tri_selection(tableau) : '''Trie le tableau sur place en utilisant le tri par sélection :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(None) :: "procédure" ''' for debut in range(len(tableau)) : print(f"Selection de l'élément d'index {debut}") index_min = minimum(tableau, debut) intervertir(tableau, debut, index_min) print(index_min) print(tableau) input("")

Nous sommes passés ici par des fonctions car cela permet de rendre le code final plus concis. Mais on aurait bien entendu pu s'en passer.

15° Tester cette version sans fonction à l'intérieur de la fonction elle-même. Du coup, on perd en visibilité dans la fonction elle-même : il faut lire le code pour savoir ce qu'il fait.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
import random as rd serie1 = [rd.randint(0, 100) for x in range(20)] def tri_selection(tableau) : '''Trie le tableau sur place en utilisant le tri par sélection :: param tableau(list) :: un tableau non vide ne contenant que des entiers :: return(None) :: "procédure" ''' for debut in range(len(tableau)) : # Recherche de l'index du minimum dans le sous-tableau index_minimum = debut # Au début, on prend le premier élément, l'index debut, pas 0 ! for index in range(debut+1, len(tableau)) : if tableau[index] < tableau[index_minimum] : index_minimum = index # Interversion des deux valeurs d'index temp = tableau[debut] tableau[debut] = tableau[index_minimum] tableau[index_minimum] = temp

✎ 16° Créer une fonction qui permet d'utiliser le tri par sélection pour trier le tableau en sens décroissant : du plus grand nombre au plus petit nombre.

✎ 17° Rajouter les lignes de code pour parvenir à lancer automatiquement les tests que vous aurez placer dans la documention. Il faudra donc utiliser le module doctest.

✎ 18° Rajouter des assertions pour vérifier les préconditions sur les types de paramètres.

Si vous ne vous souvenez plus comment ça marche, il faut aller revoir la FAQ de la leçon Python : Documenter et tester.

5 - FAQ

Nous avons donc vu l'algorithme de tri par sélection en pratique.

L'activité suivante permettra de justifier son fonctionnement correct et permettra de trouver sa complexité dans le meilleur des cas et dans le pire des cas.

Activité publiée le 01 09 2020
Dernière modification : 19 09 2020
Auteur : ows. h.