i need an output at the end! Programming Assignment: You need to implement inser
ID: 3750210 • Letter: I
Question
i need an output 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
I have created here programs to create numbers 1..n in ascending, descending, 50 random numbers, permutations of random strings generated by concatenating numbers. I have created the program to have different size of input and calculate the time taken to execute them.
Sorting programs order the input in ascending or descending order
There are different algorithms for sorting
insertion sort works well for small size by taking each input and adding to sorted array
quick sort works well or big size by splitting the array into elements lesser than and greater than pivot splitting each into two till the size becomes 1
merge sort works well in secondary memory other algorithms are for primary memory merge sort works by splitting the array into two halves and again splitting till the size becomes 1 and merging the two
#include <iostream>
using namespace std;
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
cout << arr[i] <<" ";
}
/* Driver program to test insertion sort */
int main()
{
int *arr;
int j[]={100,200,300,400,500,1000.4000.10000};
for(int k=0;k<sizeof(j)/sizeof(j[0])
{
arr = (int*) calloc (j,sizeof(int))
for(int i=1;i<sizeof(j)/sizeof(j[0];i++)
{
arr[i]=101-i;
}
clock_t t;
t = clock();
int n = sizeof(arr)/sizeof(arr[0]);
char s[20];
scanf("%s",s)
if(strcmp(s,"insertion sort")
insertionSortRecursive(arr, n);
if(strcmp(s,"merge sort")
mergeSort(arr, 0, arr_size - 1);
printArray(arr, n);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
}
printf("fun() took %f seconds to execute ", time_taken);
return 0;
}
____________________________________________________________________________________________________________________________________________________________
#include <iostream>
using namespace std;
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
cout << arr[i] <<" ";
}
/* Driver program to test insertion sort */
int main()
{
int *arr;
int j[]={100,200,300,400,500,1000.4000.10000};
for(int k=0;k<sizeof(j)/sizeof(j[0])
{
arr = (int*) calloc (j,sizeof(int))
for(int i=1;i<sizeof(j)/sizeof(j[0];i++)
{
arr[i]=i+1;
}
clock_t t;
t = clock();
int n = sizeof(arr)/sizeof(arr[0]);
char s[20];
scanf("%s",s)
if(strcmp(s,"insertion sort")
insertionSortRecursive(arr, n);
if(strcmp(s,"merge sort")
mergeSort(arr, 0, arr_size - 1);
printArray(arr, n);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("fun() took %f seconds to execute ", time_taken);
}
return 0;
}
____________________________________________________________________________________________________________________________________________________________
#include <iostream>
using namespace std;
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
cout << arr[i] <<" ";
}
/* Driver program to test insertion sort */
int main()
{
int *arr;
int j[]={100,200,300,400,500,1000.4000.10000};
for(int k=0;k<sizeof(j)/sizeof(j[0])
{
arr = (int*) calloc (j,sizeof(int))
for(int i=1;i<sizeof(j)/sizeof(j[0];i++)
{
arr[i]=rand();
}
clock_t t;
t = clock();
int n = sizeof(arr)/sizeof(arr[0]);
char s[20];
scanf("%s",s)
if(strcmp(s,"insertion sort")
insertionSortRecursive(arr, n);
if(strcmp(s,"merge sort")
mergeSort(arr, 0, arr_size - 1);
printArray(arr, n);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("fun() took %f seconds to execute ", time_taken);
}
return 0;
}
____________________________________________________________________________________________________________________________________________________________
#include <iostream>
using namespace std;
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
cout << arr[i] <<" ";
}
// Generates and prints 'count' random
// numbers in range [lower, upper].
int * printRandoms(int lower, int upper,
int count)
{
int i;
int *j;
int k;
j = (int*) calloc (count,sizeof(int));
for (i = 0; i < count; i++) {
int num = (rand() %
(upper - lower + 1)) + lower;
j[i] = num;
}
return j;
}
/* Driver program to test insertion sort */
int main()
{
int *arr;
int j[]={100,200,300,400,500,1000.4000.10000};
int *ar;
for(int k=0;k<sizeof(j)/sizeof(j[0])
{
ar=printRandoms(1,k,50);
arr = (int*) calloc (j,sizeof(int))
for(int i=1;i<sizeof(j)/sizeof(j[0];i++)
{
arr[i]=ar(1,j[k],50);
}
clock_t t;
t = clock();
int n = sizeof(arr)/sizeof(arr[0]);
char s[20];
scanf("%s",s)
if(strcmp(s,"insertion sort")
insertionSortRecursive(arr, n);
if(strcmp(s,"merge sort")
mergeSort(arr, 0, arr_size - 1);
printArray(arr, n);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("fun() took %f seconds to execute ", time_taken);
}
return 0;
}
____________________________________________________________________________________________________________________________________________________________
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
// Recursive function to sort an array using
// insertion sort
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
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++;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
cout << arr[i] <<" ";
}
// Generates and prints 'count' random
// numbers in range [lower, upper].
int * printRandoms(int lower, int upper,
int count)
{
int i;
int *j;
int k;
j = (int*) calloc (count,sizeof(int));
for (i = 0; i < count; i++) {
int num = (rand() %
(upper - lower + 1)) + lower;
j[i] = num;
}
return j;
}
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s ", a);
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}
/* Driver program to test insertion sort */
int main()
{
char *arr;
int j[]={100,200,300,400,500,1000.4000.10000};
int *ar;
char *s1;
char *s2;
for(int k=0;k<sizeof(j)/sizeof(j[0])
{
s1="";
char *result = malloc(strlen(s1) + strlen(s2) + 1);
ar=printRandoms(1,k,50);
clock_t t;
t = clock();
arr = (int*) calloc (j,sizeof(char))
for(int i=1;i<sizeof(j)/sizeof(j[0];i++)
{
s2=ar(1,j[k],50);
s1=strcat(s1,s2);
permute(s1,0,strlen()s1);
arr[i]=s1;
}
int n = sizeof(arr)/sizeof(arr[0]);
char s[20];
scanf("%s",s)
if(strcmp(s,"insertion sort")
insertionSortRecursive(arr, n);
if(strcmp(s,"merge sort")
mergeSort(arr, 0, arr_size - 1);
printArray(arr, n);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("fun() took %f seconds to execute ", time_taken);
}
return 0;
}
}
/* 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)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.