For the following two questions, determine the pivot value as a median of the le

Question

For the following two questions, determine the pivot value as a median of the leftmost, rightmost and the middle elements of your array. Assume that the function PARTITION starts with exchanging this median element with the rightmost element of the given array. The rest of the pseudocode of the QUICKSORT and PARTITION functions will be the same.

1. (a) Show exactly the progress of the QUICKSORT algorithm with the median-of-3 partition described above for the array: <1, 2, 3, 4, 5, 6, 7>.

(b) Show exactly the progress of the QUICKSORT algorithm with the median-of-3 partition described above for the array: <7, 6, 5, 4, 3, 2, 1>.

Explanation / Answer

Algorithm Quicksort {

a[1:n] ;

low = 1; high = n;

if(low <high) {

k: = Partition(a,low,high);

Quicksort(low,k-1);

Quicksort(k+1,high);

}

}

Algorithm Partition(a,low,high) {

pivot = a[1]+a[4]+a[7]/3;

swap(pivot,high);

lb = low;

ub =high;

while(lb<=ub) {

while(a[lb] <= pivot && lb<=ub) {

lb = lb +1;

while(a[ub] > pivot) {

ub = ub -1;

swap (a,lb,ub);

a[low] = a[ub];

a[lb] = pivot;

return ub;

} }

}   }   }

n = 7

low =1 high = 7

if(1<7)

k = Partition(a,1,7)

pivot = 1+4+7/3 = 4

swap(4,7);

{1,2,3,7,5,6,4}

Pivot = 4

lb=1;

ub=7;

while(1<=7)

while(a[1] < = 4)

lb = 2;

while(a[7] >4)

ub = 7

while(a[2] <=4)

lb =3

while(a[7]>4)

ub = 7

while(a[3]< = 4)

lb =4

while(a[7] > 4)

ub = 7

while(a[4] <=4)

lb =4

while(a[7]>4)

ub = 7

if(4<7)

swap(a,4,7);

{1,2,3,4,5,6,7};

n = 7

low =1 high = 7

if(1<7)

k = Partition(a,1,7)

pivot = 7+4+1/3 = 4

swap(4,7);

{7,6,5,1,3,2,4}

Pivot = 4

lb=1;

ub=7;

while(1<=7)

while(a[1] < = 4)

lb = 1;

while(a[7] >4)

ub = 7

if(1<7)

swap(a,1,7)

{4,6,5,1,3,2,7}

while(a[1] <=4)

lb=2

while(a[7]>4)

ub = 6

if(2<6)

swap(a,2,6)

{4,2,5,1,3,6,7}

while(2<=6)

while(a[2]<=4)

lb= 3

while(a[6]>4)

ub =5

if(3<5)

swap(a,3,5)

{4,2,3, 1,5,6,7}

While(3<=5)

While(a[3] <=4)

Lb =4

While(a[5]>4)

Ub = 4

If(4<4)

a[o] =a[4]=1

a[4] = 1

k =4

Quicksort(1,4)

Quicksort(5,7)

Continue partition process

We get,

{1,2,3,4,5,6,7}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.