6. [10 pts] Programming assignment: Insertion sort/Merge sort – Write a program
ID: 3748886 • Letter: 6
Question
6. [10 pts] Programming assignment: Insertion sort/Merge sort
– Write a program to implement Insertion sort and Merge sort to sort an array
– Input array should be at size of 10, 50, 100, 300, 500, 1000, 2000, 5000, 10000, 50000 for integer numbers that are not sorted at all.
• use a pseudo random number generator function to generate an input array
– Use any language and environment of your choice, such as C++, Java, or Python. However, C++ and Qt is a recommended choice. If you use Qt, you can use QtChart to draw the graph and compare the execution time for both algorithms. See the sample code SortChart.zip in Canvas as an example of using QtChart.
(x-axis = input size n, and y-axis = the running time (ms))..
– Conclude what you observe and justify your answer.
Submit the source code, output chart(s) and your observation and conclusion.
Explanation / Answer
Merge Sort
#include<stdlib.h>
#include<stdio.h>
/ Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] /
void merge(int arr[], int l, int m, int r);
/* l is for left index and r is right index of the sub-array
of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/ Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] /
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/ create temp arrays /
int L[n1], R[n2];
/ Copy data to temp arrays L[] and R[] /
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/ Copy the remaining elements of L[], if there are any /
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/ Copy the remaining elements of R[], if there are any /
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/ Function to print an array /
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}
/ Driver program to test above functions /
int main()
{
int arr[10] ;
int z = 0;
for(int z = 0 ; z<10 ;z++) {
int r = (rand() % 50000) + 1;
arr[z]= r;
}
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is ");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf(" Sorted array is ");
printArray(arr, arr_size);
return 0;
}
Insertion Sort:
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
// A function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}
/ Driver program to test insertion sort /
int main()
{
int arr[10] ;
int z = 0;
for(int z = 0 ; z<10 ;z++) {
int r = (rand() % 50000) + 1;
arr[z]= r;
}
int n = sizeof(arr)/sizeof(arr[0]);
printArray(arr, n);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.