Answer:
There are 6 comparisons in total.
There are 6 exchanges in total.
Step-by-step explanation:
In Partition algorithm, we will choose last element as pivot element.
Partition algorithm is as follows which works on Arr[low...high]
PARTITION(Arr, low, high)
x=Arr[high]
i=low-1
for j from low to high-1
if Arr[j] <= x
i=i+1
exchange/swap (Arr[i] and Arr[j])
exchange/swap(Arr[i+1] and A[r] )
return i+1
For the given array Arr={30,40,80,70,10,20,50,60}
Apply partition algorithm: low=0, high=8-1=7
x=Arr[7]=60
i=-1
Now , a loop will run for j=0 to 6
for j=0 :
Arr[0]=30 and 30<60
i=-1+1=0
So, exchange Arr[0] and Arr[0]
Arr remains same,={30,40,80,70,10,20,50,60} but 1 exchange occurs here
for j=1
Arr[1]=40 and 40<60
i=0+1=1
So, exchange Arr[1] with Arr[1]
again Arr remains same ={30,40,80,70,10,20,50,60}
But 1 exchange also occurs here
for j=2
Arr[2]=80
and 80>60
for j=3
Arr[3]=70
and 70>60
for j=4
Arr[4]=10 and 10<60
i=1+1=2
so exchange Arr[4] and Arr[2]
Arr becomes ={30,40,10,70,80,20,50,60}
1 exchange occurs here
for j=5
Arr[5]=20 and 20<60
i=2+1=3
so exchange Arr[5] and Arr[3]
Arr becomes={30,40,10,20,80,70,50,60}
1 exchange occurs here
for j=6
Arr[6]=50 and 50<60
i=3+1=4
so exchange Arr[6] and Arr[4]
Arr becomes={30,40,10,20,50,70,80,60}
1 exchange occurs here
Now, loop ends here
exchange Arr[i+1] and Arr[high] that means Arr[5] and Arr[7]
1 exchange occurs here
Arr becomes={30,40,10,20,50,60,80,70}
This is array after first partition
There are comparisons for all j between Arr[j] and x in above procedure
It means there are 6 comparisons in total.
If we count total exchanges above, we get 6 exchanges in total.