Showing posts with label merge sort. Show all posts
Showing posts with label merge sort. Show all posts

Saturday, May 28, 2016

WAP to combine two sorted link list using merge sort

#include<stdio.h>
#include<conio.h>
struct node
{
int n;
struct node *next;
}*first=NULL,*first2=NULL,*first3=NULL,*temp,*temp1,*temp2,*temp3;
void insert(int x)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->n=x;
if(first==NULL)
{
temp->next=NULL;
first=temp;
}
else
{
temp1=first;
while(temp1->next->n<x && temp1->next!=NULL)
{
temp1=temp1->next;
}
if(temp1==first && temp1->n>x)
{
temp->next=first;
first=temp;
}
else
{
temp->next=temp1->next;
temp1->next=temp;
}
}
}
void insert2(int x)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->n=x;
if(first2==NULL)
{
temp->next=NULL;
first2=temp;
}
else
{
temp1=first2;
while(temp1->next->n<x && temp1->next!=NULL)
{
temp1=temp1->next;
}
if(temp1==first2 && temp1->n>x)
{
temp->next=first2;
first2=temp;
}
else
{
temp->next=temp1->next;
temp1->next=temp;
}
}
}
void display()
{
if(first==NULL)
{
printf("Stack is empty");
return;
}
temp=first;
while(temp!=NULL)
{
printf("\n%d",temp->n);
temp=temp->next;
}
}
void display2()
{
if(first2==NULL)
{
printf("Stack is empty");
return;
}
temp=first2;
while(temp!=NULL)
{
printf("\n%d",temp->n);
temp=temp->next;
}
}
void display3()
{
if(first3==NULL)
{
printf("Stack is empty");
return;
}
temp=first3;
while(temp!=NULL)
{
printf("\n%d",temp->n);
temp=temp->next;
}
}
void merge()
{
temp2=first;
temp3=first2;
while(temp2!=NULL && temp3!=NULL)
{
temp=(struct node*)malloc(sizeof(struct node));
if(temp2->n<temp3->n)
{
temp->n=temp2->n;
temp2=temp2->next;
}
else
{
temp->n=temp3->n;
temp3=temp3->next;
}
if(first3==NULL)
{
first3=temp;
}
else
{
temp1->next=temp;
}
temp1=temp;
temp->next=NULL;
}
while(temp2!=NULL)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->n=temp2->n;
temp2=temp2->next;
temp1->next=temp;
temp1=temp;
temp->next=NULL;
}
while(temp3!=NULL)
{
temp=(struct node*)malloc(sizeof(struct node));
temp->n=temp3->n;
temp3=temp3->next;
temp1->next=temp;
temp1=temp;
temp->next=NULL;
}
}
void main()
{
int x;
char ch;
clrscr();
printf("\nEnter elements in list 1:\n");
do
{
printf("\nEnter a value: ");
scanf("%d",&x);
insert(x);
fflush(stdin);
display();
printf("\nDo you want to contiune(Y/N):");
scanf("%c",&ch);

}while(ch=='y' || ch=='Y');
printf("\nElements in list 1:\n");
display();
printf("\nEnter elements in list 2:\n");
do
{
printf("\nEnter a value: ");
scanf("%d",&x);
insert2(x);
fflush(stdin);
display2();
printf("\nDo you want to contiune(Y/N):");
scanf("%c",&ch);

}while(ch=='y' || ch=='Y');
printf("\nElements in list 2:\n");
display2();
merge();
printf("\nList after applying merge sort:\n")
display3();
getch();
}