Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort, Quicksort(A[l..s − 1]), p ← A[l], repeat i ← i + 1 until A[i] ≥…
Quicksort
-
After a partition is achieved, A[s] will be in its final position in the sorted array, and we can continue sorting the two subarrays to the left and to the right of A[s] independently (e.g., by the same method).
Note the difference with mergesort: there, the division of the problem into two subproblems is immediate and the entire work happens in combining their solutions;
Here, the entire work happens in the division stage, with no work required to combine the solutions to
the subproblems.
As a partition algorithm, we can certainly use the Lomuto partition.
Alternatively, we can partition A[0..n − 1] and, more generally, its subarray Al..r by the more sophisticated method suggested by C.A.R. Hoare, who invented quicksort
As before, we start by selecting a pivot—an element with respect to whose value we are going to divide the subarray.
-
-
-
Unlike mergesort, which divides its input elements according to their position in the array, quicksort divides them according to their value.
A partition is an arrangement of the array’s elements so that all the elements to the left of some element A[s] are less than or equal to A[s], and all the elements to the right of A[s] are greater than or equal to it.
-
-
-
-
-
-
-
-
swap(A[i], A[j]) //undo last swap when i ≥ j
-
-