Algo Selection

Identification

Infoforall

6 - tri par sélection


Nous avons vu qu'on a tendance à vouloir travailler sur des données triées.

Nous avons utilisé la méthode sort() ou la fonction native sorted() de Python.

Cette fonction trie le tableau. Ok.

Mais comment ça fonctionne ?

Nous allons voir aujourd'hui une méthode de tri, le tri par insertion.

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,

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

Evaluation ✎ : questions 16-17-18

Résumé de cours : open document ou pdf

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

Le principe du tri par sélection est d'avoir deux sous-tableaux :

  • un sous-tableau des éléments déja triés et
  • un sous-tableau des éléments pas encore triés.

A chaque étape, on rajoute un élément dans le sous-tableau trié et on le supprime du sous-tableau non trié.

On a au départ

  • un sous-tableau trié vide (on le placera à gauche) et
  • un sous-tableau non trié contenant 4 cartes .
2 de Coeur 8 de Coeur 9 de Coeur 4 de Coeur
Images dans le domaine public issues de https://publicdomainvectors.org
  • On cherche d'abord quelle carte placer sur l'indice 0.
  • 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.
  • On la sélectionne et on intervertit cette carte avec... elle-même (on laissera ainsi le 2 en place puisqu'il est déjà bien placé).
  • 2 de Coeur vide vide vide
    vide 8 de Coeur 9 de Coeur 4 de Coeur
  • On a maintenant deux sous-tableaux :
    • un sous-tableau trié de 1 élément (en orange) et
    • un sous-tableau non trie contenant les 3 autres cartes.
    2 de Coeur 8 de Coeur 9 de Coeur 4 de Coeur
  • On cherche ensuite quelle carte placer sur l'indice 1 en cherchant parmi les 3 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 sur l'indice 1 (on intervertit donc le 8 et le 4).
  • Regardons nos deux sous-tableaux :
    • un sous-tableau trié de 2 éléments (en orange) et
    • un sous-tableau non trié contenant les 2 autres cartes non encore traitées.
    2 de Coeur 4 de Coeur 9 de Coeur 8 de Coeur
  • On cherche ensuite quelle carte placer sur l'indice 2 en cherchant parmi les 2 cartes non triées 8, 9 et aini de suite...

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 délimitant le début et la fin du sosu-tableau non trié.
  • 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

On a un sous-tableau de 0 élément trié d'indice dans [] et un sous-tableau de 5 éléments non triés d'indices dans [0, 4].

On cherche à trouver l'indice contenant élément minimum dans [0, 4] et à intervertir cet élément et celui actuellement en 0.

Au début, on considère donc que la valeur situéee en 0 est le minimum et on va lire les autres valeurs une par une pour voir si il y a mieux.

Indice 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.

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

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

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

On obtient alors un sous-tableau de 1 élément trié d'indice dans [0] et un sous-tableau de 4 éléments non triés d'indices dans [1, 4].

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

Etape 2 : on cherche à trouver le minimum suivant dans le sous-tableau [1, 4] pour l'intervertir avec celui placé sur l'indice 1.

Indice 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.

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

On intervertit donc les contenus des indices 1 et 3.

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

On obtient alors un sous-tableau de 2 éléments triés d'indices dans [0, 1] et un sous-tableau de 3 éléments non triés d'indices dans [2, 4].

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

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

On obtient cherche l'indice de l'élément minimum dans [2, 4] et on l'intervertit avec celui d'indice 2.

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

On obtient alors un sous-tableau de 3 éléments triés d'indices dans [0, 2] et un sous-tableau de 2 éléments non triés d'indices dans [3, 4].

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

On obtient cherche l'indice de l'élément minimum dans [3, 4] et on l'intervertit avec celui d'indice 3.

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

On obtient alors un sous-tableau de 4 éléments triés [0, 3] et un sous-tableau de 1 élément non trié [4].

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

Inutile de vraiment la faire puisque le sous-tableau ne contient plus qu'un seul élément.

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

Indice 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

Indice 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 décrire cela sans ancune ambiguïté vis à vis des actions à réaliser : avec un 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 :

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

Après le tri, le tableau contiendra cela :

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

En Français

  • Pour chaque indice debut possible dans le tableau
    • On cherche l'indice indice_min contenant le plus petit élément dans le sous-tableau [debut ; longueur - 1].
    • On intervertit les contenus des cases des indices debut et indice_min.

Algorithme

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

    POUR debut variant de 0 à (longueur - 1)

      indice_minminimum(tableau, debut)

      on cherche l'indice de la plus petite valeur présente dans la partie non triée [debut ; longueur - 1]

      intervertir(tableau, debut, indice_min)

      on intervertit les valeurs situées aux indices debut et indice_min

    Fin POUR

    Renvoyer VIDE (∅)

02° Pourquoi pourrait-on dire que cet algorithme décrit une procédure plutôt qu'une fonction ?

...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 statiques (c'est à dire le type list de Python sans utiliser append() et pop()) sont-ils des structures de données muables ou immuables ?

Citer deux structures de données muables en Python et deux structures non muables 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 à range() ?

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'indice du plus petit élément du tableau t transmis en cherchant à partir de l'indice 0. Tester votre fonction dans la console à l'aide de deux-trois appels de tests.

1 2 3 4 5 6 7 8 9 10 11 12
def minimum(t): """Renvoie l'indice de la valeur minimale trouvée dans le tableau t :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: return (int) :: renvoie l'indice 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(t): """Renvoie l'indice de la valeur minimale trouvée dans le tableau t :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: return (int) :: renvoie l'indice de la valeur minimale :: exemple :: >>> minimum([10, 20, -50, 100, 20, 12]) 2 """ indice_minimum = 0 # Au début, on prend le premier élément, l'indice 0 for i in range(1, len(t)): if t[i] < t[indice_minimum]: indice_minimum = i return indice_minimum

06° Compléter cette nouvelle fonction minimum() pour qu'elle renvoie bien l'indice du plus petit élément du tableau t transmis mais en cherchant à partir d'un indice égal au paramètre debut.

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

Tester votre fonction dans la console à l'aide de deux-trois appels de tests.

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

07° Ecrire uniquement 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 indices transmis en argument. Il faudra transmettre le tableau à modifier également. La fonction doit donc possèder 3 paramètres.

Utiliser la version longue pour la documentation.

...CORRECTION...

1 2 3 4 5 6 7 8 9 10 11
def intervertir(t, i, j): """Procédure qui intervertit les valeurs stockées aux indices i et j :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param i(int) :: un indice valide pour le tableau :: param j(int) :: un autre indice :: 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(t:list, i:int, j:int) -> None: """Procédure qui intervertit les valeurs stockées aux indices i et j .. 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(t, i, j): """Procédure qui intervertit les valeurs stockées aux indices i et j :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param i(int) :: un indice valide pour le tableau :: param j(int) :: un autre indice valide :: 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(t, i, j): """Procédure qui intervertit les valeurs stockées aux indices i et j :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param i(int) :: un indice valide pour le tableau :: param j(int) :: un autre indice valide :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord """ temp = t[i] t[i] = t[j] t[j] = temp

10° Pourquoi ne trouve-t-on pas de return None dans la correction alors que la réponse doit être 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 _ in range(20)] serie2 = [] for _ 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 successive
  • Compression
  • Compréhension
  • Rédaction

...CORRECTION...

serie1 est créé par COMPREHENSION.

serie2 est créé par EXTENSION SUCCESSIVE.

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'indice (flèche en vert clair dans l'animation) de la case à remplir

    POUR debut variant de 0 à (longueur - 1)

      indice_minminimum(tableau, debut)

      on cherche l'indice de la plus petite valeur présente dans la partie non triée [debut; fin]

      intervertir(tableau, debut, indice_min)

      on intervertit les valeurs situées aux indices debut et indice_min

    Fin POUR

    Renvoyer VIDE (∅)

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

