Answer:
Quick Sort is a Divide and Conquer algorithm which picks an element as a pivot which divide the array into two halves.
Sorted Array -2 | 0 | 1| 3| 4| 5 | 6| 7 | 8| 9 |10 | 12 |14| now array is sorted
Time Complexity of Quick Sort = = O ( n log n )
asymptotic notation using master theorem = T(n) = aT (n/b) + θ ( n^k log^p n)
Explanation:
Quick Sort is a Divide and Conquer algorithm which picks an element as a pivot which divide the array into two halves. There are many types of Quick Sort as
- Pick the first element as pivot
- pick the last element
- pick random element
- pick median element
3 | 4 | -2 | 8 | 10 | 5 | 0 | 7 | 12 | 14 | 9 | 6 | 8 |1 | 5 //5 as a pivot
-2 | 3 | 4| 8| 5| 0| 7 |10 |12| 14 | 9 | 6 | 1| 5| 8 //8 as pivot
-2 | 0 | 1| 3| 4| 5 | 6| 7 | 8| 9 |10 | 12 |14| now array is sorted
here pick a point as initial values first pick 5 as pivot then compare the 5<values if it id true then swap it of it is false move towards next and check the condition. Similarly half array is sorted pick 8 as pivot point then do the same procedure and sort the other half array.
Time Complexity of Quick Sort
T(n) =a
= 2T(n/2) + n
= 2( 2T (n/4) + n/2) + n
= 2² T (n/2²) +n +n
= 2² (2t(n/2³)+n/4 ) +n +n
= 2³T (n/2³) + n +n +n
= 2^k T ( n/ 2^k) + nk
= nT( n/n ) + n log n
= na + n log n
= O ( n log n )
asymptotic notation using master theorem.
T(n) = aT (n/b) + θ ( n^k log^p n)
a = number in the recursion and a >= 1
n/b = size of each sub problem
b > 1, k >= 0 and p is a real number.
