Formation I.S.N.

Le tri rapide

Le principe.

Le principe du quicksort est basé sur le principe de la fonction de répartition dessus-dessous autour d'un pivot vue dans la page précédente.

Ce principe est le suivant :

  1. Partitionner la liste autour d'un pivot, ce qui lui donne la forme suivante : une liste de valeurs inférieures au égales au pivot, suivi du pivot qui se trouve à sa place définitive, suivi de valeurs strictement supérieures au pivot.
  2. Recommencer le premier point sur chacune des deux sous-listes droite et gauche tant qu'elles ont une longueur au moins égale à deux.

programmer.

Donnez une version python de ce descriptif.

  • un code possible

Une première traduction "brute" du descriptif : 


from random import randint

def quicksort(liste):
	if len(liste) <= 1 :
		return liste
	else :
		pivot = liste[0]
		avant = [ x for x in liste if x < pivot ]
		apres = [x for x in liste if x > pivot ]
		return quicksort(avant) + [pivot] + quicksort(apres)
		
		
		
L = [ randint(100, 999)  for _  in range(randint(5,15)) ]

print(L)
print(quicksort(L))

On peut améliorer un peu cette première version pour les cas où les listes à trier présenteraient beaucoup de valeurs égales : 


from random import randint

def quicksort(liste):
	if len(liste) <= 1 :
		return liste
	else :
		pivot = liste[0]
		avant = [ x for x in liste if x < pivot ]
		milieu = [ x for x in liste if x == pivot ]
		apres = [x for x in liste if x > pivot ]
		return quicksort(avant) + milieu + quicksort(apres)
		
		
		
L = [ randint(100, 999)  for _  in range(randint(5,15)) ]

print(L)
print(quicksort(L))

Ce premier code permet de bien saisir le principe. Il a toutefois le défaut de créer des listes intermédiaires et donc d'augmenter la complexité en mémoire.
Tentez d'écrire une version éliminant ce problème.

programmer.

Donnez une version python éliminant les défauts du corrigé proposé dans l'exercice précédent. En d'autres termes, proposez une version du tri rapide qui trie la liste en place (sans création de listes intermédiaires).

  • un code possible
  • avec affichage d'états intermédiaires

from random import randint


def partitionDessusDessous(liste, debut, fin) :
	pivot = liste[debut]
	gauche = debut+1
	droit = fin
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			gauche += 1
			droit -= 1
	liste[debut], liste[gauche-1] = liste[gauche-1], liste[debut]
	# on retourne la position finale du pivot :
	return gauche-1
	
	
	
def quicksort(liste) :
	def trirapide(d, f) :
		if d < f:
			indice_pivot = partitionDessusDessous(liste, d, f)
			trirapide(d, indice_pivot-1)
			trirapide(indice_pivot+1, f)
	trirapide(0, len(liste)-1)
 
		
L = [ randint(100, 999)  for _  in range(randint(5,15)) ]

print("Liste avant le tri : ", L)
quicksort(L)
print("Liste après le tri : ", L)

Les affichages choisis sont faits après chaque exécution de la fonction partition. On voit ainsi dans quel ordre les segments de listes sont traités.



from random import randint


def partitionDessusDessous(liste, debut, fin) :
	pivot = liste[debut]
	gauche = debut+1
	droit = fin
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			gauche += 1
			droit -= 1
	liste[debut], liste[gauche-1] = liste[gauche-1], liste[debut]
	# on retourne la position finale du pivot :
	return gauche-1
	
def affiche(liste, d, f, indice_pivot) :
	print()
	for x in liste :
		print(x, end=' ')
	print()
	for i in range(len(liste)) :
		if i == d :
			print('deb', end=' ')
		elif i == f :
			print('fin', end=' ')
		elif i == indice_pivot :
			print('piv',end=' ')
		else :
			print('   ', end=' ')
	print()
	for i in range(len(liste)) :
		if i == d and d == indice_pivot :
			print('piv', end=' ')
		elif i == f and f == indice_pivot :
			print('piv',end=' ')
		else :
			print('   ', end=' ')
	print()
	 
	print("*" * 4*len(liste))
	print()	
	
def quicksort(liste) :
	def trirapide(d, f) :
		if d < f:
			indice_pivot = partitionDessusDessous(liste, d, f)
			affiche(liste, d, f, indice_pivot)
			trirapide(d, indice_pivot-1)
			trirapide(indice_pivot+1, f)
	trirapide(0, len(liste)-1)
 
		
