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 ordonnés. Un pointeur indique le premier élément.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le premier élément. Le premier élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le deuxième élément. Le premier élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le deuxième élément. Le deuxième élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le troisième élément. Le deuxième élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le quatrième élément. Le deuxième élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le quatrième élément. Le quatrième élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Un pointeur indique le cinquième élément. Le quatrième élément est en orange.

  • Trouver la plus petite valeur
Structures de données et algorithmes en Python

Tri par sélection

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

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

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

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Le premier élément est en bleu et le deuxième en orange. Un pointeur indique le deuxième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Le premier élément est en bleu et le deuxième en orange. Un pointeur indique le troisième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Le premier élément est en bleu et le deuxième en orange. Un pointeur indique le quatrième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Le premier élément est en bleu et le deuxième en orange. Un pointeur indique le cinquième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu. Un pointeur indique le troisième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le troisième est en orange. Un pointeur indique le troisième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le troisième est en orange. Un pointeur indique le quatrième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le quatrième est en orange. Un pointeur indique le quatrième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le quatrième est en orange. Un pointeur indique le cinquième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonné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.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonné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.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu. Un pointeur indique le quatrième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième est en orange. Un pointeur indique le quatrième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième est en orange. Un pointeur indique le cinquième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le cinquième est en orange. Un pointeur indique le cinquième élément.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonné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.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Schéma d'une liste de nombres non ordonné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.

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

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

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

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

  • Trouver la plus petite valeur
  • Échanger la plus petite valeur avec le premier élément non trié
Structures de données et algorithmes en Python

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
Structures de données et algorithmes en Python

Tri par sélection – complexité

  • Pire cas : $O(n^2)$
  • Cas moyen : $\Theta(n^2)$
  • Meilleur cas : $\Omega(n^2)$
Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés.

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier et deuxième éléments sont en bleu. Le troisième a été surélevé.

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième a été surélevé.

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième a été surélevé. Les troisième et deuxième éléments ont été décalés vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième a été surélevé. Les troisième, deuxième et troisième éléments ont été décalés vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu. Le troisième a été surélevé. Les troisième, deuxième et troisième éléments ont été décalés vers la droite. L'élément surélevé est maintenant en première position.

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont en bleu. Le cinquième a été surélevé.

Structures de données et algorithmes en Python

Tri par insertion

Schéma d'une liste de nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont en bleu. Le cinquième a été surélevé. Le quatrième a été décalé vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

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

Structures de données et algorithmes en Python

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
Structures de données et algorithmes en Python

Tri par insertion – complexité

  • Pire cas : $O(n^2)$
  • Cas moyen : $\Theta(n^2)$
  • Meilleur cas : $\Omega(n)$
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...