Question
C++ I want to measure the runtime performance of insertion sort (naive and improved) and merge sort for random, sorted, and inverse sorted inputs of
C++
I want to measure the runtime performance of insertion sort (naive and improved) and merge sort for random, sorted, and inverse sorted inputs of different size (m) and vector dimension (n). The functions create_random_ivector, create_sorted_ivector, create reverse_sorted_ivector can be used. How do I do this?
sort.cpp
#include
#include
#include "sort.h"
int ivector_length(int* v, int n) {
int sum;
sum = 0;
for (int i = 0; i < n; i++) {
sum += (v[i] < 0) ? -v[i] : v[i];
}
return sum;
}
/*
* insertion sort
*/
void insertion_sort(int** A, int n, int l, int r) {
int i;
int* key;
for (int j = l+1; j <= r; j++) {
key = A[j];
i = j - 1;
while ((i >= l) && (ivector_length(A[i], n) > ivector_length(key, n))) {
A[i+1] = A[i];
i = i - 1;
}
A[i+1] = key;
}
}
/*
* TO IMPLEMENT: Improved Insertion Sort for problem 1.
*/
void insertion_sort_im(int** A, int n, int l, int r) {
int* key;
int pre_len;
int* pre_comp_len = new int[r-l+1]; // array to store the length of vectors
int i=0;
//precomputing length of vectors
for(int j=l; j<=r; j++) {
pre_comp_len[i++] = ivector_length(A[j], n);
}
//now apply insertion sort algorithm
for(int j=l+1; j<=r; j++){
key = A[j];
pre_len = pre_comp_len[j-l];
i = j-1;
while(i>=l && pre_comp_len[i-l]>pre_comp_len[j-l]) {
A[i+1] = A[i];
pre_comp_len[i+1-l] = pre_comp_len[i-l]; // updating pre_comp_len array as we are shifting vectors according to their length
i = i-1;
}
A[i+1] = key;
pre_comp_len[i-l+1] = pre_len;
}
}
/*
* TO IMPLEMENT: Improved Merge Sort for problem 2.
*/
// merge sort function
void merge(int** A, int* pre_comp_len, int n, int p, int m, int r, int start) {
int n1 = m - p + 1;
int n2 = r - m;
int** left_arr = new int *[n1]; // to store vectors of left side array
int** right_arr = new int*[n2]; // to store vectors of right side array;
int* left_len = new int[n1]; // to store precomputed lengths of vectors
int* right_len = new int[n2];
int i=0;
int temp = start;
for(int j = p; j<=m; j++) {
left_arr[i] = A[j];
left_len[i] = pre_comp_len[temp];
i++;
temp++;
}
i=0;
for(int j = m + 1; j <= r; j++) {
right_arr[i++] = A[j];
right_len[i] = pre_comp_len[temp];
i++;
temp++;
}
i=0;
int j=0;
int k = p;
// inserting vectors from right/left array at their correct position according to their length in sorted order
// and also updating pre computed length according to the position of vector
while(i if(left_len[i]<=right_len[j]) { A[k] = left_arr[i]; pre_comp_len[start] = left_len[i]; i++; } else { A[k] = left_arr[j]; pre_comp_len[start] = left_len[j]; j++; } start++; k++; } // inserting remaining vectors from leftt array at their correct position and also updating pre computed length according to the position of vector while(i A[k] = left_arr[i]; pre_comp_len[start] = left_len[i]; i++; k++; start++; } // inserting remaining vectors from right array at their correct position and also updating pre computed length according to the position of vector while(j A[k] = left_arr[j]; pre_comp_len[start] = left_len[j]; j++; k++; start++; } } void merge_sort_rec(int** A, int* pre_comp_len, int n, int p, int r, int start) { if(p // m is mid point int m = p + (r-p)/2; // divide array into 2 half merge_sort_rec(A, pre_comp_len, n, p, m, start); merge_sort_rec(A, pre_comp_len, n, m+1, r, start+(m-p+1)); // merge function to finalyy merge sorted vectors arrays merge(A, pre_comp_len, n, p, m, r, start); } } void merge_sort(int** A, int n, int p, int r){ int* pre_comp_len = new int[r-p+1]; // array to store the length of vectors int i=0; //precomputing length of vectors for(int j=p; j<=r; j++){ pre_comp_len[i++] = ivector_length(A[j], n); } //starting index of pre_comp_len int start = 0; // call recursive merge sort function merge_sort_rec(A, pre_comp_len, n, p, r, start); } /* * Simple function to check that our sorting algorithm did work * -> problem, if we find position, where the (i-1)-th element is * greater than the i-th element. */ bool check_sorted(int** A, int n, int l, int r){ for (int i = l+1; i <= r; i++) if (ivector_length(A[i-1], n) > ivector_length(A[i], n)) return false; return true; } /* * generate sorted/reverse/random arrays of type hw1type */ int** create_ivector(int n, int m){ int** iv_array; iv_array = new int*[m]; for (int i = 0; i < m; i++) iv_array[i] = new int[n]; return iv_array; } void remove_ivector(int** iv_array, int m){ for (int i = 0; i < m; i++) delete[] iv_array[i]; delete[] iv_array; } int** create_sorted_ivector(int n, int m){ int** iv_array; iv_array = create_ivector(n, m); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) iv_array[i][j] = (i+j)/n; return iv_array; } int** create_reverse_sorted_ivector(int n, int m){ int** iv_array; iv_array = create_ivector(n, m); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) iv_array[i][j] = ((m-i)+j)/n; return iv_array; } int** create_random_ivector(int n, int m, bool small){ random_generator rg; int** iv_array; iv_array = create_ivector(n, m); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { rg >> iv_array[i][j]; if (small) iv_array[i][j] %= 100; else iv_array[i][j] %= 65536; } return iv_array; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started