Thursday 18 April 2013

MERGE SORT


Conceptually, a merge sort works as follows
  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

The following figures will clearly illustrate the working of merge sort:-



IMPLEMENTATION OF MERGE SORT USING LINKED LIST

Here each number, that the user is prompted to input is stored in a node of the linked list, and then the list is divided, and then a recursive function is called to implement the merging.

/***********************************************************************************************************///MERGE SORT
//SORTING A LINK LIST
//RECURSIVE DEFINITION


#include<stdio.h>
#include<conio.h>

struct Node
{
int val;
struct Node*next;
};

typedef struct Node node;

void printlist(node*);
node*makenode(int);
node*mergesort(node*);
node*divide(node*);
node*merge(node*,node*);

int main()
{
int i,tmp;
node*start,*nn,*last;
clrscr();
start=last=NULL;

while(1)
{
printf("enter the data part of the node:");
scanf("%d",&tmp);

if(tmp==0)
break;

nn=makenode(tmp);

if(start)
{
last->next=nn;
last=nn;
}
else
{
start=last=nn;
}
}
start=mergesort(start);

printlist(start);
getch();
return 1;
}


node*mergesort(node*start)
{
node*nh;
if(start&&start->next)
{

nh=divide(start);
start=mergesort(start);
nh=mergesort(nh);
start=merge(start,nh);
}
return start;
}

node*divide(node*start)
{
node*ptr1,*ptr2,*start2=NULL;
if(start->next)
{
ptr1=start;
ptr2=start->next->next;
while(ptr2)
{
ptr1=ptr1->next;
ptr2=ptr2->next;
if(ptr2)
ptr2=ptr2->next;
}
start2=ptr1->next;
ptr1->next=NULL;
}
return start2;
}

node*merge(node*s1,node*s2)
{
node*s3,*l3,*tmp;
s3=l3=NULL;
while(s1&&s2)
{
if(s1->val<s2->val)
{
tmp=s1;
s1=s1->next;
}
else
{
tmp=s2;
s2=s2->next;
}
if(!s3)
s3=tmp;
else
l3->next=tmp;
l3=tmp;
}
if(s1)
{
if(!s3)
s3=s1;
else
l3->next=s1;
}
if(s2)
{
if(!s3)
s3=s2;
else
l3->next=s2;
}
return s3;
}


void printlist(node*start)
{
while(start)
{
printf("%d\t",start->val);
start=start->next;
}
}


node*makenode(int tmp)
{
node*nn;
nn=(node*)malloc(sizeof(node));
nn->val=tmp;
nn->next=NULL;
return nn;
}
/*******************************************************************************/



IMPLEMENTATION OF MERGE-SORT USING ARRAYS

/*****************************************************************************/
//MERGE SORT

#include<stdio.h>
#include<conio.h>

void mergesort(int*,int ,int);
void merge(int *,int ,int);

//int b[20];

int main()
{
//clrscr();
int arr[20];
int i,j,n;
clrscr();
printf("ENTER THE NUMBER OF ELEMENTS OF ARRAY:");
scanf("%d",&n);
printf("enter the data of array:\n");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

mergesort(arr,0,n-1);

for(i=0;i<n;i++)
printf("%d\t",arr[i]);

getch();
return 1;
}

void mergesort(int *arr,int i,int j)
{
int mid;
if(i>=j)
return;
else
{
mid=(i+j)/2;
mergesort(arr,i,mid);
mergesort(arr,mid+1,j);
merge(arr,i,j);
}
}

void merge(int *arr,int i,int j)
{
int start=i;
int mid,k,l=i,b[20];
mid=(i+j)/2;

k=mid+1;

while(k<=j&&i<=mid)
{

if(arr[i]<arr[k])
b[l++]=arr[i++];
else
b[l++] =arr[k++];
}

if(i>mid)
while(k<=j)
b[l++]=arr[k++];
else if(k>j)
while(i<=mid)
b[l++]=arr[i++];

for(l=start;l<=j;l++)
arr[l]=b[l];
}

/****************************************************************************/

No comments:

Post a Comment