Merge Sort, sorted : O(N*logN) Merge Sort, reversed ordered: O(N*logN) Insertion
ID: 3872059 • Letter: M
Question
Merge Sort, sorted : O(N*logN)
Merge Sort, reversed ordered: O(N*logN)
Insertion Sort, sorted: O(N)
Insertion Sort, reversed ordered: N*(n-1)/2
-----------------------------------------------------------------------
Write a program in C++ to verify this. program should randomly generate three integer arrays of N=103, 105, and 107 elements and run either merge sort or insertion sort to sort the arrays in increasing and decreasing orders. Then run both insertion sort and merge sort on the three ordered and three reverse-ordered arrays and output the numbers of comparisons and assignments performed between elements of the input arrays during the executions of the two sorting algorithms on each of the arrays. Draw a table to summarize the outputs of your program on the six input arrays (3 ordered and 3 reverse-ordered) and discuss about whether the performance of the insertion sort and merge sort on those ordered and reverse-ordered arrays is consistent with the solution above. If not, why?
Will Rate, thank you.
Explanation / Answer
Merge sort comparison count on three arrays (randomly generated ) -
#include <iostream>
#include<cstdlib>
using namespace std;
int c=0;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
c++;
}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
c++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
c++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}
int main()
{
int n, i;
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=rand()%100;//randsom number in the range of 0 to 100
}
MergeSort(arr, 0, 103-1);
cout<<"Number of comparisons for 103 inputs are "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=rand()%100;//randsom number in the range of 0 to 100
}
c=0;
MergeSort(brr, 0, 105-1);
cout<<"Number of comparisons for 105 inputs are "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=rand()%100;//randsom number in the range of 0 to 100
}
c=0;
MergeSort(arr, 0, 107-1);
cout<<"Number of comparisons for 107 inputs are "<<c<<endl;
return 0;
}
Output -
Number of comparisons for 103 inputs are 696
Number of comparisons for 105 inputs are 712
Number of comparisons for 107 inputs are 728
Merge sort for sorted elements -
#include <iostream>
#include<cstdlib>
using namespace std;
int c=0;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
c++;
}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
c++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
c++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}
int main()
{
int n, i;
//array list is alreday sorted
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=i;
}
MergeSort(arr, 0, 103-1);
cout<<"Number of comparisons for 103 inputs are in sorted array "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=i;
}
c=0;
MergeSort(brr, 0, 105-1);
cout<<"Number of comparisons for 105 inputs are in sorted array "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=i;
}
c=0;
MergeSort(arr, 0, 107-1);
cout<<"Number of comparisons for 107 inputs are in sorted array "<<c<<endl;
return 0;
}
output -
Number of comparisons for 103 inputs are in sorted array 696
Number of comparisons for 105 inputs are in sorted array 712
Number of comparisons for 107 inputs are in sorted array 728
merge sort for reverse array -
#include <iostream>
#include<cstdlib>
using namespace std;
int c=0;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
c++;
}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
c++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
c++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);
// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}
int main()
{
int n, i;
//array list is alreday sorted
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=100-i;
}
MergeSort(arr, 0, 103-1);
cout<<"Number of comparisons for 103 inputs are in reversed array "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=100-i;
}
c=0;
MergeSort(brr, 0, 105-1);
cout<<"Number of comparisons for 105 inputs are in reversed array "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=100-i;
}
c=0;
MergeSort(arr, 0, 107-1);
cout<<"Number of comparisons for 107 inputs are in reversed array "<<c<<endl;
return 0;
}
outputs -
Number of comparisons for 103 inputs are in sorted array 696
Number of comparisons for 105 inputs are in sorted array 712
Number of comparisons for 107 inputs are in sorted array 728
So complexity of merge sort is O(n*log(n)) that will be same for sorted or random array.
Inserion sort for random array -
#include<iostream>
#include<cstdlib>
using namespace std;
int c=0;
void insertion_sort(int arr[],int n );
int main()
{
int n, i;
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=rand()%100;
}
insertion_sort(arr, 103);
cout<<"Number of comparisons for 103 inputs are in random array "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=rand()%100;
}
c=0;
insertion_sort(brr, 105);
cout<<"Number of comparisons for 105 inputs are in random array "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=rand()%100;
}
c=0;
insertion_sort(crr, 107);
cout<<"Number of comparisons for 107 inputs are in random array "<<c<<endl;
return 0;
}
void insertion_sort(int arr[],int n )
{
int i , j , temp;
for(i=1; i<n; i++)
{
temp=arr[i];
j=i-1;
c++;
while((temp<arr[j]) && (j>=0))
{
arr[j+1]=arr[j];
j=j-1;
c++;
}
arr[j+1]=temp;
}
}
outputs -
Number of comparisons for 103 inputs are in random array 2642
Number of comparisons for 105 inputs are in random array 3061
Number of comparisons for 107 inputs are in random array 2618
Insertion sort for sorted array -
#include<iostream>
#include<cstdlib>
using namespace std;
int c=0;
void insertion_sort(int arr[],int n );
int main()
{
int n, i;
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=i;
}
insertion_sort(arr, 103);
cout<<"Number of comparisons for 103 inputs are in sorted array "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=i;
}
c=0;
insertion_sort(brr, 105);
cout<<"Number of comparisons for 105 inputs are in sorted array "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=i;
}
c=0;
insertion_sort(crr, 107);
cout<<"Number of comparisons for 107 inputs are in sorted array "<<c<<endl;
return 0;
}
void insertion_sort(int arr[],int n )
{
int i , j , temp;
for(i=1; i<n; i++)
{
temp=arr[i];
j=i-1;
c++;
while((temp<arr[j]) && (j>=0))
{
arr[j+1]=arr[j];
j=j-1;
c++;
}
arr[j+1]=temp;
}
}
outputs -
Number of comparisons for 103 inputs are in sorted array 102
Number of comparisons for 105 inputs are in sorted array 104
Number of comparisons for 107 inputs are in sorted array 106
insertion sort for reversed array -
#include<iostream>
#include<cstdlib>
using namespace std;
int c=0;
void insertion_sort(int arr[],int n );
int main()
{
int n, i;
int arr[200],brr[200],crr[200];
for(i = 0; i < 103; i++)
{
arr[i]=100-i;
}
insertion_sort(arr, 103);
cout<<"Number of comparisons for 103 inputs are in reversed array "<<c<<endl;
for(i = 0; i < 105; i++)
{
brr[i]=100-i;
}
c=0;
insertion_sort(brr, 105);
cout<<"Number of comparisons for 105 inputs are in reversed array "<<c<<endl;
for(i = 0; i < 107; i++)
{
crr[i]=100-i;
}
c=0;
insertion_sort(crr, 107);
cout<<"Number of comparisons for 107 inputs are inreversed array "<<c<<endl;
return 0;
}
void insertion_sort(int arr[],int n )
{
int i , j , temp;
for(i=1; i<n; i++)
{
temp=arr[i];
j=i-1;
c++;
while((temp<arr[j]) && (j>=0))
{
arr[j+1]=arr[j];
j=j-1;
c++;
}
arr[j+1]=temp;
}
}
outputs -
Number of comparisons for 103 inputs are in reversed array 5355
Number of comparisons for 105 inputs are in reversed array 5564
Number of comparisons for 107 inputs are inreversed array 5777