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