OUTPUTS AT THE END! Programming Assignment: You need to implement insertion sort
ID: 3751420 • Letter: O
Question
OUTPUTS AT THE END!
Programming Assignment: You need to implement insertion sort and merge sort (decreasing or increasing order) algorithms and measure the performance of these two algorithms in terms of number of steps and CPU running time. For each algorithm, and for each n = 100, 200, 300, 400, 500, 1000, 4000, 10000, measure its running time and number of steps when the input is (1) already sort, i.e. n, n-1, …, 3, 2,1; (2) reversely sorted 1, 2, 3, … n; (3) random permutation of 1, 2, …, n; (4) 50 instances of n random numbers generated in the range of [1..n].
Note:
(1) You may have to repeat the algorithm many times, each time you need to initialize the array.
(2) Your running time should exclude the time for initialization.
(3) All measurement should be done in a single run, i.e. you do not need to run once for n=100, another time for n=200, etc
What to turn in:
(1) Well documented source code in C++
(2) Report the number of steps and the CPU running time in a table,
(3) Plot the running time of the algorithm results
(4) Approximation the constant c in the complexity of insertion sort (cn^2), and merge sort (cnlgn) by inspecting the results
Explanation / Answer
ANS:
C++ CODE:
INSERTION SORT:
#include<iostream>
using namespace std;
int main()
{
int i,j,n,tmp,m[30];
cout<<"Enter the number of elements you want to sort:";
cin>>n;
cout<<" …Enter the elements… ";
for(i=0;i<n;i++)
{
cin>>m[i];
}
for(i=1;i<=n-1;i++)
{
tmp=m[i];
j=i-1;
while((tmp<m[j])&&(j>=0))
{
m[j+1]=m[j];
j=j-1;
}
m[j+1]=tmp;
}
cout<<" The Sorted list is as follows ";
for(i=0;i<n;i++)
{
cout<<m[i]<<" ";
}
return 0;
}
à therefore we can say that if it’s a 1 COMPARISON during pass 1 for proper place and then There are 2 comparisons during pass 2 for proper place and So on..
--F(n) = 1 + 2 + 3 + . . . . + (n-1)
= n (n-1)/2
à F(n) = O(n2)
Therefore ,ultimately in the insertion sort program the complexity is O(n2)
SELECTION SORT:
àdefinition:It is the selection of an element and placing it in sorted order.
The below is the code for the SELECTION SORT:
#include<iostream>
using namespace std;
int main()
{
int i,j,n,location,tmp,low,m[30];
cout<<"Enter the number of numbers you want:";
cin>>n;
cout<<" Enter your numbers ";
for(i=0;i<n;i++)
{
cin>>m[i];
}
for(i=0;i<n-1;i++)
{
low=m[i];
location=i;
for(j=i+1;j<n;j++)
{
if(low>m[j])
{
low=m[j];
location=j;
}
}
tmp=m[i];
m[i]=m[location];
m[location]=tmp;
}
cout<<" The Sorted list is :: ";
for(i=0;i<n;i++)
{
cout<<m[i]<<" ";
}
return 0;
}
Therefore,the time complexity in worst case for selection sort is O(n^2).
MERGE SORT:
àmerge sort is nothing but the divide and conquer method,it splits the array into two sets and it will merge them
The below is the code for the MERGE SORT:
#include <iostream>
using namespace std;
void Mrge(int *a, int lw, int hgh, int md)
{
int i, j, k, tmp[hgh-lw+1];
i = lw;
k = 0;
j = md + 1;
while (i <= md && j <= hgh)
{
if (y[i] < y[j])
{
tmp[k] = y[i];
k++;
i++;
}
else
{
tmp[k] = y[j];
k++;
j++;
}
}
while (i <= md)
{
tmp[k] = y[i];
k++;
i++;
}
while (j <= hgh)
{
tmp[k] = y[j];
k++;
j++;
}
for (i = lw; i <= hgh; i++)
{
y[i] = tmp[i-lw];
}
}
void MrgeSort(int *a, int lw, int hgh)
{
int md;
if (lw < hgh)
{
md=(lw+hgh)/2;
MrgeSort(a, lw, md);
MrgeSort(a, md+1, hgh);
Mrge(a, lw, hgh, md);
}
}
int main()
{
int n, i;
cout<<" Enter your numbers to be sorted: ";
cin>>n;
int ar[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>ar[i];
}
MrgeSort(ar, 0, n-1);
cout<<" The Sorted Data is:: ";
for (i = 0; i < n; i++)
cout<<"->"<<ar[i];
return 0;
then here the merge sort has the time complexity is O(nlogn)
QUICK SORT:
àIn this the problem discuss with the pivot element,intilally we will pick the pivot element and then all the elements smaller than pivot are placed at its left while elements bigger are placed at right
The below is the code for the QUICK SORT:
#include <iostream>
using namespace std;
void qsort(int[],int,int);
int ption(int[],int,int);
int main()
{
int l[50],n,i;
cout<<"enter number of elements?";
cin>>n;
cout<<" Enter the array elements:";
for(i=0;i<n;i++)
cin>>l[i];
qsort(a,0,n-1);
cout<<" after sorting the array is :";
for(i=0;i<n;i++)
cout<<l[i]<<" ";
return 0;
}
void qsort(int l[],int l,int u)
{
int j;
if(l<u)
{
j=ption(a,l,u);
qsort(a,l,j-1);
qsort(a,j+1,u);
}
}
int ption(int l[],int l,int u)
{
int v,i,j,tmp;
v=l[l];
i=l;
j=u+1;
do
{
do
i++;
while(l[i]<v&&i<=u);
do
j--;
while(v<l[j]);
if(i<j)
{
tmp=l[i];
l[i]=l[j];
l[j]=tmp;
}
}while(i<j);
l[l]=l[j];
l[j]=v;
return(j);
}
Hence,here the time complexity is forthe average and best case O(nlogn) and worst case O(n^2).
BUBBLE SORT:
àthis process exists if the sorting adjacent elements are sorting and swapping if required for sorting.
The below is the code for the BUBBLE SORT:
#include<iostream>
using namespace std;
int main()
{
int p[50],n,i,j,tmp;
cout<<"Enter the size of array you want: ";
cin>>n;
cout<<"Enter the array elements as required: ";
for(i=0;i<n;++i)
cin>>p[i];
for(i=1;i<n;++i)
{
for(j=0;j<(n-i);++j)
if(p[j]>p[j+1])
{
tmp=p[j];
p[j]=p[j+1];
p[j+1]=tmp;
}
}
cout<<"Array after bubble sort elements are:";
for(i=0;i<n;++i)
cout<<" "<<p[i];
return 0;
}
Hence it uses the 2 loops for comparision then the timecomplexity for this algorithm is O(n^2).
IF YOU HAVE ANY EXTRA ANSWER COMMENT BELLOW
RATE THUMBSUP PLZZZZZZZZZZZ
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.