Use Quicksort algorithm to sort the following list of random numbers. Show all steps. Derive the time complexity of Quicksort and find the asymptotic notation using master theorem.
3 | 4 | -2 | 8 | 10 | 5 | 0 | 7 | 12 | 14 | 9 | 6 | 8 |1 | 5

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

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.