Challenge: Improving Quicksort

Solve the Improving Quicksort Problem.

We'll cover the following

The QuickSortQuickSort algorithm becomes slow when the input array contains many repeated elements. For example, when all elements in the input array are the same, the partition procedure splits the array into two parts, one empty part and the other part with n1n − 1 elements. Since QuickSortQuickSort spends ana \cdot n time to perform this partition, its overall running time is:

an+a(n1)+a(n2)+=an(n+1)2a \cdot n + a \cdot (n − 1) + a \cdot (n − 2) + \ldots = a \cdot \frac{n \cdot (n + 1)}{2}

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.