Tri à bulles

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de tri

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Les premier et deuxième éléments ont été permutés.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du deuxième élément et un autre en direction du troisième élément.

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

Tri à bulles

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

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du troisième élément et un autre pointeur en direction du quatrième élément. Les troisième et quatrième éléments ont été intervertis.

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

Tri à bulles

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 et un autre en direction du cinquième élément.

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

Tri à bulles

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 et un autre en direction du cinquième élément. Les quatrième et cinquième éléments ont été intervertis.

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

Tri à bulles

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 et un autre en direction du cinquième élément. Le cinquième élément est coloré en bleu parce qu’il est ordonné.

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

Tri à bulles

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

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

Tri à bulles

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

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du deuxième élément et un autre en direction du troisième élément. Le deuxième et le troisième éléments ont été intervertis. Le dernier élément est coloré en bleu.

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

Tri à bulles

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

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du troisième élément et un autre pointeur en direction du quatrième élément. Les deux derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Les deux derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Les premier et deuxième éléments ont été intervertis. Les deux derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du deuxième élément et un autre en direction du troisième élément. Les deux derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du deuxième élément et un autre en direction du troisième élément. Les trois derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Les trois derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Les quatre derniers éléments sont en bleu.

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

Tri à bulles

Une représentation schématique d’une liste avec des nombres non ordonnés. Il y a un pointeur en direction du premier élément et un autre en direction du deuxième élément. Tous les éléments sont colorés en bleu.

  • Première valeur supérieure à deuxième valeur
    • Les échanger
  • Deuxième valeur supérieure à première valeur
    • Rien
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)$
  • Fonctionne mal avec grandes listes très désordonnées
  • Fonctionne bien :
    • grandes listes triées/quasi 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...