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: