0
7.4kviews
Sort the following numbers using Quick sort. Also derive the time complexity of quick sort. 50, 31, 71, 38, 77, 81, 12, 33
1 Answer
0
353views

We have set a pivot for the given numbers by which we can apply quick sort algorithm. enter image description here

Hence after applying the quick sort technique the sorted numbers are 12, 31, 33, 38, 50, 71, 77, 81.

Complexity of Quick Sort

  1. Worst-case: O(N2)

This happens when the pivot is the smallest (or the largest) element.

Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.

  1. Best-case O(NlogN)

The best case is when the pivot is the median of the array, and then the left and the right part will have same size.

There are logN partitions, and to obtain each partitions we do N comparisons (and not more than N/2 swaps). Hence the complexity is O(NlogN)

  1. Average-case - O(NlogN)
Please log in to add an answer.