I need the solution to this first home work assignement please. It\'s a summer c

Question

I need the solution to this first home work assignement please. It's a summer class so it's very fast paced.

Due date: June 8, 2017 (No late submission allowed) How to submit? : Submit your source code and sample result with report of findings Implement two sorting algorithm (insertion and merge sort) learned in the class with several inputs from different size. Compare the running time from implementations and write a report of your findings. Start with small size input like 10 integer array and increase your input size until your computer can handle or meaningful results occurs. Use exact algorithm from text book for sorting programming and you can use system clock to measure running time.

Explanation / Answer

Insertion Sort :

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Program :

Merge Sort :

merge sort first divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

Program :

#include<stdio.h>
#include<conio.h>
void merge(int [],int ,int ,int );
void part(int [],int ,int );
int main()
{
int arr[30];
int i,size;
printf(" ------- Merge sorting method ------- ");
printf("Enter total no. of elements : ");
scanf("%d",&size);
for(i=0; i<size; i++)
{
printf("Enter %d element : ",i+1);
scanf("%d",&arr[i]);
}
part(arr,0,size-1);
printf(" ------- Merge sorted elements ------- ");
for(i=0; i<size; i++)
printf("%d ",arr[i]);
getch();
return 0;
}


void part(int arr[],int min,int max)
{
int mid;
if(min<max)
{
mid=(min+max)/2;
part(arr,min,mid);
part(arr,mid+1,max);
merge(arr,min,mid,max);
}
}


void merge(int arr[],int min,int mid,int max)
{
int tmp[30];
int i,j,k,m;
j=min;
m=mid+1;
for(i=min; j<=mid && m<=max ; i++)
{
if(arr[j]<=arr[m])
{
tmp[i]=arr[j];
j++;
}
else
{
tmp[i]=arr[m];
m++;
}
}
if(j>mid)
{
for(k=m; k<=max; k++)
{
tmp[i]=arr[k];
i++;
}
}
else
{
for(k=j; k<=mid; k++)
{
tmp[i]=arr[k];
i++;
}
}
for(k=min; k<=max; k++)
arr[k]=tmp[k];
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.