Aller au contenu

III) Tri par sélection

1) Algorithme du tri par sélection

Comme pour le tri par insertion, commençons par le visionnage d'une petite vidéo :

https://www.youtube.com/watch?v=8u3Yq-5DTN8

On peut résumer le principe de fonctionnement de l'algorithme de tri par sélection avec le schéma suivant :

Voici l'algorithme du tri par sélection :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i←1
tant que i<longueur(t):   //boucle 1
  j←i+1
  min←i
  tant que j<=longueur(t):   //boucle 2
    si t[j]<t[min]:
      min←j
    fin si
    j←j+1
  fin tant que
  si min≠i :
    échanger t[i] et t[min]
  fin si
  i←i+1
fin tant que
FIN

2) Complexité du tri par sélection

Essayons maintenant de déterminer la complexité de l'algorithme de tri par sélection :

Pour établir la complexité de cet algorithme, comme pour l'algorithme de tri par insertion, nous n'allons pas directement nous intéresser au nombre d'opérations élémentaires. Cette fois, nous allons comptabiliser les comparaisons entre 2 entiers.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [12, 8, 23, 10, 15] à t = [8, 12, 23, 10, 15] :

(i = 1) nous avons 4 comparaisons : 12 avec 8, puis 8 avec 23, puis 8 avec 10 et enfin 8 avec 15.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 12, 23, 10, 15] à t = [8, 10, 23, 12, 15] :

(i = 2) nous avons 3 comparaisons : 12 avec 23, puis 12 avec 10, et enfin 10 avec 15.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 10, 23, 12, 15] à t = [8, 10, 12, 23, 15] :

(i = 3) nous avons 2 comparaisons : 23 avec 12 et 12 avec 15.

Si nous nous intéressons à l'étape qui nous permet de passer de t = [8, 10, 12, 23, 15] à t = [8, 10, 12, 15, 23] :

(i = 4) nous avons 1 comparaison : 23 avec 15.

Pour trier un tableau comportant 5 éléments nous avons : comparaisons.

Dans le cas où nous avons un tableau à trier qui contient éléments, nous aurons : comparaisons.

Si vous n'êtes pas convaincu, faites le test avec un tableau de 6 éléments, vous devriez trouver comparaisons.

Vous avez sans doute déjà remarqué que nous avons un résultat similaire au tri par insertion (sauf que nous nous intéressons ici aux comparaisons alors que pour le tri par insertion nous nous intéressons aux décalages, mais cela ne change rien au problème)

Conclusion : nous allons trouver exactement le même résultat que pour le tri par insertion : l'algorithme de tri par sélection a une complexité en (complexité quadratique).

Nous avons vu précédemment des algorithmes de complexité linéaire (O(n)) avec les algorithmes de recherche d'un entier dans un tableau, de recherche d'un extremum ou encore de calcul d'une moyenne. Nous avons vu ici que les algorithmes de tri par sélection et de tri par insertion ont tous les deux une complexité quadratique (). Il est important de bien avoir conscience de l'impact de ces complexités sur l'utilisation des algorithmes : si vous doublez la taille du tableau, vous doublerez le temps d'exécution d'un algorithme de complexité linéaire, en revanche vous quadruplerez le temps d'exécution d'un algorithme de complexité quadratique.

Si votre ordinateur met secondes pour trier un tableau de taille , il mettra secondes pour trier une tableau de taille .