Tri par sélection et tri par insertion

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le premier élément.

  • Déterminer valeur la plus basse
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le premier élément. Le premier élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le deuxième élément. Le premier élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le deuxième élément. Le deuxième élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le troisième élément. Le deuxième élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du quatrième élément. Le deuxième élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du quatrième élément. Le quatrième élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur qui pointe vers le cinquième élément. Le quatrième élément est coloré en orange.

  • Déterminez valeur la plus faible
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le quatrième élément est coloré en orange. Il y a deux flèches qui indiquent que le premier et le quatrième éléments seront échangés.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en orange. Les premier et quatrième éléments ont été intervertis.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu et le second en orange. Il y a un pointeur qui pointe vers le deuxième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu et le second en orange. Il y a un pointeur qui pointe vers le troisième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu et le second en orange. Il y a un pointeur qui pointe vers le quatrième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est en bleu et le second en orange. Il y a un pointeur qui pointe vers le cinquième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu. Il y a un pointeur qui pointe vers le troisième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le troisième élément est en orange. Il y a un pointeur qui pointe vers le troisième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le troisième élément est en orange. Il y a un pointeur qui pointe vers le quatrième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu et le quatrième élément est coloré en orange. Il y a un pointeur qui pointe vers le quatrième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu et le quatrième élément est coloré en orange. Il y a un pointeur qui pointe vers le cinquième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu et le quatrième élément est coloré en orange. Il y a deux flèches qui indiquent que le troisième et le quatrième éléments seront échangés.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont en bleu et le troisième élément est en orange. Les troisième et quatrième éléments ont été intervertis.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Il y a un pointeur qui pointe vers le quatrième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième élément est en orange. Il y a un pointeur qui pointe vers le quatrième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième élément est en orange. Il y a un pointeur qui pointe vers le cinquième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le cinquième élément est en orange. Il y a un pointeur qui pointe vers le cinquième élément.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le cinquième élément est en orange. Il y a deux flèches qui indiquent que le quatrième et le cinquième éléments seront échangés.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont en bleu, et le quatrième élément est en orange. Le quatrième et le cinquième éléments ont été intervertis.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en bleu.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec premier élément non trié
Structures de données et algorithmes en Python

Tri par sélection

Une représentation schématique d’une liste avec des nombres non ordonnés. Tous les éléments sont colorés en bleu.

  • Déterminez valeur la plus faible
  • Échanger valeur plus basse avec 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

Une représentation schématique d’une liste avec des nombres non ordonnés.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est coloré en bleu et le deuxième élément a été élevé au-dessus des autres.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Le premier élément est coloré en bleu et le deuxième élément a été surélevé au-dessus des autres. Le premier élément a été décalé vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Le deuxième élément est coloré en bleu. L’élément qui a été déplacé vers le haut est maintenant en première position.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier et deuxième éléments sont colorés en bleu. Le troisième élément a été élevé au-dessus des autres.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Le troisième élément a été élevé au-dessus des autres.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Le troisième élément a été placé au-dessus des autres. Le troisième élément a été décalé vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Le troisième élément a été placé au-dessus des autres. 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

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Le troisième élément a été placé au-dessus des autres. Le troisième, le deuxième et le troisième éléments ont été décalés vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième et troisième éléments sont colorés en bleu. Le troisième élément a été placé au-dessus des autres. Les troisième, deuxième et troisième éléments ont été décalés vers la droite. L’élément qui a été déplacé est maintenant en première position.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en bleu.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en bleu. Le cinquième élément a été placé au-dessus des autres.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en bleu. Le cinquième élément a été élevé au-dessus des autres. Le quatrième élément a été décalé vers la droite.

Structures de données et algorithmes en Python

Tri par insertion

Une représentation schématique d’une liste avec des nombres non ordonnés. Les premier, deuxième, troisième et quatrième éléments sont colorés en bleu. Le cinquième élément a été élevé au-dessus des autres. L’élément qui a été déplacé est maintenant à la 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...