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;

}