Structure des données et algorithmes - Tri rapide

Le tri rapide est un algorithme de tri très efficace basé sur le partitionnement d'un tableau de données en tableaux plus petits. Un grand tableau est partitionné en deux tableaux dont l'un contient des valeurs inférieures à la valeur spécifiée, disons pivot, en fonction de laquelle la partition est créée et un autre tableau contient des valeurs supérieures à la valeur pivot.

Quicksort partitionne un tableau puis s'appelle lui-même deux fois de manière récursive pour trier les deux sous-tableaux résultants. Cet algorithme est assez efficace pour les ensembles de données de grande taille car sa complexité moyenne et dans le pire des cas sont respectivement O (n ² ).

Partition en tri rapide

La représentation animée suivante explique comment trouver la valeur de pivot dans un tableau.

La valeur pivot divise la liste en deux parties. Et récursivement, nous trouvons le pivot pour chaque sous-liste jusqu'à ce que toutes les listes contiennent un seul élément.

Algorithme de tri rapide de pivot

Sur la base de notre compréhension du partitionnement en tri rapide, nous allons maintenant essayer d'écrire un algorithme pour celui-ci, qui est le suivant.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Pseudocode du pivot de tri rapide

Le pseudocode de l'algorithme ci-dessus peut être dérivé comme -

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Algorithme de tri rapide

En utilisant un algorithme de pivot récursivement, nous nous retrouvons avec des partitions possibles plus petites. Chaque partition est ensuite traitée pour un tri rapide. Nous définissons l'algorithme récursif pour le tri rapide comme suit -

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Pseudocode de tri rapide

Pour en savoir plus, voyons le pseudocode de l'algorithme de tri rapide -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

Pour en savoir plus sur l'implémentation du tri rapide dans le langage de programmation C, veuillez cliquer ici .