Méthode de partition

Question

J'essaie de comprendre exactement ce que cette méthode fait, il est supposé "Continuez à échanger les paires les plus à l'extérieur les plus mal positionnées". Je mets cela dans un programme et essayé différents choix, mais le résultat n'a pas de sens pour moi, qu'est-ce exactement ce faire

partition(A, p) 
A: array of size n, p: integer s.t. 0 <= p < n 

1. swap(A[0],A[p]) 

2. i <- 1, j <- n − 1 

3. while i < j do 

4. while A[i] <= A[0] and i < n do 

5.  i <- i + 1 

6. while A[j] > A[0] and j > 0 do 

7.  j <- j − 1 

8. if i < j then 

9.  swap(A[i], A[j]) 

10. swap(A[0], A[j]) 

11. return j 

Answer 1

L'algorithme est ce pseudo-code met en œuvre la phase de partitionnement du quicksort sorting algorithm. Il arrangera le tableau de sorte que toutes les valeurs inférieures ou égales à A[p] soient à gauche et toutes les plus grandes valeurs à droite. Il renvoie l'index j qui est le dernier index du côté gauche pour lequel A[j] est égal à A[p]. Si vous n'êtes pas familiarisé avec quicksort, l'intention est d'utiliser cet algorithme de partition pour diviser le tableau en "petites" et "grandes" parties et trier récursivement chaque partie. Puisque les petits avaient été arrangés pour venir avant les grands dans le tableau, le tableau est trié. Si p est sélectionné de manière appropriée pour que A[p] soit proche du milieu des valeurs de A, il s'agit d'une méthode de tri très rapide.