Merge Sort and Insertion Sort Programs In C++ Implement merge sort and insertion
ID: 3703032 • Letter: M
Question
Merge Sort and Insertion Sort Programs
In C++
Implement merge sort and insertion sort to sort an array/vector of integers. Name one program “mergesort” and the other “insertsort”. Your programs should be able to read inputs from a file called “data.txt” where the first value of each line is the number of integers that need to be sorted, followed by the integers.
Example values for data.txt:
3 18 1 5 12
8 3 3 5 4 6 6 2 2
The output will be written to files called “merge.out” and “insert.out”. For the above example the output would be:
1 3 5 12 18
2 2 3 3 4 5 6 6 8
Explanation / Answer
#include<iostream>
#include<fstream>
using namespace std;
void insertion_sort(int a[], int n);
void merge_sort(int arr[],int p, int r);
void merge(int arr[],int p,int q,int r);
int main()
{
ifstream in("data.txt");
// insertion sort
int n1;
in>>n1;
// create array of size n1
int arr1[n1 + 1];
arr1[0] = n1;
int i;
// read content from file
for( i = 1 ; i <= n1 ; i++ )
in>>arr1[i];
insertion_sort(arr1 , n1 + 1);
cout<<endl;
// open file in write mode
ofstream out1("insert.out");
// write content into file
for( i = 0 ; i <= n1 ; i++ )
out1<<arr1[i]<<" ";
// merge sort
int n2;
in>>n2;
// create array of size n1
int arr2[n2 + 1];
arr2[0] = n2;
// read content from file
for( i = 1 ; i <= n2 ; i++ )
in>>arr2[i];
merge_sort( arr2, 0 , n2 );
// open file in write mode
ofstream out2("merge.out");
// write content into file
for( i = 0 ; i <= n2 ; i++ )
out2<<arr2[i]<<" ";
return 0;
}
void insertion_sort(int a[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
// store the current element in temp
temp = a[i];
// set j to i - 1
j = i - 1;
// all elements greater than temp are
// shifted 1 position right
while (j >= 0 && a[j] > temp)
{
// shifted 1 position right
a[j+1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
void merge_sort(int arr[],int p, int r)
{
// if index is right
if(p < r)
{
// get the mid index
int mid = (p + r) / 2;
// sort the left subarray
merge_sort(arr, p, mid);
// sort the right subarray
merge_sort(arr, mid + 1, r);
// merge the two subarrays
merge(arr, p, mid, r);
}
}
// merge thw two arrays
void merge(int arr[],int p,int q,int r)
{
// get the length of left subarray
int n1 = q - p + 1;
// get the length of right subarray
int n2 = r - q;
int i,j,k;
// create two arrays left and right
int *left = new int[n1 + 1];
int *right = new int[n2 + 1];
// fill left with the contents of left subarray of arr
for(i = 0; i < n1; i++)
left[i] = arr[p + i];
// fill right with the contents of right subarray of arr
for(i = 0; i < n2; i++)
right[i] = arr[q + i + 1];
// set the last element to infinity
left[n1] = INT_MAX;
right[n2] = INT_MAX;
i=0;
j=0;
for(k = p ; k <= r; k++)
{
// if the current element of left is smaller than
// current element of right
if(left[i] <= right[j])
{
arr[k] = left[i];
i++;
}
// if the current element of left is larger than
// current element of right
else
{
arr[k] = right[j];
j++;
}
}
}
-----------------------data.txt-----------------------
4 18 1 5 12
8 3 3 5 4 6 6 2 2
-------------------------------merge.out--------------------------------
2 2 3 3 4 5 6 6 8
-----------------------------insert.out----------------------------
1 4 5 12 18