Bilan sur les tris par sélection et insertion

Tri par sélection

• À chaque itération on ramène la valeur minimale en première position

• On itère sur tous les éléments sauf le dernier. Appliquer l'algorithme au dernier élément n'est pas pas nécessaire mais ne modifie pas la validité de l'algorithme.

• Le coût est quadratique

• Il y a autant de comparaisons quel que soit le tableau proposé.

• L'algorithme en pseudo-code est :

  📋 Pseudo-code

  Pour i allant de 0 inclus à longueur(tableau) - 1 exclu :
      i_mini est l'indice de l'élément minimal parmi ceux d'indices supérieurs ou égaux à i
      Échanger les éléments d'indices i et i_mini (si i ≠ i_mini)
  

Tri par insertion

• À chaque itération on décale une valeur vers la gauche jusqu'à ce qu'elle soit au début du tableau ou précédée par une valeur inférieure ou égale

• On itère sur tous les éléments sauf le dernier premier. Appliquer l'algorithme au premier élément n'est pas pas nécessaire mais ne modifie pas la validité de l'algorithme.

• Le coût est quadratique

• Le pire des cas est quand le tableau est trié dans l'ordre décroissant.

• L'algorithme en pseudo-code est :

  📋 Pseudo-code

  Pour i allant de 1 à longueur(tableau) (exclu) :
      valeur_a_inserer = tableau[i]
      j = i
      Tant que j > 0 et tableau[j - 1] > valeur_a_inserer :
          tableau[j] = tableau[j - 1]
          j = j - 1
      tableau[j] = valeur_a_inserer
  

Remarque

Le tri à bulles n'étant pas au programme de la spécialité NSI, on ne propose pas de bilan le concernant.