Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort - Coggle Diagram
Quicksort
Algorithm Efficiency:
Number of Key Comparisons
n + 1
if the scanning
indices cross over
n
if they coincide
If all the splits happen in the middle of corresponding subarrays, we will have the best case
Number of key comparisons in the
Best Case
Cbest(n) = 2Cbest(n/2) + n for n > 1, Cbest(1) = 0.
Number of key comparisons in the
Worst Case
Cworst(n) = (n + 1) + n + ... + 3 = [(n + 1)(n + 2)]/2- 3
Asymptotic Analysis
Best-Case:
Big Theta(n log2 n)
Worst-Case
Big Theta(n^2)
Divides the input according to their value
Partition Algorithm
Partition->
Is an arrangement of the array's elements that all elements to the left of some elemente 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.
A[0]...A[s-1]<=
A[s]
<=A[s+1]....A[n-1]
After a partition is achieved,
A[s]
will be in its final position in the
sorted array
Continue sorting the two subarrays to the left and to the
right of A[s] independently.
Start by selecting a pivot
Scan the subarray from both ends
Compare the subarray’s elements to the pivot
Left-to-right Scan
Skips over elements that are smaller than the pivot and stops upon encountering the first element greater than or equal to the pivot
The Scan search for elements smaller than the pivot to be in the left part of the subarray
Right-to-left Scan
Search for elements larger than the pivot to be in the right part of the subarray
The scan skips over elements that are larger than the pivot and stops on encoutering the first element smaller than or equal to the pivot
After both scans stops
If scanning indices i and j have not crossed
Exchange A[i] and A[j ] and resume the scans by incrementing i
and decrementing j, respectively
If the scanning indices have crossed over
we will have partitioned the
subarray after exchanging the pivot with A[j ]
If the scanning indices stop while pointing to the same element i = j
We have the
subarray partitioned, with the split position s = i = j