(b) Run both programs on the worst-case input (reverse-sorted array) on differen
ID: 3756497 • Letter: #
Question
(b) Run both programs on the worst-case input (reverse-sorted array) on different sizes eg. n-1,2,3,...) and write down the value of n for which the running time in milliseconds) of insertion sort exceeds that of mergesort (c) Make a copy of your mergesort program and modify it so that instead of recursively sorting the two sub-arrays, it would instead sort the two sub-arrays using insertion sort (let us call this new algorithm hybrid-mergesort) (d) Run hybrid-mergesort on the worst-case input for the same value of n that you recorded in part (b) of this exercise. Is the running-tie of hybrid-mergesort better or worse than mergesort at this value of n?Explanation / Answer
Insertion Sort :
Insertion sorting is used for sorting upto N elements. It is the fastest sorting algorithm and pick up the elements arr[i] and insert it into sorted sequence arr[0…i-1].It is a simple sorting algorithm.
Insertion sort(itemtype array[], datatye n)
{
int i=1,j;
for ( i=1;i<n;i++)
{
itemtype value=array[i];
while(j>0 && value <array[j-1])
{
array[j]= array[j-1];
--j;
}
array[j]=value;
}
}
Merge sort:
Merge sort also known as recursive algorithm.It follows the divide and conquer strategy.
That means it divide the array into two sub-arrays.
Merge sort(A, p, r)
If p > r
return;
q = (p+r)/2;
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Insertion sort is the better when comparing to merge sort.
for Worst cas scenario of insertion sort:
1)Inner loop is executed i times for each i=1 to n-1 =>O(N2)
2)In reverse order array :
The arr[i] is inserted into the sorted arr[0..n-1],and to arr[i] needs to compare with all elements arr[0..n-1] and move each element one position to the right. The time complexity of
For example N=100 so 1* 10-7 seconds -->O(1)
O(N2)= 1*10-4 seconds for N=100
2) Worst case of mergesort :ssample
In mergesort the it divided into two sub arrays and do the maximum comparison.
int GWC(int arr[], int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
int left[m - l + 1];
int right[r - m];
div(arr, left, right, l, m, r);
GWC(left, l, m);
GWC(right, m + 1, r);
merge(arr, left, right, l, m, r);
}
}
int merge(int arr[], int l[], int r[],
int l1, int m, int r1)
{
int i;
for (i = 0; i <= m - l1; i++)
arr[i] = left[i];
for (int j = 0; j < r1 - m; j++)
arr[i + j] = right[j];
}
int div(int arr[], int l[], int r[],
int l1, int m, int r1)
{
for (int i = 0; i <= m - l1; i++)
left[i] = arr[i * 2];
for (int i = 0; i < r1 - m; i++)
right[i] = arr[i * 2 + 1];
}
It gives the worst case output. It
Hybrid mergesort :
Hybrid MergeInsertionSort:
program:
Hybrid mergesort( int n, int m,int s, int arr[])
{
int mid =(n+m)/2, r=0, l=0;
if (m-n<=s)
return insertsort(arr,n,m);
else
{
r=mergesort(n,mid,s,arr);
l=mergesort(mid+1,m,s,arr);
return r+l+merge(n,m,s,arr);
}
}
insertionsort(int arr[], int n, int m)
{
int t, stat=0;
for(int i=n+1;i<=m;i++)
{
for(int j=i;j>n;j--)
{
stat++;
if(arr[j]<arr[j-1])
{
t=arr[j];
arr[j]=arr[j-1];
arr[j-1]=t;
}else
break;
}}return stat;
}
shift arr method(int st,int m, int arr[])
{
for(int i=m;i>st;i--)
arr[i]=arr[i-1];
}
mergesort(int n, int m, int s, int arr[])
int c=0;
if(m-n<=s)
return 0;
int mid=(n+m)/2;
int t, i=n,j=mid+1;
while(i<=mid && j<=m)
{
c++;
if(arr[i] >= arr[j])
{
if(i==mid++&&j==m && (arr[i]==arr[j]))
break;
t = arr[j];
shiftArraymethod(i,j++,arr);
arr[i] = temp;
if(arr[i+1]==arr[i]){
i++;
}
}
i++;
}
return c;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.