Nuxt Dashboard Template

Voici une explication détaillée de l’algorithme de Tri par Sélection (ou Selection Sort) basée sur le code fourni.

1. Le principe général

Le Tri par Sélection suit une logique très intuitive, proche de celle qu’on utiliserait pour trier des cartes à jouer manuellement :

On cherche le plus petit élément (le minimum) dans la partie non triée du tableau.
On l’échange avec le premier élément de cette partie non triée.
On répète l’opération pour le reste du tableau, en réduisant la zone de recherche à chaque fois.

Contrairement au tri à bulles qui fait remonter les grands éléments vers la fin, le tri par sélection fait “descendre” les plus petits éléments vers le début.

2. Explication détaillée du code

Analysons les étapes de votre algorithme :

La boucle principale (`pour i de 1 jusqu'à n-1 faire`)

Cette boucle délimite la frontière entre la partie triée (à gauche de i) et la partie non triée (à droite de i, incluant i).
Au début, i=1, donc rien n’est trié. À chaque tour, on va placer le bon élément à la position i, puis on avancera i.

L’initialisation du minimum (`m ← i`)

La variable m va servir à mémoriser l’indice du plus petit élément trouvé jusqu’à présent.
Au début de chaque recherche, on fait l’hypothèse que le premier élément de la zone non triée (Tab[i]) est le minimum. On stocke son indice i dans m.

La boucle de recherche (`pour j de i+1 jusqu'à n faire`)

On parcourt le reste du tableau (de i+1 jusqu’à la fin n) pour voir s’il existe un élément plus petit que celui pointé par m.
La condition : si Tab[j] < Tab[m]
- On compare l’élément actuel Tab[j] avec le minimum actuel Tab[m].
- Si Tab[j] est plus petit, c’est lui le nouveau minimum.
La mise à jour : m ← j
- On met à jour l’indice m pour qu’il pointe vers ce nouveau minimum. Attention : on ne fait pas d’échange ici, on mémorise juste la position.

L’échange final (après la boucle interne)

Une fois la boucle interne terminée, m contient l’indice du plus petit élément de la zone non triée.

On échange Tab[m] (le minimum trouvé) avec Tab[i] (la position où il doit être).
On utilise la variable temp pour effectuer cette permutation.

3. Exemple concret

Prenons le tableau Tab = [30, 10, 50, 20] (n=4).

Tour 1 (i = 1) : On cherche le minimum entre les indices 1 et 4.

m est initialisé à 1 (valeur 30).
j=2 : Tab[2] (10) < Tab[1] (30) ? Oui. m devient 2.
j=3 : Tab[3] (50) < Tab[2] (10) ? Non.
j=4 : Tab[4] (20) < Tab[2] (10) ? Non.
Fin de la boucle interne : m vaut 2 (le 10 est le minimum).
On échange Tab[1] et Tab[2].
Résultat : [10, 30, 50, 20]. (Le 10 est bien placé au début).

Tour 2 (i = 2) : On cherche le minimum entre les indices 2 et 4 (on ignore le 10 déjà trié).

m est initialisé à 2 (valeur 30).
j=3 : Tab[3] (50) < Tab[2] (30) ? Non.
j=4 : Tab[4] (20) < Tab[2] (30) ? Oui. m devient 4.
Fin de la boucle interne : m vaut 4 (le 20 est le minimum de la zone restante).
On échange Tab[2] et Tab[4].
Résultat : [10, 20, 50, 30]. (Les deux premiers sont triés).

Tour 3 (i = 3) : On cherche le minimum entre les indices 3 et 4.

m est initialisé à 3 (valeur 50).
j=4 : Tab[4] (30) < Tab[3] (50) ? Oui. m devient 4.
Fin de la boucle interne : m vaut 4 (le 30 est le minimum).
On échange Tab[3] et Tab[4].
Résultat : [10, 20, 30, 50]. Le tableau est trié.

4. Complexité

Complexité Temporelle : O(n²)

Tout comme le tri à bulles, il y a deux boucles imbriquées.

La boucle externe fait n-1 tours.
La boucle interne fait en moyenne n/2 tours.
Le nombre total de comparaisons est donc approximativement n^2 / 2, ce qui se simplifie en O(n^2).

La nuance importante : Bien que la complexité théorique soit la même que le tri à bulles, le tri par sélection est souvent un peu plus performant en pratique car il effectue beaucoup moins d’échanges (permutations). Il ne fait qu’un seul échange par tour de boucle principal (maximum n échanges), alors que le tri à bulles peut faire des dizaines d’échanges pour faire remonter une valeur.

Complexité Spatiale : O(1)

L’algorithme trie le tableau “sur place” (in-place). Il ne nécessite qu’un nombre constant de variables supplémentaires (m, i, j, temp), peu importe la taille du tableau.