11 - tri par sélection

⏪

⏬

⏩

1 - Cartes

2 - Principe

3 - Algorithme

4 - Python

5 - FAQ

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

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.

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

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

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

dans le pire des cas (liste triée à l'envers) : Θ(n²).

sa complexité est en n²
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

Résumé de cours : open document ou pdf

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 — Images dans le domaine public issues de https://publicdomainvectors.org

8 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).

On a maintenant deux listes : une liste triée de un élément et une liste non triée contenant les autres cartes.

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.

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.

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

...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_min ← minimum(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 ?

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

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

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

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 ?

...CORRECTION...

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.

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 ?

...CORRECTION...

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 ?

...CORRECTION...

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 ?

...CORRECTION...

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.

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 ?

...CORRECTION...

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 ?

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

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 ?

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

...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_min ← minimum(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 ?

...CORRECTION...

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.

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.

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

⇩ ⇧ ⤊

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

⏪

⏫

⏩