Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Hoare partition
scan the array from both ends
If A[i] < p, increment i. If A[j] > p, decrement j.
When both scans stop, three situations may arise
complexity
n operations if i coincides with j
n + 1 basic operations if i crosses j
in the best case all splits happen in the middle
in the worst case one subarray is empty and the other is smaller by 1 unity
C(average)(n) = 1.39n log n
Pros
usually better than mergesort
space efficiency
Cons
not stable
divide and conquer
divides input elements according to their value
the entire work happens in the division stage
no work required to combine the solutions to the subproblems