Understanding quick sort algorithm and its worst case

Question

i think i know quick sort algorithm.But i need help in figuring out its worst case.

Lets look at the below quicksort code---->

void quicksort(int arr[],int low,int high) //low and high are pased from main()
{
 int m;
 if(low<high)
 {
  m=partition(arr,low,high);
  quicksort(arr,low,m-1);
  quicksort(arr,m+1,high);
  }
}
int partition(int arr[],int low,int high)
{
 int pivot=arr[low],i=low,j=high;
 while(i<j)
 {
  while((arr[i]<=pivot)&&(i<=high))
  i++;
  while(arr[j]>pivot)
  j--;
  if(i<j)
  swap(arr,i,j);               //swaps arr[i]and arr[j]
 }
  swap(arr,low,j);             //swaps arr[low] and arr[j]
  return j;
}

I am not writing the definition of swap function here as it is self explanatory.

Now lets trace the above code for arr 1 2 3 4 5

0   4    0         partion swaps 1 with 1 and returns 0 which is assigned to m
low high m     
__________________________
0   0    *         
0   4    0
low high m
___________________________
0   0    * 
1   4    1         partition swaps 2 with 2
0   4    0
low high m
____________________________
2   4    2         partition swaps 3 with 3
1   4    1
0   4    0
low high m
____________________________
2   1    * 
2   4    2         
1   4    1
0   4    0
low high m
______________________________
3   4    3            partition swaps 4 with 4
2   4    2
1   4    1
0   4    0
low high m
________________________________
3   2    *
3   4    3
2   4    2
1   4    1
0   4    0
low high m
_________________________________
4   4    *
3   4    3
2   4    2
1   4    1
0   4    0
low high m
_________________________________
Stack empty
low high m

ques1.Is my understanding of quicksort correct?

ques2.In worst case , quicksort does n-1+n-2+.....+1 comparisons.How?

Here,i think it would have n+2 comparisons...instead of n-1. Partition would check

(1<=1,i++),(5>1,j--),
(2<=1,don't incr i),(4>1,j--),
(3>1,j--),
(2>1,j--),
(1>1,don't incr j)

total 7 i.e (n+2) comparisons

Answer 1

With algorithm you have shown, the pivot is always selected as the first element of the array. Just suppose you get an already ordered array, in that case the pivot will go to the first element (as it was) after comparing with it n-1 elements, and you will call quicksort recursively for two arrays, the first with the elements before the pivot (0 elements, an empty array) and the other with all elements after the pivot (n-1 elements). In that case, you'll get a recursive call to quicksort with an array of n-1 elements, that happens to be ordered again, and the first element (the new pivot) is going to produce an array of 0 elements (before the pivot), the pivot, and an array of n-2 elements. Do you follow the sequence?

As the worst case in your code happens precisely with an already ordered array, normally quicksort just gets the element in the middle as the pivot, so in that case it doesn't do anything also, but degenerating in half size arrays each time (well half the size minus one --the pivot).

In the case you get a degenerated situation like the previous, you get n comparisons in the first pass, then n-1 comparisons, then n-2, for a total of n*(n+1)/2 total of comparisons, and in the case you divide by two each time, you get n comparisons each pass for a total of log_2(n) passes, what makes a total of n*log_2(n) comparisons. Suppose n=1000000, that makes 1000001000000/2 = 200000500000 comparisons in the first case, in front of 20*1000000 = 20000000 (a lot less)