6 - tri par sélection

⏪

⏬

⏩

1 - Cartes

2 - Principe

3 - Algorithme

4 - Python

5 - FAQ

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

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

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.

On cherche ensuite quelle carte placer sur l'indice 1 en cherchant parmi les 3 cartes non triées 8, 9 et 4.

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.

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 ?

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

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

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

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

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 ?

...CORRECTION...

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.

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 ?

...CORRECTION...

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 ?

...CORRECTION...

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 ?

...CORRECTION...

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.

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 ?

...CORRECTION...

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 ?

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

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

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

...CORRECTION...

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.

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.

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

⇩ ⇧ ⤊

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

⏪

⏫

⏩