Votre fonction pourra bien entendu utiliser à l'interne les deux fonctions que nous avions déjà réalisé : intervertir() et minimum().

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(t, i, j): """Procédure qui intervertit les valeurs stockées aux indices i et j :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param i(int) :: un indice valide pour le tableau :: param j(int) :: un autre indice valide :: return(None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord """ temp = t[i] t[i] = t[j] t[j] = temp def minimum(t, debut): """Renvoie l'indice de la valeur minimale trouvé dans le sous-tableau commençant à l'indice début :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param debut(int) :: un indice valide pour le tableau :: return(int) :: renvoie l'indice de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 """ indice_minimum = debut # Au début, on prend le premier élément, l'indice debut, pas 0 ! for i in range(debut+1, len(t)): if t[i] < t[indice_minimum]: indice_minimum = i return indice_minimum def tri_selection(t): """Trie le tableau t en place en utilisant le tri par sélection :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: return (None) :: "procédure" """ for debut in range(len(t)): indice_min = minimum(t, debut) intervertir(t, debut, indice_min)

14° Utiliser cette nouvelle 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(t, i, j): """Procédure qui intervertit les valeurs stockées aux indices i et j :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param i(int) :: un indice valide pour le tableau :: param j(int) :: un autre indice valide :: return (None) :: "procédure" .. Effet de bord :: le tableau est modifié par effet de bord """ temp = t[i] t[i] = tableau[j] t[j] = temp def minimum(t, debut): """Renvoie l'indice de la valeur minimale trouvé dans le sous-tableau commençant à l'indice début :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: param debut(int) :: un indice valide pour le tableau :: return (int) :: renvoie l'indice de la valeur minimale :: exemple :: >>> minimum([10,20,-50,100,20,12], 3) 5 """ indice_minimum = debut # Au début, on prend le premier élément, l'indice debut, pas 0 ! for i in range(debut+1, len(t)): if t[i] < t[indice_minimum]: indice_minimum = i return indice_minimum def tri_selection(t): """Trie le tableau sur place en utilisant le tri par sélection :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: return (None) :: "procédure" """ for debut in range(len(t)): print(f"Selection de l'élément d'indice {debut}") indice_min = minimum(t, debut) intervertir(t, debut, indice_min) print(indice_min) print(t) 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, mais ce n'est pas une bonne pratique : une fonction - une tâche est préférable.

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(t): """Trie le tableau t en place en utilisant le tri par sélection :: param t(list) :: un tableau NON VIDE ne contenant que des entiers :: return (None) :: "procédure" """ for debut in range(len(tableau)): # Recherche de l'indice du minimum dans le sous-tableau indice_minimum = debut # Au début, on prend le premier élément, l'indice debut, pas 0 ! for i in range(debut+1, len(t)): if t[i] < t[indice_minimum]: indice_minimum = i # Interversion des deux valeurs d'index temp = t[debut] t[debut] = t[indice_minimum] t[indice_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° Préparation pour le DS : fournir l'algorithme du tri par sélection.

Pensez à fournir le principe, les entrées, la sortie puis l'algorithme en lui-même.

✎ 18° Préparation pour le DS : fournir la fonction permettant d'implémenter cet algorithme. Utiliser des fonctions permettant de décomposer les tâches est un plus certain pour votre notation.

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 : 02 04 2023
Auteur : ows. h.