Tri à bulles

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de tri

  • Étudié en profondeur
  • Résoudre le tri d'une collection non triée en ordre croissant/décroissant
  • Peut réduire la complexité des problèmes
  • Quelques algorithmes de tri :
    • tri à bulles
    • tri par sélection
    • tri par insertion
    • tri par fusion
    • tri rapide
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le premier élément et un autre le deuxième.

  • Première valeur supérieure à la deuxième
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le premier élément et un autre le deuxième. Les deux premiers éléments ont été échangés.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le deuxième élément et un autre le troisième.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le troisième élément et un autre le quatrième.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le troisième élément et un autre le quatrième. Les troisième et quatrième éléments ont été échangés.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le quatrième élément et un autre le cinquième.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le quatrième élément et un autre le cinquième. Les quatrième et cinquième éléments ont été échangés.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le quatrième élément et un autre le cinquième. Le cinquième est en bleu car il est ordonné.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le deuxième élément et un autre le troisième. Le dernier élément est en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le deuxième élément et un autre le troisième. Les deuxième et troisième éléments ont été échangés. Le dernier élément est en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le troisième élément et un autre le quatrième. Le dernier élément est en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le troisième élément et un autre le quatrième. Les deux derniers éléments sont en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le premier élément et un autre le deuxième. Les deux premiers éléments ont été échangés. Les deux derniers éléments sont en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

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

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles

Schéma d'une liste de nombres non ordonnés. Un pointeur vise le premier élément et un autre le deuxième. Tous les éléments sont en bleu.

  • Première valeur supérieure à la deuxième
    • Les échanger
  • Deuxième valeur supérieure à la première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles - mise en œuvre

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

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Structures de données et algorithmes en Python

Tri à bulles - mise en œuvre

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Structures de données et algorithmes en Python

Tri à bulles - complexité

  • Pire cas : $O(n^2)$
  • Meilleur cas – version non améliorée : $\Omega(n^2)$
  • Meilleur cas – version améliorée : $\Omega(n)$
  • Cas moyen : $\Theta(n^2)$
  • Peu performant sur de grandes listes très désordonnées
  • Performant pour :
    • grandes listes triées/presque triées
    • petites listes
Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...