Worst case of the Quicksort algorithm

Question

I found many implementations of quick sort algorithm, but at the end I decided to stick to this one:

public static void quickSort(int array[], int start, int end)
        {
            if(end <= start || start >= end) { 

            } else {
            int pivot = array[start];
            int temp = 0 ;
            int i = start+1;

            for(int j = 1; j <= end; j++)  { 
                if(pivot > array[j]) { 
                    temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                    i++;
                }

            }
            array[start] = array[i-1];
            array[i-1] = pivot;
            quickSort(array, start, i-2);
            quickSort(array, i, end);
        }} 

There are several things I'm confused about.
Why some people suggest taking the first element as a pivot point, others tell to pick the middle element and some will tell that you should pick the last element as your pivot point, wouldn't it be different?
Let's say I'm trying to show why if the array is sorted quick sort will have O(n^2) as the worst case order of growth.
I have the following array:
{1, 2, 3, 4, 5, 6}.
If I pick the first element as my pivot element, would it not compare it to every other element and then will just swap it with itself and will be just O(n)? Then it will proceed further to two lines which are O(logn)

quickSort(array, start, i-2);
quickSort(array, i, end);

So at the end, even if it is an ordered list of integers, it will still be O(nlogn)?

If I decided to pick my last element as my pivot element, would it not be completely different? It will be swapping 6 and 1 and hence it will be doing the operations that are completely different compared to when the pivot element was the first element in the array.

I just don't understand why the worst case is O(n^2).

Any help will be greatly appreciated!

Answer 1

The whole point of Quicksort is to find a pivot that partitions the array into two approximately equal pieces. That's where you get the log(n) from.

Suppose there is an array of size n and at each iteration you can partition the array into equal parts. Then we have:

T(n) = 2 * T(n / 2) + O(n)
     = 4 * T(n/4) + 2 * O(n)
.
.
(log(n) steps)
.
.
    = 2^log(n) * T(1) + log(n) * O(n)
    = n * O(1) + O(n * log(n))
    = O(n * log(n))

Now, if we partition the array into sizes say 1 and n-1, we get:

T(n) = T(1) + T(n-1) + O(n) = T(n-1) + O(n)
     = T(n-2) + O(n-1) + O(n)
     = T(n-3) + O(n-2) + O(n-1) + O(n)
.
.
(n-1) steps
.
.
    = T(1) + O(2) + O(3) + ... + O(n)
    = O(1 + 2 + 3 + .... + n)
    = O(n^2)

In the case that you mention, both of the following will not individually be O(log(n)). One will be O(1) and the other will be T(n-1) if the array is sorted. Hence you would get the O(n^2) complexity.

quickSort(array, start, i-2); // should be constant time
quickSort(array, i, end); // should be T(n-1)

And as @MarkRansom mentions below, this is not exclusive to sorted arrays. In general, if you choose pivots in such a way that the array is very unevenly partitioned, you'll run into such worst-case complexities. For example, if the array is not sorted but you always choose the maximum (or minimum depending upon your implementation) for the pivot, you'll run into the same problem.