Implement merge sort algorithm – IGNOU BCA Assignment 2015 – 16

By | October 4, 2015

BACHELOR OF COMPUTER APPLICATIONS

Course Code : BCSL-045
Course Title : Introduction to Algorithm Design Lab
Assignment Number : BCA(IV)/L-045/Assignment/2015
Maximum Marks : 50
Weightage : 25%

Implement merge sort algorithm.

 

#include<stdio.h>
int numbers[10]={2,8,4,1,0,7,9,3,5,6};
int temp[10],array_size=10;

void mergeSort(int numbers[],int temp[],int array_size);
void m_sort(int numbers[],int temp[],int left,int right);
void merge(int numbers[],int temp[],int left,int mid,int right);

void main()
{
int i;
clrscr();
printf(“\nUnsorted List : “);
for(i=0;i<10;i++)
printf(” %d”,numbers[i]);
printf(“\n\n Starting Sorting…\n”);
mergeSort(numbers,temp,array_size);
printf(“\n Sorted List : “);
for(i=0;i<10;i++)
printf(” %d”,numbers[i]);
getch();
}

void mergeSort(int numbers[],int temp[],int array_size)
{
m_sort(numbers,temp,0,array_size-1);
}

void m_sort(int numbers[],int temp[],int left,int right)
{
int mid;
if(right > left)
{
mid = (right+left)/2;
m_sort(numbers,temp,left,mid);
m_sort(numbers,temp,mid+1,right);

merge(numbers,temp,left,mid+1,right);
}
}

void merge(int numbers[],int temp[],int left,int mid,int right)
{
int i,left_end,num_elements,tmp_pos;
left_end = mid-1;
tmp_pos = left;
num_elements = right-left+1;
while((left <= left_end) && (mid <= right))
{
if(numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos+1;
left = left+1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos+1;
mid = mid+1;
}
}

while(left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left+1;
tmp_pos = tmp_pos+1;
}
while(mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid+1;
tmp_pos = tmp_pos+1;
}
for(i=0;i<=num_elements;i++)
{
numbers[right] = temp[right];
right = right – 1;
}
}

 

Code:

[codesyntax lang=”c”]

#include<stdio.h>
int numbers[10]={2,8,4,1,0,7,9,3,5,6};
int temp[10],array_size=10;

void mergeSort(int numbers[],int temp[],int array_size);
void m_sort(int numbers[],int temp[],int left,int right);
void merge(int numbers[],int temp[],int left,int mid,int right);

void main()
{
int i;
clrscr();
printf("\nUnsorted List : ");
for(i=0;i<10;i++)
printf(" %d",numbers[i]);
printf("\n\n Starting Sorting...\n");
mergeSort(numbers,temp,array_size);
printf("\n Sorted List : ");
for(i=0;i<10;i++)
printf(" %d",numbers[i]);
getch();
}

void mergeSort(int numbers[],int temp[],int array_size)
{
m_sort(numbers,temp,0,array_size-1);
}

void m_sort(int numbers[],int temp[],int left,int right)
{
int mid;
if(right > left)
{
mid = (right+left)/2;
m_sort(numbers,temp,left,mid);
m_sort(numbers,temp,mid+1,right);

merge(numbers,temp,left,mid+1,right);
}
}

void merge(int numbers[],int temp[],int left,int mid,int right)
{
int i,left_end,num_elements,tmp_pos;
left_end = mid-1;
tmp_pos = left;
num_elements = right-left+1;
while((left <= left_end) && (mid <= right))
{
if(numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos+1;
left = left+1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos+1;
mid = mid+1;
}
}

while(left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left+1;
tmp_pos = tmp_pos+1;
}
while(mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid+1;
tmp_pos = tmp_pos+1;
}
for(i=0;i<=num_elements;i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

[/codesyntax]

ScreenShots:

C_program_Sort_Merge

C_program_Sort_Merge_Output