Tri par sélection et tri par insertion

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le premier élément.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le premier élément. Le premier élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le deuxième élément. Le premier élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le deuxième élément. Le deuxième élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le troisième élément. Le deuxième élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le quatrième élément. Le deuxième élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le quatrième élément. Le quatrième élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Un curseur pointe le cinquième élément. Le quatrième élément est en orange.

Identifier la plus petite valeur

Tri par sélection

Schéma d’une liste de nombres non triés. Le quatrième élément est en orange. Deux flèches indiquent l’échange entre le premier et le quatrième éléments.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Le premier élément est en orange. Le premier et le quatrième éléments ont été échangés.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième en orange. Un curseur pointe le deuxième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième en orange. Un curseur pointe le troisième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième en orange. Un curseur pointe le quatrième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième en orange. Un curseur pointe le cinquième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu. Un curseur pointe le troisième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le troisième est en orange. Un curseur pointe le troisième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le troisième est en orange. Un curseur pointe le quatrième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le quatrième est en orange. Un curseur pointe le quatrième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le quatrième est en orange. Un curseur pointe le cinquième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le quatrième est en orange. Deux flèches indiquent l’échange entre les troisième et quatrième éléments.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu et le troisième est en orange. Les troisième et quatrième éléments ont été échangés.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu. Un curseur pointe le quatrième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième est en orange. Un curseur pointe le quatrième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième est en orange. Un curseur pointe le cinquième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu, et le cinquième est en orange. Un curseur pointe le cinquième élément.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu, et le cinquième est en orange. Deux flèches indiquent l’échange entre les quatrième et cinquième éléments.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième est en orange. Les quatrième et cinquième éléments ont été échangés.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en bleu.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection

Schéma d’une liste de nombres non triés. Tous les éléments sont en bleu.

Identifier la plus petite valeur
L’échanger avec le premier élément non trié

Tri par sélection - implémentation

def selection_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length - 1):

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

Tri par sélection - complexité

Pire cas : $O(n^2)$
Cas moyen : $\Theta(n^2)$
Meilleur cas : $\Omega(n^2)$

Tri par insertion

Schéma d’une liste de nombres non triés.

Tri par insertion

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième est surélevé.

Tri par insertion

Schéma d’une liste de nombres non triés. Le premier élément est en bleu et le deuxième est surélevé. Le premier élément a été décalé à droite.

Tri par insertion

Schéma d’une liste de nombres non triés. Le deuxième élément est en bleu. L’élément surélevé est maintenant en première position.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier et deuxième éléments sont en bleu. Le troisième élément est surélevé.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième élément est surélevé.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième élément est surélevé. Le troisième élément a été décalé à droite.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième élément est surélevé. Les troisième et deuxième éléments ont été décalés à droite.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième élément est surélevé. Les troisième, deuxième et troisième éléments ont été décalés à droite.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en bleu.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en bleu. Le cinquième élément est surélevé.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en bleu. Le cinquième élément est surélevé. Le quatrième élément a été décalé à droite.

Tri par insertion

Schéma d’une liste de nombres non triés. Les premier, deuxième, troisième et quatrième éléments sont en bleu. Le cinquième élément est surélevé. L’élément surélevé est maintenant en quatrième position.

Tri par insertion - implémentation

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

Tri par insertion - complexité

Pire cas : $O(n^2)$
Cas moyen : $\Theta(n^2)$
Meilleur cas : $\Omega(n)$

Passons à la pratique !

Structures de données et algorithmes en Python