Design and Analysis of Algorithm Lab

Experiment No.

WAP to sort an array using heap sort technique:

#include<stdio.h>

void create(int [ ]);
void down_adjust(int [ ],int);

void main()
{
int heap[30],n,i,last,temp;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=1;i<=n;i++)
scanf("%d",&heap[i]);

//create a heap
heap[0]=n;
create(heap);

//sorting
while(heap[0] > 1)
{
//swap heap[1] and heap[last]
last=heap[0];
temp=heap[1];
heap[1]=heap[last];
heap[last]=temp;
heap[0]--;
down_adjust(heap,1);
}

//print sorted data
printf("\nArray after sorting:\n");
for(i=1;i<=n;i++)
printf("%d ",heap[i]);
}

void create(int heap[ ])
{
int i,n;
n=heap[0]; //no. of elements

, for(i=n/2;i>=1;i--)
down_adjust(heap,i);
}

void down_adjust(int heap[ ],int i)
{
int j,temp,n,flag=1;
n=heap[0];

while(2*i<=n && flag==1)
{
j=2*i; //j points to left child
if(j+1<=n && heap[j+1] > heap[j])
j=j+1;
if(heap[i] > heap[j])
flag=0;
else
{
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
i=j;
}
}
}




Output
Enter no. of elements:5
Enter elements:12 8 46 23 7
Array after sorting:
7 8 12 23 46

, Experiment No.

WAP to sort an array using Merge sort technique



#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)
{