Quicksort: Analysis

Exercise Based on your understanding of the "partitioning" process, what is the runtime of the partition subroutine?

Solution

It is $O(n)$; each element is visited once using the left and right pointers.

For the following theoretical considerations, assume the case where we select the pivot to be the right most element.

The quicksort runs in $O(n^{2})$ time in the worst case.

Exercise Complete the following statement.

  • The worst case is when the sequence values are already sorted (in ascending or descending order).

  • In this case, the partition algorithm will always select the (next) smallest/largest element, resulting in the most unbalanced split possible; two subsequences with ________ and ________ elements.

  • Repeated partitioning of this type will occur ________ times before both subsequences get down to size 1 or 0 subsequences (base-case)..

  • So there will be ________ calls made to the partition algorithm, which itself runs in $O(n)$ time.

  • So the total running time for the quicksort algorithm, in this case, is $O(n^{2})$.

Solution

  • The worst case is when the sequence values are already sorted (in ascending or descending order).

  • In this case, the partition algorithm will always select the (next) smallest/largest element, resulting in the most unbalanced split possible; two subsequences with $(n-1)$ and $0$ elements.

  • Repeated partitioning of this type will occur $O(n)$ times before both subsequences get down to size 1 or 0 subsequences (base-case)..

  • So there will be $O(n)$ calls made to the partition algorithm, which itself runs in $O(n)$ time.

  • So the total running time for the quicksort algorithm, in this case, is $O(n^{2})$.

Exercise In the worst-case, quicksort behaves like selection sort. True or false? Why?

Solution

True because each call to partition amounts to selecting the largest (or smallest) element from the subsequence passed to it.

The quicksort runs in $O(n \lg n)$ time in the best case.

Exercise Complete the following statement.

  • The best case is when the sequence values are not in sorted order. Instead the values are in a random order.

  • In this case, each recursive call to the quicksort algorithm divides the sequence into two subsequences of _______________ length.

  • Similar to binary search and merge sort, this repeated subdivision takes ________ steps to get down to size 1 or 0 subsequences (base-case).

  • So there will be ________ subsequences and that many calls to the partition algorithm which runs in $O(n)$ time.

  • So the total running time for the quicksort algorithm, in this case, is $O(n \lg n)$.

Solution

  • The best case is when the sequence values are not in sorted order. Instead the values are in a random order.

  • In this case, each recursive call to the quicksort algorithm divides the sequence into two subsequences of nearly equal length.

  • Similar to binary search and merge sort, this repeated subdivision takes $\lg n$ steps to get down to size 1 or 0 subsequences (base-case).

  • So there will be $O(\lg n)$ subsequences and that many calls to the partition algorithm which runs in $O(n)$ time.

  • So the total running time for the quicksort algorithm, in this case, is $O(n \log n)$.

The quicksort runs in $O(n \lg n)$ time in the average case.

The proof is beyond the scope of this course! Interested reader is referred to CLRS, section $7.2$, Performance of quicksort.

Resources