Consider the following algorithm for sorting an array segment A[0..n-1]. In the

Question

Consider the following algorithm for sorting an array segment A[0..n-1]. In the first step the algorithm performs the bubble-up operation on the range [0..n-1] and it places the smallest item on position 0. In the second step it performs the bubble-down operation on the range [1..n-1] and it places the largest item on position n-1. In the third step it performs bubble-up operation on the range [1..n-2] and it places the second smallest item on position 1. In the fourth step it performs the bubble-down operation on the range [2..n-2] and it places the second largest item on position n-2. The algorithm continues alternating bubble-up and bubble-down operations until the range consists of a single field.

(i) What is the number of swap operations performed in the worse case? Explain.

(ii) What is the average number of swap operations performed by this algorithm? Explain.

Explanation / Answer

void BubbleUp(int a[],int l,int h)

{

for(int i=h-1;i>l;i--)

{

if(a[i]<a[i-1])

{ int temp=a[i]; a[i]=a[i-1]; a[i-1]=temp; }

}

void BubbleDown(int a[],int l,int h)

{

for(int i=l;i<h-1;i--)

{

if(a[i]>a[i+1])

{ int temp=a[i]; a[i]=a[i-1]; a[i-1]=temp; }

}

void BubbleSort(int a[],int n)

{

for(int i=0,h=n;i<n/2;i++,h--)

{

BubbleUp(a,i,h);

BubbleDown(a,i+1,h);

}

}

Using the above algorithm in program,

i) In worst case, the array will be arranged in decreasing order

For example 5 4 3 2 1

when i=0

n-1 swaps will be done by BubbleUp function .So the array will become 1 5 4 3 2

n-2 swaps will be done by BubbleDown function.So the array will become 1 4 3 2 5

Similarly,

when i=1

n-3 swaps will be done by BubbleUp function .So the array will become 1 2 4 3 5

n-4 swaps will be done by BubbleDown function.So the array will become 1 2 3 4 5

This will happen until i<n/2 and

In this manner, total no. of swaps performed = 1+2+3+.......+(n-1) = ((n-1)*n)/2

ii)

There are total n/2 steps performed. In every kth step, n-k(BubbleUp) and n-k-1(BubbleDown) = 2n-2k-1 swaps are performed. Average no.of swaps performed = Total No. of Swaps performed / Total no of steps =( n*(n-1)/2) /(n/2) =n-1 swaps

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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