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.