CPGE Oujda Spé

Tri (quicksort)

Le tri rapide (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner.

La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique. Malgré ce désavantage théorique, c'est en pratique un des tris les plus rapides, et donc un des plus utilisés. Le tri rapide ne peut cependant pas tirer avantage du fait que l'entrée est déjà presque triée. Dans ce cas particulier, il est plus avantageux d'utiliser le tri par insertion

Description de l'algorithme

La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui sont inférieurs au pivot soient à sa gauche et que tous ceux qui sont supérieurs au pivot soient à sa droite.

Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement, jusqu'à ce que l'ensemble des éléments soit trié.

Concrètement, pour partitioner un sous-tableau :

• on place le pivot à la fin (arbitrairement), en l'échangeant avec le dernier élément du sous-tableau ;
• on place tous les éléments inférieurs au pivot en début du sous-tableau ;
• on place le pivot à la fin des éléments déplacés.
• Illustration de l'algorithme de tri rapide (Quicksort).

Autre Exemple :

• Soit la liste :
• L = [ 4, 23, 3, 42, 2, 14, 45, 18, 38, 16 ]
• Prenons comme pivot la dernière valeur
• pivot = 16
• Nous obtenons donc :
  L1 = [4, 14, 3, 2]
• L2 = [23, 45, 18, 38, 42]
• A cette étape voici l'arrangement de L :
  L = L1 + pivot + L2  = [4, 14, 3, 2, 16, 23, 45, 18, 38, 42]

Solution récursive avec fonction unique

def Trirapide(L) :

Solution avec partitionnement :

def partitionner(T,premier,dernier) :

def triRapide(T,premier,dernier) :

Choix du pivot et complexité

Pivot arbitraire

Une manière simple de choisir le pivot est de prendre toujours le premier élément du sous-tableau courant (ou le dernier).la complexité moyenne du tri rapide en sélectionnant le pivot de cette façon est Θ(n log n). Cependant, la complexité dans le pire cas est Θ(n²).

Si on prend comme pivot le milieu du tableau, le résultat est identique.

Pivot aléatoire

Si on utilise la méthode donnée dans la description de l'algorithme, c'est-à-dire choisir le pivot aléatoirement, alors la complexité moyenne du tri rapide est Θ(n log n) sur n'importe quelle entrée. Dans le pire cas, la complexité est Θ(n²). Néanmoins, l'écart type de la complexité est seulement Θ(n), ce qui signifie que l'algorithme s'écarte peu du temps d'exécution moyen.

Dans le meilleur cas, l'algorithme est en Θ(n log n).

Pivot optimal

En théorie, on pourrait faire en sorte que la complexité de l'algorithme soit Θ(n log n) dans le pire cas en prenant comme pivot la valeur médiane du sous-tableau. L'algorithme BFPRT ou médiane des médianes permet en effet de calculer cette médiane de façon déterministe en temps linéaire. Mais l'algorithme n'est pas suffisamment efficace dans la pratique, et cette variante est peu utilisée.

(En théorie des probabilités et en statistiques, une médiane d'un ensemble de valeurs (échantillon, population, distribution de probabilités) est une valeur m qui permet de couper l'ensemble des valeurs en deux parties égales : mettant d'un côté une moitié des valeurs, qui sont toutes inférieures ou égales à m et de l'autre côté l'autre moitié des valeurs, qui sont toutes supérieures ou égales à m (s'il y a un nombre impair de valeurs, la valeur centrale sera mise des deux côtés). Intuitivement, on peut dire que la médiane est le point milieu de l'ensemble¹, qu'elle divise en deux moitiés. C'est une caractéristique de position de la série. On peut déterminer une médiane pour un ensemble de valeurs non numériques¹ pour autant qu'on puisse choisir un critère d'ordonnancement de ces valeurs.)

Complexit´e du tri rapide(calcul mathématique)

L’´etude math´ematique est en section suivante @[Complexit´es du tri rapide].

Pour calculer la complexit´e de l’algorithme du tri rapide on part de la d´efinition r´e- cursive du tri rapide. Soit C (T ) le nombre de comparaisons pour trier un tableau T et soit P (T ) le nombre de comparaisons pour partitionner T selon le pivot. Si la partition r´epartit les ´el´ements dans deux tableaux T₁ et T₂, on obtient :

C (T ) = P (T ) + C (T₁) + C (T₂)

Si T est de taille n, le nombre de comparaisons pour r´ealiser la partition ne peut ˆetre plus petit que n − 1 (il faut comparer chacun des autres ´el´ements au pivot pour d´ecider du sous-tableau dans lequel il doit se trouver). On supposera donc que P (T ) = n − 1. Dans l’algorithme partitionner, le nombre de comparaisons pour partitionner un tableau de taille n peut aller jusqu’`a n + 1 mais cela ne change pas l’ordre de grandeur du r´esultat final.

Mais pour ce qui est de la place du pivot, et donc des tailles de T₁ et T₂, la situation est tr`es variable :

1. Si le pivot est le plus petit (ou plus grand) ´el´ement du tableau, l’un des deux tableaux de la partition aura une taille nulle et l’autre aura une taille de n − 1.

2. Si le pivot est l’´el´ement m´edian, les deux tableaux T₁ et T₂ auront pour taille

(environ) la moiti´e de n.

3. En g´en´eral si la place du pivot est k, il reste `a traiter r´ecursivement un tableau de taille k − 1 et un tableau de taille n − k.

Complexit´e au pire Le premier cas est le pire des cas possibles (et il se produit

lorsque le tableau initial est tri´e – en ordre croissant ou d´ecroissant). Dans ce cas, pour

un tableau de taille n, le nombre de comparaison pour trier est :

C_max(n) = n − 1 + C_max(n − 1)

Et avec le cas initial C_max(1) = 0, la r´ecurrence se r´esout en :

C_max(n) = n(n − 1)/2 = O(n²)

Complexit´e au meilleur Le second cas est le meilleur des cas possibles. En effet,

s’il se r´ep`ete `a toutes les ´etapes r´ecursives, on a finalement pour le nombre minimal de comparaisons pour trier un tableau de taille n :

C_min(n) = n − 1 + C_min(bn/2c) + C_min(dn/2e)

Et avec le cas initial C_min(1) = 0, cette r´ecurrence se r´esout en :

C_min(n) ∼ n lg n = Ω(n lg n)

La r´esolution de cette r´ecurrence donne :

C_moy (n) ∼ 2n lg n = Θ(n lg n)

Conclusion

Ainsi la complexit´e moyenne du tri rapide est en Θ(n lg n). Par exemple pour un tableau d’un million d’´el´ements, le tri par insertion n´ecessite de un milliard de comparai- sons en moyenne alors que le tri rapide n’en fera en moyenne qu’une vingtaine de millions (10⁶ ≈ 2²⁰ donc lg 10⁶ ≈ 20).

_{Toutefois dans le pire cas, le tri rapide est en O(n}²_{). Et cela est d’autant plus gˆenant}

que ce cas apparaˆıt pour des tableaux tri´es. Il existe cependant plusieurs parades pour

´eviter le cas le pire, en faisant en sorte que le pivot se place toujours dans la r´egion m´ediane du tableau pour avoir un tri en temps proportionnel `a n lg n (voir plus loin

@[Rendre le tri rapide efficace]).

Le tri rapide est consid´er´e en g´en´eral comme le tri le plus efficace et c’est par exemple

le tri utilis´e dans la plupart des syst`emes d’exploitation.

Solution1 :

partitionner(tableau T, premier, dernier, pivot)

échanger T[pivot] et T[dernier]

j := premier

pour i de premier à dernier - 1

si T[i] <= T[dernier] alors

échanger T[i] et T[j]

j := j + 1

échanger T[dernier] et T[j]

renvoyer j

tri_rapide(tableau t, entier premier, entier dernier)

début

si premier < dernier alors

pivot := choix_pivot(t, premier, dernier)

pivot := partitionner(t, premier, dernier, pivot)

tri_rapide(t ,premier, pivot-1)

tri_rapide(t, pivot+1, dernier)

fin si

fin

Solution recurive avec fonction unique

def Trirapide(L) :

if L == [ ] :

return [ ]

else :

n = len(L)-1 #on va balayer la liste L et r_epartir les valeurs

L1 = [ ]

L2 = [ ]

for k in range(1,n+1) :

if L[k]<=L[0] :

L1.append(L[k]) #L1 re_coit les _el_ements plus petits

else :

L2.append(L[k]) #L2 re_coit les _el_ements plus grands

L = Trirapide(L1)+[L[0]]+Trirapide(L2)

return L

Exemple :

>>>T=Trirapide([10,39,21,2,8,6,1])

>>>print(T) vaut [1; 2; 6; 8; 10; 21; 39]

Solution 3 avec partitionnement :

def partitionner(T,premier,dernier) :

p=T[dernier]

j=premier

for i in range(premier,dernier) :

if T[i]<=p :

T[i],T[j]=T[j],T[i]

j=j+1

T[dernier],T[j]=T[j],T[dernier]

return j

def triRapide(T,premier,dernier) :

if premier < dernier :

pivot=partitionner(T,premier,dernier)

triRapide(T,premier,pivot-1)

triRapide(T,pivot+1,dernier)