Consider an array of size eight with the numbers 30, 40, 80, 70, 10, 20, 50, 60. Assume you execute quicksort using the version of partition from class and from CLRS. Note that in this algorithm an element might exchange with itself (which counts as one exchange). (a) Show the array after the first partition. How many comparisons are used? How many exchanges?

There are 6 comparisons in total.

There are 6 exchanges in total.

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.