CODEWITHSUNDEEP
algorithmdata-structures
Amna Shahbaz
Amna Shahbaz

Reputation: 57

Average Case of Quick Sort

I'm working on the program just needed in the following to understand it better.

What is the average case running time for Quick sort and what may cause this average case performance? How can we modify quick sort program to mitigate this problem?

I know that it has average case O(n log(n)) and I know it occurs when the pivot median element. My question is how can I modify the program to mitigate this problem.

Upvotes: 2

Views: 7768

Answers (1)

kaya3
kaya3

Reputation: 51152

The average case of quicksort is not when the pivot is the median element - that's the best case. Analyzing the average case is a bit tricker. We'll assume that the array is in a random order, so that each element is equally likely to be selected as the pivot. Alternatively, we can just select the pivot randomly so that the original array order doesn't matter; either way leads to the same conclusion.

If the numbers in the array are [1, 2, 3, 4, 5], for example, then each number has a 1/5 probability of being selected as the pivot.

  • If 1 is selected as the pivot, then the recursive calls are on arrays of size 0 and 4.
  • If 2 is the pivot, then the recursive calls are on arrays of size 1 and 3.
  • If 3 is the pivot, then we will make recursive calls on arrays of size 2 and 2.
  • If 4 is the pivot, then the recursive calls are on arrays of size 3 and 1.
  • If 5 is selected as the pivot, then the recursive calls are on arrays of size 4 and 0.

So the recurrence is that T(5) is 1/5 of T(4) + T(0), T(3) + T(1), T(2) + T(2), T(1) + T(3) and T(0) + T(4), plus an O(n) term for the cost of partitioning. The general form of this recurrence relation is a sum over every possible pivot, divided by the number of possible pivots:

recurrence relation

The solution to this recurrence relation happens to be that T(n) is in O(n log n).

The fact that the quicksort algorithm runs in O(n log n) time in the average case is not a problem; in fact, this is asymptotically optimal for any comparison-based sorting algorithm. No comparison-based sorting algorithm can have a better asymptotic running time in the average case.

Upvotes: 6

Related Questions