inspire_all -4 Newbie Poster

Hello everyone,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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.