Question

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisons made. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort.

Answer 1

Program in C:

a)

#include<stdio.h>

void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);

int main()
{
   int a[30],n,i;
   printf("Enter no of elements:");
   scanf("%d",&n);
   printf("Enter array elements:");
  
   for(i=0;i<n;i++)
       scanf("%d",&a[i]);
      
   mergesort(a,0,n-1);
  
   printf("\nSorted array is :");
   for(i=0;i<n;i++)
       printf("%d ",a[i]);
      
   return 0;
}

void mergesort(int a[],int i,int j)
{
   int mid;
      
   if(i<j)
   {
       mid=(i+j)/2;
       mergesort(a,i,mid);       //left recursion
       mergesort(a,mid+1,j);   //right recursion
       merge(a,i,mid,mid+1,j);   //merging of two sorted sub-arrays
   }
}

void merge(int a[],int i1,int j1,int i2,int j2)
{
   int temp[50];   //array used for merging
   int i,j,k;
   i=i1;   //beginning of the first list
   j=i2;   //beginning of the second list
   k=0;
  
   while(i<=j1 && j<=j2)   //while elements in both lists
   {
       if(a[i]<a[j])
           temp[k++]=a[i++];
       else
           temp[k++]=a[j++];
   }
  
   while(i<=j1)   //copy remaining elements of the first list
       temp[k++]=a[i++];
      
   while(j<=j2)   //copy remaining elements of the second list
       temp[k++]=a[j++];
      
   //Transfer elements from temp[] back to a[]
   for(i=i1,j=0;i<=j2;i++,j++)
       a[i]=temp[j];
}

output:

Enter no of elements:9                                                                                                

Enter array elements:5 13 2 25 7 17 20 8 4                                                                            

                                                                                                                      

Sorted array is :2 4 5 7 8 13 17 20 25                                                                                

                                                                                                                      

...Program finished with exit code 0