Formation I.S.N.

Bubble : programmer

programmation du tri bulle.

Écrire une fonction python triant une liste de bulles suivant l'algorithme proposé dans la page précédente.

  • un code possible
  • avec traces

from random import randint

def tri_bulles(bulles):
	n = len(bulles)
	for i in range(0,n-1):
		for j in range(n-1,i,-1):
			if bulles[j] < bulles[j-1]:
				bulles[j], bulles[j-1] = bulles[j-1], bulles[j]



champagne = [ randint(1,15) for _ in range(randint(5,15)) ]
print(champagne)

 

tri_bulles(champagne)
print(champagne)


from random import randint


def afficher(liste, i, j):
	for x in liste:
		print(x, end=' ')
	print()
	for k in range(len(liste)):
		if k == i : print("i ", end=' ')
		elif k == j : print("j ", end=' ')
		else : print("  ", end=' ')
	print()
	print()

def tri_bulles(bulles):
	n = len(bulles)
	for i in range(0,n-1):
		for j in range(n-1,i,-1):
			afficher(bulles, i, j)
			if bulles[j] < bulles[j-1]:
				bulles[j], bulles[j-1] = bulles[j-1], bulles[j]
				 



champagne = [ randint(10,99) for _ in range(randint(5,15)) ]
print(champagne)



tri_bulles(champagne)
print(champagne)

On obtient par exemple : 

 
[23, 46, 43, 84, 53, 93, 86, 42, 15, 54, 39]
23 46 43 84 53 93 86 42 15 54 39 
i                             j  

23 46 43 84 53 93 86 42 15 39 54 
i                          j     

23 46 43 84 53 93 86 42 15 39 54 
i                       j        

23 46 43 84 53 93 86 15 42 39 54 
i                    j           

23 46 43 84 53 93 15 86 42 39 54 
i                 j              

23 46 43 84 53 15 93 86 42 39 54 
i              j                 

23 46 43 84 15 53 93 86 42 39 54 
i           j                    

23 46 43 15 84 53 93 86 42 39 54 
i        j                       

23 46 15 43 84 53 93 86 42 39 54 
i     j                          

23 15 46 43 84 53 93 86 42 39 54 
i  j                             

15 23 46 43 84 53 93 86 42 39 54 
   i                          j  

15 23 46 43 84 53 93 86 42 39 54 
   i                       j     

15 23 46 43 84 53 93 86 39 42 54 
   i                    j        

15 23 46 43 84 53 93 39 86 42 54 
   i                 j           

15 23 46 43 84 53 39 93 86 42 54 
   i              j              

15 23 46 43 84 39 53 93 86 42 54 
   i           j                 

15 23 46 43 39 84 53 93 86 42 54 
   i        j                    

15 23 46 39 43 84 53 93 86 42 54 
   i     j                       

15 23 39 46 43 84 53 93 86 42 54 
   i  j                          

15 23 39 46 43 84 53 93 86 42 54 
      i                       j  

15 23 39 46 43 84 53 93 86 42 54 
      i                    j     

15 23 39 46 43 84 53 93 42 86 54 
      i                 j        

15 23 39 46 43 84 53 42 93 86 54 
      i              j           

15 23 39 46 43 84 42 53 93 86 54 
      i           j              

15 23 39 46 43 42 84 53 93 86 54 
      i        j                 

15 23 39 46 42 43 84 53 93 86 54 
      i     j                    

15 23 39 42 46 43 84 53 93 86 54 
      i  j                       

15 23 39 42 46 43 84 53 93 86 54 
         i                    j  

15 23 39 42 46 43 84 53 93 54 86 
         i                 j     

15 23 39 42 46 43 84 53 54 93 86 
         i              j        

15 23 39 42 46 43 84 53 54 93 86 
         i           j           

15 23 39 42 46 43 53 84 54 93 86 
         i        j              

15 23 39 42 46 43 53 84 54 93 86 
         i     j                 

15 23 39 42 43 46 53 84 54 93 86 
         i  j                    

15 23 39 42 43 46 53 84 54 93 86 
            i                 j  

15 23 39 42 43 46 53 84 54 86 93 
            i              j     

15 23 39 42 43 46 53 84 54 86 93 
            i           j        

15 23 39 42 43 46 53 54 84 86 93 
            i        j           

15 23 39 42 43 46 53 54 84 86 93 
            i     j              

15 23 39 42 43 46 53 54 84 86 93 
            i  j                 

15 23 39 42 43 46 53 54 84 86 93 
               i              j  

15 23 39 42 43 46 53 54 84 86 93 
               i           j     

15 23 39 42 43 46 53 54 84 86 93 
               i        j        

15 23 39 42 43 46 53 54 84 86 93 
               i     j           

15 23 39 42 43 46 53 54 84 86 93 
               i  j              

15 23 39 42 43 46 53 54 84 86 93 
                  i           j  

15 23 39 42 43 46 53 54 84 86 93 
                  i        j     

15 23 39 42 43 46 53 54 84 86 93 
                  i     j        

15 23 39 42 43 46 53 54 84 86 93 
                  i  j           

15 23 39 42 43 46 53 54 84 86 93 
                     i        j  

15 23 39 42 43 46 53 54 84 86 93 
                     i     j     

15 23 39 42 43 46 53 54 84 86 93 
                     i  j        

15 23 39 42 43 46 53 54 84 86 93 
                        i     j  

15 23 39 42 43 46 53 54 84 86 93 
                        i  j     

15 23 39 42 43 46 53 54 84 86 93 
                           i  j  

[15, 23, 39, 42, 43, 46, 53, 54, 84, 86, 93]

amélioration.

On reprend le programme de tri du corrigé précédent.


from random import randint

def tri_bulles(bulles):
	n = len(bulles)
	for i in range(0,n-1):
		for j in range(n-1,i,-1):
			if bulles[j] < bulles[j-1]:
				bulles[j], bulles[j-1] = bulles[j-1], bulles[j]
 
champagne = [ randint(1,15) for _ in range(randint(5,15)) ]
print(champagne)
 
tri_bulles(champagne)
print(champagne)
  1. Justifier que si, pour une valeur de i donnée, il n'y a aucun échange dans la boucle for j correspondante, alors il n'y aura pas non plus d'échanges pour les valeurs de i suivantes.
  2. En déduire une amélioration du programme proposé.
  • Question 1
  • Question 2

Si une valeur de i donnée, il n'y a pas d'échange, cela signifie que tous les tests if bulles[j] < bulles[j-1]: de la boucle en j valent False, autrement dit que l'on a bulles[n-1] ≥ bulles[n-2], bulles[n-1] ≥ bulles[n-2], ..., bulles[i+1] ≥ bulles[i].

Comme il n'y a pas eu d'échange, les tests pour les valeurs suivantes de i seront les mêmes (ou plutôt une partie de ceux là) : il n'y aura donc pas non plus d'échange. En d'autres termes, la liste est triée dès qu'une boucle en j ne donne lieu à aucun échange.

Pour améliorer le temps de calcul, on introduit une variable permettant de savoir s'il y a eu échange ou non. On stoppe la boucle en i dès qu'il n'y a plus d'échanges. 


from random import randint

def tri_bulles(bulles):
	n = len(bulles)
	for i in range(0,n-1):
		echange = False
		for j in range(n-1,i,-1):
			if bulles[j] < bulles[j-1]:
				bulles[j], bulles[j-1] = bulles[j-1], bulles[j]
				echange = True
		if not(echange) : break



champagne = [ randint(1,15) for _ in range(randint(5,15)) ]
print(champagne)



tri_bulles(champagne)
print(champagne)