Algorithmes et Structures de Données

Tri à bulles (Bubble Sort)

Étant donné un tableau de n entiers, nous souhaitons les trier par ordre croissant. Le tri à bulles (Bubble Sort) est l’un des algorithmes les plus connus et les plus simples pour y parvenir (toutefois, gardez à l’esprit qu’il n’est pas rapide – la plupart des algorithmes utilisés en production s’appuient sur des techniques différentes pour trier une liste de nombres).
Video preview
Dans l’algorithme de tri à bulles, on parcourt plusieurs fois le tableau donné et on permute tout élément voisin qui n’est pas dans le bon ordre. Ainsi, si , on échange ces deux éléments pour garantir que le tableau soit bien en ordre croissant.
Plus concrètement, on prend le tableau initial a (par exemple a = [4, 1, -1, 0, 2, 8]) et on observe les deux premiers éléments. S’ils ne sont pas dans l’ordre, on échange leurs places (ce qui donne [1, 4, -1, 0, 2, 8]). Puis on passe à la paire suivante. S’ils ne sont pas dans l’ordre, on les permute (ce qui donne [1, -1, 4, 0, 2, 8]). On répète ce processus jusqu’à la fin du tableau (dans notre exemple, on obtient successivement [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → aucune modification → terminé).
Ensuite, on relance la boucle en partant du début du tableau. On regarde la première paire et on la compare. S’ils ne sont pas dans le bon ordre, on les permute. On passe ensuite à la paire suivante, puis à celle d’après, et ainsi de suite jusqu’à la fin du tableau. Dans notre exemple, cela donne : [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → aucune modification.
On répète ce processus jusqu’à ce que le tableau soit entièrement trié :
a = [...]
while True:                                 # tourner jusqu'à ce que le tableau soit trié
    is_sorted = True                        # si on modifie quelque chose, on passe ceci à False
    for i in range(len(a) - 1):             # parcourir de 0 ... n-2
        if a[i] > a[i + 1]:                 # si un élément n'est pas dans l'ordre
            is_sorted = False               # => le tableau n'était pas trié
            a[i], a[i + 1] = a[i + 1], a[i] # échanger a[i] et a[i + 1]
    
    if is_sorted:                           # arrêter le processus si a est trié
        break
print(a)
Il existe une optimisation possible pour éviter d’effectuer des opérations inutiles :
  • Nous savons qu’après chaque itération, les éléments les plus grands se retrouvent à la fin du tableau. Ainsi, après k passages, les k éléments les plus élevés sont assurément triés et se situent en fin de tableau. Par conséquent, nous pouvons ignorer ces éléments lors de la boucle interne
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = limite supérieure pour la boucle interne
    is_sorted = True                        # si on modifie quelque chose, on passe ceci à False
    for i in range(u):                      # parcourir de 0 ... u-1
        if a[i] > a[i + 1]:                 # si un élément n'est pas dans l'ordre
            is_sorted = False               # => le tableau n'était pas trié
            a[i], a[i + 1] = a[i + 1], a[i] # échanger a[i] et a[i + 1]
    
    if is_sorted:                           # arrêter le processus si a est trié
        break
print(a)
Le pire scénario pour l’algorithme de tri à bulles se produit lorsque les nombres sont dans l’ordre strictement inverse (décroissant) au lieu d’être croissants. Dans ce cas, l’algorithme effectuera opérations, ce qui est nettement plus que dans le cas d’algorithmes plus rapides que nous verrons plus tard dans ce cours.
Voyons comment cet algorithme fonctionne sur plusieurs tableaux :
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ échange ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ échange ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ échange ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ échange ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ échange ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ échange ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ échange ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ échange ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ ne rien faire
Activité complémentaire (vidéo intéressante)
La chaîne YouTube de Lines That Connect propose une excellente vidéo qui explore plus en profondeur l’algorithme de tri à bulles et explique l’intuition derrière la courbe qui se forme lors de son exécution.
Video preview
Vidéo de Lines That Connect – la courbe du tri à bulles.

Défi

n personnes participent à une compétition. Vous devez les positionner par ordre croissant de taille. À chaque étape, vous pouvez demander à deux participants voisins d’échanger leurs places. Vous n’avez pas beaucoup de temps, donc vous souhaitez faire cela de la manière la plus efficace possible.
Vous avez décidé d’écrire un programme qui affichera les indices des participants qui doivent échanger leurs positions. La numérotation commence à 0.

Entrée

La première ligne de l’entrée contient un seul entier n (1 ≤ n ≤ 1000).
La ligne suivante contient n entiers séparés par des espaces, ( ≤ ≤ ) représentant les hauteurs des participants.

Sortie

Le programme doit imprimer les paires d’indices des participants qui doivent échanger leurs positions. Chaque paire doit être imprimée sur une nouvelle ligne. En cas de multiples réponses optimales, n’importe laquelle est acceptable.

Exemples

Input
Output
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Explication

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue