Tri par sélection

Tri par sélection#

Qu'est-ce qu'un algorithme de tri ?#

Trier une liste, c'est réordonner ses éléments du plus petit au plus grand (ou l'inverse). C'est l'une des opérations les plus courantes en informatique : classement d'une compétition, résultats d'une recherche du plus pertinent au moins pertinent, contacts par ordre alphabétique... Et comme on l'a vu avec la recherche dichotomique, une liste triée permet souvent d'écrire des algorithmes beaucoup plus rapides par la suite.

Python sait évidemment trier une liste tout seul, mais il existe de nombreuses manières de le faire, plus ou moins rapides. Dans les pages qui suivent, nous allons étudier les plus célèbres, comprendre leur fonctionnement, les programmer, et comparer leur complexité.

Le principe du tri par sélection#

Imaginez que vous deviez ranger les élèves d'une classe par taille, du plus petit au plus grand. Une méthode naturelle consiste à chercher le plus petit élève et à le placer au début de la rangée, puis à chercher le plus petit parmi ceux qui restent et à le placer en deuxième position, et ainsi de suite. C'est exactement le principe du tri par sélection : à chaque étape, on sélectionne le minimum de la partie non triée, et on l'échange avec le premier élément de cette partie.

1Pour chaque position i, de la première à l'avant-dernière :
2    Chercher la position du minimum parmi les éléments de la position i jusqu'à la fin
3    Échanger ce minimum avec l'élément de la position i

Après le premier passage, le plus petit élément est à sa place définitive au début de la liste. Après le deuxième passage, les deux plus petits sont à leur place, etc. Le dernier élément n'a pas besoin d'être traité : quand tous les autres sont à leur place, il l'est forcément aussi.

Observez l'algorithme en action dans la visualisation ci-dessous, étape par étape ou en lecture automatique. Vous pouvez aussi tirer de nouvelles listes.

Exemple pas à pas#

Le tableau ci-dessous résume le tri de la liste [7, 3, 9, 1, 5]. La partie déjà triée est en gras.

Passage

Partie non triée

Minimum

Échange

Liste après le passage

i = 0

[7, 3, 9, 1, 5]

1

1 et 7

[1, 3, 9, 7, 5]

i = 1

[3, 9, 7, 5]

3

aucun, il est déjà à sa place

[1, 3, 9, 7, 5]

i = 2

[9, 7, 5]

5

5 et 9

[1, 3, 5, 7, 9]

i = 3

[7, 9]

7

aucun, il est déjà à sa place

[1, 3, 5, 7, 9]

Modifier et échanger des éléments d'une liste#

Pour programmer ce tri, il faut savoir modifier un élément d'une liste. Pour cela, on affecte une nouvelle valeur à l'élément, désigné par son index.

1scores = [10, 25, 7]
2scores[2] = 30               # remplace le 7 par 30
3scores[0] = scores[0] + 5    # ajoute 5 au premier score
4print(scores)

Pour échanger deux éléments, il ne suffit pas d'écrire liste[i] = liste[j] puis liste[j] = liste[i] : la première affectation écrase la valeur de liste[i], qui est alors perdue (souvenez-vous du faux échange de la page sur les variables). Il faut d'abord la sauvegarder dans une variable temporaire.

1lettres = ["A", "B", "C", "D"]
2temp = lettres[0]
3lettres[0] = lettres[3]
4lettres[3] = temp
5print(lettres)

Enfin, une fonction peut recevoir une liste en paramètre et la modifier directement. Dans ce cas, la modification reste visible après l'appel, même sans return.

1def bonus(notes):
2    notes[0] = notes[0] + 0.5
3
4mes_notes = [4.5, 5, 3.5]
5bonus(mes_notes)
6print(mes_notes)

Important

  • liste[i] = valeur remplace l'élément d'index i.

  • Pour échanger deux éléments, on passe par une variable temporaire.

  • Une fonction qui modifie une liste reçue en paramètre la modifie pour tout le programme.

Le code Python#

On peut maintenant traduire l'algorithme en Python. La fonction tri_selection ne retourne rien : elle trie directement la liste reçue en paramètre.

 1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        # Recherche du minimum de la partie non triée
 5        position_min = i
 6        for j in range(i + 1, n):
 7            if liste[j] < liste[position_min]:
 8                position_min = j
 9        # Échange du minimum avec le premier élément de la partie non triée
10        if position_min != i:
11            temp = liste[i]
12            liste[i] = liste[position_min]
13            liste[position_min] = temp
14
15nombres = [7, 3, 9, 1, 5, 8, 2, 6]
16tri_selection(nombres)
17print(nombres)

  1. La boucle extérieure parcourt les positions 0 à n - 2 : c'est la position i à remplir avec le minimum de la partie non triée.

  2. La boucle intérieure cherche la position du minimum (et non sa valeur), car c'est elle dont on a besoin pour faire l'échange. On part du principe que le minimum est en position i, puis on compare chaque élément suivant au minimum trouvé jusque-là.

  3. L'échange n'est fait que si le minimum n'est pas déjà à sa place.

À vous de jouer#

