Enonce

La fonction tri_bulles prend en paramètre une liste tab d’entiers (type list) et le modifie pour le trier par ordre croissant.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant le tableau de gauche à droite et en échangeant au passage les éléments voisins mal ordonnés (si la valeur de l’élément d’indice i a une valeur strictement supérieure à celle de l’indice i + 1, ils sont échangés). Le tri place ensuite en avant-dernière position le plus grand élément du tableau privé de son dernier élément en procédant encore à des échanges d’éléments voisins. Ce principe est répété jusqu’à placer le minimum en première position.

Exemple : pour trier le tableau [7, 9, 4, 3] :

  • première étape : 7 et 9 ne sont pas échangés, puis 9 et 4 sont échangés, puis 9 et 3 sont échangés, le tableau est alors [7, 4, 3, 9]
  • deuxième étape : 7 et 4 sont échangés, puis 7 et 3 sont échangés, le tableau est alors [4, 3, 7, 9]
  • troisième étape : 4 et 3 sont échangés, le tableau est alors [3, 4, 7, 9]

Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = ... 
    tab[i] = ... 
    tab[j] = ... 

def tri_bulles(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri à bulles.'''
    n = len(tab)
    for i in range(...): 
        for j in range(...): 
            if ... > ...: 
                echange(tab, j, ...)

Exemples : 

>>> tab = []
>>> tri_bulles(tab)
>>> tab
[]
>>> tab2 = [9, 3, 7, 2, 3, 1, 6]
>>> tri_bulles(tab2)
>>> tab2
[1, 2, 3, 3, 6, 7, 9]
>>> tab3 = [9, 7, 4, 3]
>>> tri_bulles(tab3)
>>> tab3
[3, 4, 7, 9]