Question

Data Structure in C++

Using namespace std;
In this assignment you will implement a variation of Mergesort known as a bitonic mergesort, recursively.
In a normal mergesort, the input to the merge step is a single array, which is divided into two sections, both sorted ascending. We assume that the first half (0 up to but not including size/2) is the first section and the second half (size/2 up to but not including size) is the second section.
In a bitonic mergesort, we use the same arrangement, except that the second sequence is sorted in descending order: the first half goes up, and then the second half goes down. This means that when we are doing a merge, sometimes we want to merge the results into ascending order, while other times we want to merge into descending order (depending on which "half" of the final array the result will end up in). So we add another parameter, to describe the direction the output should be sorted into:
void merge(int* input, int size, int* output, bool output_asc);
If output_asc == true then after the merge output should contain size elements, sorted in ascending order. If output_asc == false, output should contain the elements sorted in descending order.
The other thing we glossed over in class was the allocation of the temporary space needed by the algorithm. It’s quite wasteful to allocate it in each recursive call: it would be better to allocate all the necessary space up front, and then just pass a pointer to it. In order to do this, we’ll write the recursive mergesort function in a helper function which will preallocate the space needed for the results:
int* mergesort(int* input, int size) {
int* output = new int[size];
mergesort(input, size, output, true);
return output;
}
void mergesort(int *input, int size, int* output, bool output_asc) {
// Your implementation here
}
The parameter output_asc serves the same purpose here as for merge: it tells the function that we want the output to be sorted ascending.
Interface
You must implement the functions
void merge(int* input, int size, int* output, bool output_asc);
int* mergesort(int* input, int size);
void mergesort(int *input, int size, int* output, bool output_asc);
Download a template .cpp file containing these definitions. This file is also available on the server in /usr/local/class/src.
merge must run in O(n) time with n= size. mergesort (both versions) must run in O(nlogn) time, and must use O(n) space. If you allocate any space other than the output array, you should free it before your function returns.
The test runner will test each function separately, and then in combination. It checks the result of sorting to make sure that it’s actually sorted, and then nothing is missing or added from the original (unsorted) sequence.

Answer 1

The code .cpp is available bellow

#include<iostream>

using namespace std;

//declaring variables

void merge(int* ip, int sz, int* opt, bool opt_asc); //merging

int* mergesort(int* ip, int sz);

void mergesort(int *ip, int sz, int* opt, bool opt_asc);

void merge(int* ip, int sz, int* opt, bool opt_asc)

{

int s1 = 0;

int mid_sz = sz / 2;

int s2 = mid_sz;

int e2 = sz;

int s3 = 0;

int end3 = sz;

int i, j;

if (opt_asc==true)

{

i = s1;

j = e2 - 1;

while (i < mid_sz && j >= s2)

{

if (*(ip + i) > *(ip + j))

{

*(opt + s3) = *(ip + j);

s3++;

j--;

}

else if (*(ip + i) <= *(ip + j))

{

*(opt + s3) = *(ip + i);

s3++;

i++;

}

}

if (i != mid_sz)

{

while (i < mid_sz)

{

*(opt + s3) = *(ip + i);

s3++;

i++;

}

}

if (j >= s2)

{

while (j >= s2)

{

*(opt + s3) = *(ip + j);

s3++;

j--;

}

}

}

else

{

i = mid_sz - 1;

j = s2;

while (i >= s1 && j <e2)

{

if (*(ip + i) > *(ip + j))

{

*(opt + s3) = *(ip + i);

s3++;

i--;

}

else if (*(ip + i) <= *(ip + j))

{

*(opt + s3) = *(ip + j);

s3++;

j++;

}

}

if (i >= s1)

{

while (i >= s1)

{

*(opt + s3) = *(ip + i);

s3++;

i--;

}

}

if (j != e2)

{

while (j < e2)

{

*(opt + s3) = *(ip + j);

s3++;

j++;

}

}

}

for (i = 0; i < sz; i++)

*(ip + i) = *(opt + i);

}

int* mergesort(int* ip, int sz)

{

int* opt = new int[sz];

mergesort(ip, sz, opt, true);

return opt;

}

void mergesort(int *ip, int sz, int* opt, bool opt_asc)

{

if (sz > 1)

{

int q = sz / 2;

mergesort(ip, sz / 2, opt, true);

mergesort(ip + sz / 2, sz - sz / 2, opt + sz / 2, false);

merge(ip, sz, opt, opt_asc);

}

}

int main()

{

int arr1[12] = { 5, 6, 9, 8,25,36, 3, 2, 5, 16, 87, 12 };

int arr2[14] = { 2, 3, 4, 5, 1, 20,15,30, 2, 3, 4, 6, 9,12 };

int arr3[10] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };

int *opt;

cout << "Arays after sorting:\\";

cout << "Array 1 : ";

opt = mergesort(arr1, 12);

for (int i = 0; i < 12; i++)

cout << opt[i] << " ";

cout << endl;

cout << "Array 2 : ";

opt = mergesort(arr2, 14);

for (int i = 0; i < 14; i++)

cout << opt[i] << " ";

cout << endl;

cout << "Array 3 : ";

opt = mergesort(arr3, 10);

for (int i = 0; i < 10; i++)

cout << opt[i] << " ";

cout << endl;

return 0;

}