Tri par sélection⚓︎
Au programme de NSI
Le tri par sélection fait partie du programme de NSI.
Dans ce cadre il est important de le comprendre et de pouvoir le rédiger.
Le tri par sélection en bref
On cherche la valeur minimale et on la place au début du tableau.
On recommence à partir de la deuxième valeur, puis de la troisième, etc.
Le tri par sélection est l'un des plus simples à comprendre. Il est même probable que vous l'ayez déjà mis en application.
Supposons que vous ayez des cartes à jouer en main et que vous souhaitiez les trier dans l'ordre croissant. Vous pouvez :
-
Parcourir du regard l'ensemble des cartes et déterminer laquelle est la plus petite,
-
Échanger cette carte minimale avec la première carte de votre main,
- Recommencer en cherchant la carte minimale à partir de la deuxième carte et l'échanger avec celle-ci,
- Recommencer à partir de la troisième carte etc.
Déroulé « à la main »⚓︎
-
On considère le tableau \([3,\,4,\,1,\,2]\).
-
Lors de la première itération de l'algorithme, on cherche la valeur minimale à partir de l'indice \(0\). C'est le \(1\) placé à l'indice \(2\). On échange donc les éléments d'indices \(0\) et \(2\). Le tableau devient \([1,\,4,\,3,\,2]\).
-
Lors de l'itération suivante on cherche le minimum à partir de l'indice \(1\) : c'est le \(2\) situé à l'indice \(3\). Après échange, le tableau devient \([1,\,2,\,3,\,4]\).
-
On recommence encore une fois la recherche à partir de l'indice \(2\) : le minimum est à l'indice \(2\), on l'échange avec lui-même.
-
Lorsqu'il ne reste plus qu'un élément à trier (le dernier), il est inutile de chercher le minimum car il est obligatoirement bien placé (en dernière position).
Vous pouvez observer le déroulé de cet algorithme ci-dessous.
Trier votre tableau
Tri par sélection « à la main »
On considère le tableau \([6,\,1,\,4,\,5,\,2,\,3]\).
- Lors de la première itération on échange les valeurs d'indices \(1\) et \(6\)
- Après deux itérations, le tableau est \([1,\,2,\,4,\,5,\,6,\,3]\)
- La valeur \(4\) ne changera de position qu'une seule fois durant l'algorithme
- Au total il y a eu \(5\) échanges de valeurs
Lors de la première itération on échange les valeurs d'indices \(0\) et \(1\). \(1\) et \(6\) sont leurs valeurs !
La première itération échange \(6\) et \(1\), la deuxième \(6\) et \(2\). Ce tableau est donc correct- La valeur \(4\) sera échangée deux fois : avec le \(3\) lors de la troisième itération puis avec le \(5\) lors de la quatrième. Elle sera alors bien placée
- On échange au total : \(6\) et \(1\), \(6\) et \(2\), \(4\) et \(3\), \(5\) et \(4\), \(6\) et \(5\). Il y a donc bien 5 échanges
La performance du tri par sélection peut s'évaluer en nombre d'itérations élémentaires. Attention, il y a deux boucles imbriquées :
- la boucle principale parcourt les valeurs de la première à l'avant dernière afin de les remplacer par la valeur minimale restante,
- au sein de cette boucle, on en trouve une seconde qui cherche la plus petite valeur à partir de celle étudiée dans la boucle principale.
Ainsi, dans un tableau de \(10\) valeurs, on effectue \(9\) itérations de la boucle principale (on rappelle qu'il est inutile de trier le dernier élément). Lors de la première itération, on doit lire les valeurs des \(10\) éléments.
Remarque
Le tri par sélection fera autant d'itérations et lira autant de valeurs qu'on lui fournisse un tableau mélangé, trié dans l'ordre décroissant ou même le tableau est déjà trié !
Combien d'itérations de la boucle principale ? de lectures ?
On considère un tableau de \(20\) valeurs.
- La boucle principale va s'exécuter \(20\) fois
- Lors de la première itération de la boucle principale on doit lire \(19\) valeurs
- Lors de la deuxième itération de la boucle principale on doit lire \(19\) valeurs
- Lors de la troisième itération de la boucle principale on doit lire \(19\) valeur
- Il est inutile de trier la dernière valeur : la boucle principale va donc s'exécuter \(19\) fois
- Lors de la première itération de la boucle principale on doit lire la totalité des \(20\) valeurs
- Lors de la deuxième itération de la boucle principale, on a déjà trié une valeur. Il faut donc trouver le minimum parmi les \(19\) restantes
- Lors de la troisième itération de la boucle principale, on a déjà trié deux valeurs. Il faut donc trouver le minimum parmi les \(18\) restantes
De façon générale, pour un tableau de \(N\) valeurs :
- la boucle principale effectue \(N-1\) itérations,
- la première boucle secondaire lit \(N\) valeurs,
- la deuxième lit \(N - 1\) valeurs,
- la troisième \(N - 2\) valeurs,
- ...
- la dernière boucle secondaire lit \(2\) valeurs.
On lit donc au total \(N + (N - 1) + (N - 2) + \dots+2\). On retrouve quasiment la somme étudiée dans cette page. Le coût de cet algorithme est donc quadratique.
Une autre démonstration du coût
Il y a \(N - 1\) itérations principales qui lisent chacune moins de \(N - 1\) valeurs, donc le coût est inférieur à \(N^2\). Le coût est au plus quadratique.
D'autre part, lors des \(\frac{N}{2}\) premières itérations de la boucle principale, on lit au moins \(\frac{N}{2}\) valeurs : le coût est donc supérieur à \(\frac{N}{2} \times \frac{N}{2} = \frac{N^2}{4}\). Le coût de l'algorithme est donc au moins quadratique.
Bilan : l'algorithme a un coût au minimum et au maximum quadratique ! Son coût est donc quadratique.
Notons que même face à un tableau initialement trié dans l'ordre croissant, le tri par sélection effectuera autant de parcours du tableau et de lectures de valeurs. Le coût restera quadratique.
Minimum à partir de ...⚓︎
L'une des étapes essentielles du tri par sélection est donc de déterminer l'indice de la valeur minimale à partir d'un certain indice i.
Cette recherche ayant lieu à plusieurs reprises, nous allons utiliser une fonction pour la réaliser.
La fonction indice_minimum_depuis
Compléter la fonction indice_minimum_depuis prenant en argument un tableau ainsi qu'un indice i et renvoyant l'indice de la valeur minimale parmi les éléments situés après celui d'indice i (inclus).
On garantit que i est un indice valide.
Si plusieurs valeurs sont égales au minimum, on renverra l'indice de la première d'entre elles.
Solution
def indice_minimum_depuis(tableau, i):
i_mini = i
for j in range(i + 1, len(tableau)):
if tableau[j] < tableau[i_mini]:
i_mini = j
return i_mini
Dans le cas où le minimum apparaît plusieurs fois, on aurait pu aussi retenir la dernière d'entre elles. Le fonctionnement général de l'algorithme aurait été similaire (mais il n'aurait plus été stable)
En entier !⚓︎
On donne les fonctions echange et indice_minimum_depuis.
La fonction tri_selection
Compléter la fonction tri_selection prenant en argument un tableau et le triant en place à l'aide du tri par sélection.
On pourra utiliser les fonctions echange et indice_minimum_depuis.
Solution
def tri_selection(tableau):
for i in range(len(tableau) - 1):
i_mini = indice_minimum_depuis(tableau, i)
echange(tableau, i, i_mini)
Une seule fonction⚓︎
Le code précédent est court et lisible.
Toutefois le plus souvent le tri par sélection est rédigé en une seule fonction. Terminons notre étude par cette rédaction.
La fonction tri_selection (bis)
Compléter la fonction tri_selection prenant en argument un tableau et le triant en place à l'aide du tri par sélection.
On n'utilisera pas les fonctions echange et indice_minimum_depuis.
Solution
def tri_selection(tableau):
for i in range(len(tableau) - 1):
i_mini = i
for j in range(i + 1, len(tableau)):
if tableau[j] < tableau[i_mini]:
i_mini = j
tableau[i], tableau[i_mini] = tableau[i_mini], tableau[i]