C'est un tri qualifié de lent.

Observer l'animation toujours sur le même site, mais en cliquant sur Selection Sort

Le principe est de parcourir le tableau à la recherche de la plus petite valeur et de la placer en tout début de tableau et de recommencer ainsi de suite.

Algorithme par sélection

varA ← 0
tant que varA<longueur(tab):
  varB ← varA + 1
  min ← varA
  tant que varB<longueur(tab):
    si tab[varB]<tab[min]:
      min ← varB
    fin si
    varB ← varB + 1
  fin tant que
  si min≠varA :
    échanger tab[varA] et tab[min]
  fin si
  varA ← varA + 1
fin tant que

Vous testez à la main cet algorithme en prenant comme valeurs tab[ 44, 73, 52, 28].

Quelles sont les valeurs de varA et varB pour lesquelles les 2 boucles s'arrêtent ?

Complexité

Quelle est la complexité de cet algorithme puisqu'il y a 2 boucles imbriquées ?

Pyhton

Pour ceux qui veulent : réaliser en python le programme correspondant et lancez-le afin de vérifier le résultat.

Exercice

Soit l'algorithme ci-dessous que vous devez faire tourner à la main.

Les colonnes bleues correspondent à la partie bleue de l'algorithme.

Compléter les valeurs au fur et à mesure que vous faites tourner l'algorithme à la main sans mettre d'espace.

Ne compléter les colonnes que si nécessaire

[28,12,30,29]