Triez la liste ci-dessous en suivant exactement le tri par sélection. Sélectionnez deux éléments en cliquant dessus, puis choisissez l'opération : chaque comparaison et chaque échange doivent être faits dans le bon ordre.

Complexité#

Pour une liste de \(n\) éléments, le premier passage compare le minimum provisoire aux \(n - 1\) éléments suivants, le deuxième passage fait \(n - 2\) comparaisons, et ainsi de suite jusqu'au dernier passage, qui n'en fait qu'une. On retrouve la somme de la page sur la complexité :

\[(n - 1) + (n - 2) + \ldots + 2 + 1 = \frac{n \cdot (n - 1)}{2}\]

Le tri par sélection est donc en \(O(n^2)\). Surtout, ce nombre de comparaisons ne dépend pas du contenu de la liste : même une liste déjà triée demande exactement le même travail, car l'algorithme doit tout parcourir pour être sûr d'avoir trouvé le minimum. Vérifiez-le dans la visualisation de la théorie en choisissant une liste "déjà triée", ou avec le programme ci-dessous.

 1from random import randint
 2
 3def tri_selection_compte(liste):
 4    nb_comparaisons = 0
 5    n = len(liste)
 6    for i in range(n - 1):
 7        position_min = i
 8        for j in range(i + 1, n):
 9            nb_comparaisons = nb_comparaisons + 1
10            if liste[j] < liste[position_min]:
11                position_min = j
12        if position_min != i:
13            temp = liste[i]
14            liste[i] = liste[position_min]
15            liste[position_min] = temp
16    return nb_comparaisons
17
18for n in [10, 100, 1000]:
19    aleatoire = []
20    triee = []
21    for k in range(n):
22        aleatoire.append(randint(1, 1000))
23        triee.append(k)
24    print(n, "éléments :", tri_selection_compte(aleatoire), "comparaisons (liste aléatoire),",
25          tri_selection_compte(triee), "comparaisons (liste déjà triée)")

En revanche, le tri par sélection fait très peu d'échanges : au plus un par passage, soit au plus \(n - 1\) échanges au total.

Important

Tri par sélection, pour une liste de \(n\) éléments :

  • comparaisons : toujours \(\frac{n \cdot (n - 1)}{2}\), quel que soit le contenu de la liste, donc \(O(n^2)\) ;

  • échanges : au plus \(n - 1\).

Exercices#

Exercice 9#

On trie la liste [6, 2, 8, 4, 1, 9, 3] avec le tri par sélection. Répondez sans exécuter de programme. Pour les listes, écrivez par exemple [4, 2, 7].

  1. Que vaut la liste après le premier passage ?

  2. Que vaut la liste après le deuxième passage ?

  3. Que vaut la liste après le troisième passage ?

  4. Combien de comparaisons le tri effectue-t-il au total ?

  5. Combien d'échanges le tri effectue-t-il au total ?

