1. Jan 4, 2012

### pc2-brazil

Good evening,

I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm.
Every source about this subject seems to agree that the worst case scenario is when the list to be sorted is already sorted and the pivot is the smaller element on the list. In this case, the total number of comparisons is n(n - 1)/2, where n is the number of items in the list
But it seems to me that the worst case happens when the list is sorted in decreasing order and the pivot is the first element in the list, which, in this case, would be the greatest element on the list.
For example, consider the list {4, 3, 2, 1}. I will chose the pivot as the first element. Each step of the quicksort will divide the original list as follows:

In the first step, {4, 3, 2, 1} is divided into two lists: {3, 2, 1, 4} (elements smaller than the pivot plus the pivot appended in the end) and {} (elements greater than the pivot: empty list). The first step requires 3 comparisons to find that 3, 2, 1 are smaller than 4.
Similarly, in the second step, the list {3, 2, 1, 4} is divided into {2, 1, 3} and {4}, requiring 3 comparisons (to find that 2, 1 are smaller than 3 and 4 is greater than 3).
The third step divides {2, 1, 3} into {1, 2} and {3}, requiring 2 comparisons.
The last step divides {1, 2} into {1} and {2}, requiring 1 comparison.
If I sum the number of comparisons for each step, I find 3 + 3 + 2 + 1 = 9.
In fact, if I generalize the above situation to n elements sorted in decreasing order, with the first element as the pivot, I get n(n - 1)/2 + n - 1 comparisons.

If I chose the pivot to be the smaller element on the list, and the list were sorted {1, 2, 3, 4}, the number of comparisons would be n(n - 1)/2 = 4(3)/2 = 6.

9 comparisons is greater than 6 comparisons. Why isn't it the worst case?

2. Jan 5, 2012

### AlephZero

There is a different way of thinking about at this. The worst choice of a pivot element splits a list of length n into lists of length 1 and n-1.

This will happen if the pivot is either the smallest element or the largest element in the list.

In practice, there are several ways to select the pivot element to avoid the the problem that sorting an already-sorted list is slow. For example you can select the element at a random position in the list, not the first or last element. Or you can select say 3 different elements at random positions in the list, and choose the middle-sized one as the pivot.

3. Jan 5, 2012

### pc2-brazil

The choice that I made to sort the list in decreasing order and choose the largest element as the pivot split the original list into lists of length 0 and n (because there is no element larger than the first element, so the second sublist at the first step is empty). It made necessary a larger number of comparisons than if the list was split in lists of length 1 and n-1.
Why isn't this approach taken as the worst case? Is there any restriction that makes this approach incorrect?