Tri à bulles

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de tri

  • Étudiés en profondeur
  • Résoudre le tri d’une collection non ordonné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 second.

  • Première valeur > seconde
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 second. Le premier et le second ont été échangés.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 troisième et le quatrième ont été échangés.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 quatrième et le cinquième ont été échangés.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 second. Le dernier élément est en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 deuxième et le troisième ont été échangés. Le dernier élément est en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 second. Les deux derniers éléments sont en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 second. Le premier et le second ont été échangés. Les deux derniers éléments sont en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 > seconde
    • Les échanger
  • Seconde valeur > 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 second. Les trois derniers éléments sont en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 second. Les quatre derniers éléments sont en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > 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 second. Tous les éléments sont en bleu.

  • Première valeur > seconde
    • Les échanger
  • Seconde valeur > première
    • Ne rien faire
Structures de données et algorithmes en Python

Tri à bulles - implémentation

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 - implémentation

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 efficace sur de grandes listes très désordonnées
  • Efficace 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...