Solution

  1. Le minimum de toute la liste est 1 : il est échangé avec 6, le premier élément.

  2. Le minimum de [2, 8, 4, 6, 9, 3] est 2, qui est déjà en position 1 : pas d'échange, la liste ne change pas.

  3. Le minimum de [8, 4, 6, 9, 3] est 3 : il est échangé avec 8.

  4. Pour 7 éléments : \(6 + 5 + 4 + 3 + 2 + 1 = \frac{7 \cdot 6}{2} = 21\) comparaisons.

  5. Les passages suivants donnent [1, 2, 3, 4, 6, 9, 8] (pas d'échange, 4 est en place), puis encore aucun échange pour 6, et enfin l'échange de 9 et 8. Au total : 1 et 6, 3 et 8, puis 8 et 9, soit 3 échanges.

Exercice 10#

Triez cette liste plus longue avec le tri par sélection. Cette fois, seuls les échanges sont demandés : à vous de trouver mentalement le minimum à chaque passage.

Exercice 11#

Chacune des fonctions ci-dessous devrait trier la liste par sélection, mais comporte une erreur. Exécutez-les pour observer le problème, puis corrigez-les.

  1.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = 0
 5        for j in range(i + 1, n):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            temp = liste[i]
10            liste[i] = liste[position_min]
11            liste[position_min] = temp
12
13nombres = [7, 3, 9, 1, 5]
14tri_selection(nombres)
15print(nombres)

  2.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = i
 5        for j in range(i + 1, n - 1):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            temp = liste[i]
10            liste[i] = liste[position_min]
11            liste[position_min] = temp
12
13nombres = [5, 3, 8, 1]
14tri_selection(nombres)
15print(nombres)

  3.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = i
 5        for j in range(i + 1, n):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            liste[i] = liste[position_min]
10            liste[position_min] = liste[i]
11
12nombres = [7, 3, 9, 1, 5]
13tri_selection(nombres)
14print(nombres)

Solution

  1.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = i
 5        for j in range(i + 1, n):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            temp = liste[i]
10            liste[i] = liste[position_min]
11            liste[position_min] = temp
12
13nombres = [7, 3, 9, 1, 5]
14tri_selection(nombres)
15print(nombres)

    Le minimum provisoire doit être le premier élément de la partie non triée, c'est-à-dire liste[i]. Avec position_min = 0, dès le deuxième passage, le minimum provisoire est le plus petit élément de toute la liste (déjà placé en position 0), et l'algorithme le déplace à nouveau.

  2.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = i
 5        for j in range(i + 1, n):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            temp = liste[i]
10            liste[i] = liste[position_min]
11            liste[position_min] = temp
12
13nombres = [5, 3, 8, 1]
14tri_selection(nombres)
15print(nombres)

    La fin d'un range() est exclue : avec range(i + 1, n - 1), le dernier élément de la liste n'est jamais examiné. Si le minimum s'y trouve, il n'est pas trouvé.

  3.  1def tri_selection(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_min = i
 5        for j in range(i + 1, n):
 6            if liste[j] < liste[position_min]:
 7                position_min = j
 8        if position_min != i:
 9            temp = liste[i]
10            liste[i] = liste[position_min]
11            liste[position_min] = temp
12
13nombres = [7, 3, 9, 1, 5]
14tri_selection(nombres)
15print(nombres)

    C'est le faux échange : la première affectation écrase liste[i], et la seconde recopie donc la même valeur. Des éléments disparaissent et d'autres apparaissent deux fois.

Exercice 12#

  1. Modifiez la fonction tri_selection pour qu'elle trie la liste dans l'ordre décroissant.

  2. Testez ensuite la fonction d'origine (ordre croissant) sur une liste de prénoms. Fonctionne-t-elle ? Pourquoi ?

1def tri_selection_decroissant(liste):
2    #Complétez le corps de la fonction
3
4nombres = [7, 3, 9, 1, 5, 8, 2, 6]
5tri_selection_decroissant(nombres)
6print(nombres)

Solution

 1def tri_selection_decroissant(liste):
 2    n = len(liste)
 3    for i in range(n - 1):
 4        position_max = i
 5        for j in range(i + 1, n):
 6            if liste[j] > liste[position_max]:
 7                position_max = j
 8        if position_max != i:
 9            temp = liste[i]
10            liste[i] = liste[position_max]
11            liste[position_max] = temp
12
13nombres = [7, 3, 9, 1, 5, 8, 2, 6]
14tri_selection_decroissant(nombres)
15print(nombres)
16
17def tri_selection(liste):
18    n = len(liste)
19    for i in range(n - 1):
20        position_min = i
21        for j in range(i + 1, n):
22            if liste[j] < liste[position_min]:
23                position_min = j
24        if position_min != i:
25            temp = liste[i]
26            liste[i] = liste[position_min]
27            liste[position_min] = temp
28
29prénoms = ["Mila", "Loris", "Anja", "Kilian", "Sara", "Pedro"]
30tri_selection(prénoms)
31print(prénoms)

  1. Il suffit d'inverser la comparaison : on sélectionne cette fois le maximum de la partie non triée. Seul le signe < change vraiment ; renommer la variable en position_max rend simplement le code plus lisible.

  2. La fonction trie les prénoms par ordre alphabétique sans aucune modification : en Python, les opérateurs < et > comparent les str selon l'ordre alphabétique ("Anja" < "Loris" vaut True). L'algorithme ne s'intéresse qu'au résultat des comparaisons, pas au type des éléments.

Exercice 13#

Écrivez une fonction nb_echanges_selection(liste) qui trie la liste par sélection et retourne le nombre d'échanges effectués. Avant d'exécuter votre programme, essayez de prédire le résultat pour chacune des trois listes proposées. La troisième devrait vous surprendre !

1def nb_echanges_selection(liste):
2    #Complétez le corps de la fonction
3
4print(nb_echanges_selection([1, 2, 3, 4, 5, 6]))
5print(nb_echanges_selection([2, 1, 4, 3, 6, 5]))
6print(nb_echanges_selection([6, 5, 4, 3, 2, 1]))

Solution

 1def nb_echanges_selection(liste):
 2    nb_echanges = 0
 3    n = len(liste)
 4    for i in range(n - 1):
 5        position_min = i
 6        for j in range(i + 1, n):
 7            if liste[j] < liste[position_min]:
 8                position_min = j
 9        if position_min != i:
10            temp = liste[i]
11            liste[i] = liste[position_min]
12            liste[position_min] = temp
13            nb_echanges = nb_echanges + 1
14    return nb_echanges
15
16print(nb_echanges_selection([1, 2, 3, 4, 5, 6]))
17print(nb_echanges_selection([2, 1, 4, 3, 6, 5]))
18print(nb_echanges_selection([6, 5, 4, 3, 2, 1]))

  1. Une liste déjà triée ne demande aucun échange : chaque minimum est déjà à sa place.

  2. Pour [2, 1, 4, 3, 6, 5], il faut 3 échanges, un pour chaque paire inversée.

  3. La liste triée à l'envers ne demande elle aussi que 3 échanges, et non 5 : en échangeant 1 et 6, on place d'un coup deux éléments à leur place définitive (l'un au début, l'autre à la fin). Il en va de même pour 2 et 5, puis pour 3 et 4.