DAA - Tri rapide

Il est utilisé sur le principe de diviser pour conquérir. Le tri rapide est un algorithme de choix dans de nombreuses situations car il n'est pas difficile à mettre en œuvre. C'est un bon tri à usage général et il consomme relativement moins de ressources lors de l'exécution.

Avantages

  • Il est en place car il n'utilise qu'une petite pile auxiliaire.

  • Il ne nécessite que n (log n) il est temps de trier n articles.

  • Il a une boucle intérieure extrêmement courte.

  • Cet algorithme a été soumis à une analyse mathématique approfondie, une déclaration très précise peut être faite sur les problèmes de performances.

Désavantages

  • C'est récursif. Surtout, si la récursivité n'est pas disponible, la mise en œuvre est extrêmement compliquée.

  • Il nécessite un temps quadratique (c'est-à-dire n2) dans le pire des cas.

  • Il est fragile, c'est-à-dire qu'une simple erreur de mise en œuvre peut passer inaperçue et entraîner de mauvaises performances.

Le tri rapide fonctionne en partitionnant un tableau donné A[p ... r] en deux sous-tableaux non vides A[p ... q] et A[q+1 ... r] de telle sorte que chaque clé dans A[p ... q] est inférieur ou égal à chaque clé dans A[q+1 ... r].

Ensuite, les deux sous-tableaux sont triés par des appels récursifs au tri rapide. La position exacte de la partition dépend du tableau et de l'index donnésq est calculé dans le cadre de la procédure de partitionnement.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Notez que pour trier le tableau entier, l'appel initial doit être Quick-Sort (A, 1, length[A])

Dans un premier temps, le tri rapide choisit l'un des éléments du tableau à trier comme pivot. Ensuite, le tableau est partitionné de chaque côté du pivot. Les éléments inférieurs ou égaux à pivot se déplaceront vers la gauche, tandis que les éléments supérieurs ou égaux à pivot se déplaceront vers la droite.

Partitionner le tableau

La procédure de partitionnement réorganise les sous-matrices sur place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Une analyse

Le pire des cas de complexité de l'algorithme de tri rapide est O(n2). Cependant en utilisant cette technique, dans les cas moyens, nous obtenons généralement la sortie enO(n log n) temps.