Question

Trace the partition function provided for the array A = {27, 38, 12, 39, 27, 16}. After each iteration of the loop check that the invariant is true.

int partition(int A[], int first, int last) {

// Take A[first] as the item to be placed in correct

// sorted order. Set pivotIndex to that item and return it.

  

int p= A[first]; // Initialisation to satisfy the invariant.

int LastS1= first;

int FirstUnknown= first + 1;

int temp;

while (FirstUnknown <= last) {

// INVARIANT: The items in myArray[first+1..LastS1]

// are all strictly less than p,

// and the items in myArray[LastS1+1.. FirstUnknown-1] are at least p.

if (A[FirstUnknown] < p) { // Case: need to add to S1

LastS1++; // Increment LastS1

temp= A[FirstUnknown];

A[FirstUnknown]= A[LastS1];

A[LastS1]= temp;

FirstUnknown++;

}

else {

FirstUnknown++;

} // Case: Need to add to S2

}

temp= A[first];

A[first]= A[LastS1];

A[LastS1]= temp;

FirstUnknown++;

return LastS1;

}

Answer 1

first in this code

array a[]={27,38,12,39,27,16}

variables are

initially

FirstUnknown =1

p=0

LastS1=0

FirstUnknown	P		LastS1	a[FirstUnknown]	a[LastS1]	array
1	27		0	38	27	27,38,12,39,27,16
2	27		0	12	27	27,38,12,39,27,16
3	27		1	39	12	27,12,38,39,27,16
4	27		1	27	12	27,12,38,39,27,16
5	27		1	16	12	27,12,38,39,27,16
6	27		2	-	16	27,12,16,39,27,38

now its change

first and LastS1

so that a[first]=a[LastS1]

so that a[first]=16

and a[LastS1]=27

the sequence is 16,12,27,39,27,38.

SUMMERY:

code is goto first to last element of array

then check a[Firstunknown] < (p=a[first])

if condition satisfy then do LastS1++; and change value of LastS1 and FirstUnknown while end of the array

at last changed value of LastS1 and First element.

please like,

comment if you have any query.