Tech: Comprendre le principe de l'algorithme Tri-Rapide:partionnement alternatif

Quicksort en action sur une liste

Le tri rapideest un algorithme de tri inventé par C.A.R. Hoare en 1961et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable.Le principe de l'algorithme est le suivant :

• Trouver le plus petit i tel que T[i] soit supérieur ou égal au pivot.
• Trouver le plus grand j tel que T[j] soit inférieur ou égal au pivot.
• Si i<j, échanger T[i] et T[j] puis recommencer.

Il est possible de formaliser cet algorithme de sorte qu'il soit linéaire :

partitionner(tableau T, premier, dernier, pivot)
     échanger T[pivot] et T[premier]
     i = premier + 1, j = dernier
     tant que i < j
         tant que i < j et T[i] < T[premier], faire i := i + 1
         tant que i < j et T[j] > T[premier], faire j := j - 1
         échanger T[i] et T[j]
         i := i + 1, j := j - 1
     fin tant que
     // le tableau est à présent en 3 parties 

consécutives : pivot, partie gauche, 

partie droite
     // dans partie gauche, tous les 

éléments sont <= pivot
     // dans partie droite, tous les 

éléments sont >= pivot
     // mais les deux parties peuvent 

se chevaucher : i-j peut être 0, 1 ou 2
     // il faut replacer le pivot entre 

les 2 parties et retourner l'indice du 

pivot : c'est assez compliqué...
     // il vaut mieux laisser le pivot à 

sa place au départ et le déplacer en cas

 de chevauchement :
     // voir l'algorithme classique 

à Wikipedia Quicksort en anglais

BY TAATJENE

Warning: Nous vous préconisons à plus de vigilance sur internet et mobile.En cas de doute Contacter Nous(traitement immédiat) .