L = [ randint(100, 999)  for _  in range(randint(5,15)) ]

print("Liste avant le tri : ", L)
quicksort(L)
print("Liste après le tri : ", L)

On obtient par exemple : 

 
Liste avant le tri :  [211, 188, 283, 108, 499, 195, 701, 753, 116, 265, 424, 676, 981]

195 188 116 108 211 499 701 753 283 265 424 676 981 
deb             piv                             fin 
                                                    
****************************************************


108 188 116 195 211 499 701 753 283 265 424 676 981 
deb         fin                                     
            piv                                     
****************************************************


108 188 116 195 211 499 701 753 283 265 424 676 981 
deb     fin                                         
piv                                                 
****************************************************


108 116 188 195 211 499 701 753 283 265 424 676 981 
    deb fin                                         
        piv                                         
****************************************************


108 116 188 195 211 283 424 265 499 753 701 676 981 
                    deb         piv             fin 
                                                    
****************************************************


108 116 188 195 211 265 283 424 499 753 701 676 981 
                    deb piv fin                     
                                                    
****************************************************


108 116 188 195 211 265 283 424 499 676 701 753 981 
                                    deb     piv fin 
                                                    
****************************************************


108 116 188 195 211 265 283 424 499 676 701 753 981 
                                    deb fin         
                                    piv             
****************************************************

Liste après le tri :  [108, 116, 188, 195, 211, 265, 283, 424, 499, 676, 701, 753, 981]

 
Liste avant le tri :  [687, 467, 561, 907, 197]

197 467 561 687 907 
deb         piv fin 
                    
********************


197 467 561 687 907 
deb     fin         
piv                 
********************


197 467 561 687 907 
    deb fin         
    piv             
********************

Liste après le tri :  [197, 467, 561, 687, 907]

 
Liste avant le tri :  [329, 615, 615, 866, 258, 279, 826, 283, 292, 360, 884, 309, 911, 403]

279 309 292 283 258 329 826 866 615 360 884 615 911 403 
deb                 piv                             fin 
                                                        
********************************************************


258 279 292 283 309 329 826 866 615 360 884 615 911 403 
deb piv         fin                                     
                                                        
********************************************************


258 279 283 292 309 329 826 866 615 360 884 615 911 403 
        deb piv fin                                     
                                                        
********************************************************


258 279 283 292 309 329 615 403 615 360 826 884 911 866 
                        deb             piv         fin 
                                                        
********************************************************


258 279 283 292 309 329 360 403 615 615 826 884 911 866 
                        deb         fin                 
                                    piv                 
********************************************************


258 279 283 292 309 329 360 403 615 615 826 884 911 866 
                        deb     fin                     
                        piv                             
********************************************************


258 279 283 292 309 329 360 403 615 615 826 884 911 866 
                            deb fin                     
                            piv                         
********************************************************


258 279 283 292 309 329 360 403 615 615 826 866 884 911 
                                            deb piv fin 
                                                        
********************************************************

Liste après le tri :  [258, 279, 283, 292, 309, 329, 360, 403, 615, 615, 826, 866, 884, 911]

programmer.

Reprendre la version récursive du corrigé de l'exercice précédent. En donner une version non récursive.

  • un code possible

from random import randint
 
 

def partitionDessusDessous(liste, debut, fin) :
	pivot = liste[debut]
	gauche = debut+1
	droit = fin
	while gauche <= droit :
		while gauche <= droit and liste[gauche] <= pivot :
			gauche +=1
		while gauche <= droit and liste[droit] > pivot :
			droit -= 1
		if gauche < droit :
			liste[gauche], liste[droit] = liste[droit], liste[gauche]
			gauche += 1
			droit -= 1
	liste[debut], liste[gauche-1] = liste[gauche-1], liste[debut]
	# on retourne la position finale du pivot :
	return gauche-1



def quicksort(liste) :
	def trirapide(debut, fin):
		pile = [(debut, fin)]
		while pile != [] :
			d, f = pile.pop()
			indice_pivot = partitionDessusDessous(liste, d, f)
			if indice_pivot-1 > d : pile.append((d, indice_pivot-1)) 
			if indice_pivot+1 < f : pile.append((indice_pivot+1, f))
		
	trirapide(0, len(liste)-1)


L = [ randint(100, 999)  for _  in range(randint(5,15)) ]

print("Liste avant le tri : ", L)
quicksort(L)
print("Liste après le tri : ", L)