Question

in C++

Description In this lab assignment your job is to implement Merge-Sort. See the textbook for the algorithm and its pseudo-code. You must output the given elements integers) in non- decreasing order. Input structure The input starts with an integer number which indicates the number of elements, n. Then, the elements follow, one per line. Output structure Output the elements in non-decreasing order. Each element must be fol- lowed by ;. Examples of input and output: Input ܗ ܗ ܚ ܟܬ ܝܪ ܗ ܛ Output 1;2;3;4;5; 6;

Answer 1

#include<stdio.h>

#include<stdlib.h>

#include <cstdlib>

#include <iostream>

#include <vector>

#define RAN_MAX 327

using namespace std;

//functions

void mergeSort(int *v, int p, int q, int r);

void merge(int *v, int p, int r);

int MAX_VAL = 65536;

void merge(int *v, int p, int q, int r) {

int j, i;

int k = 0;

int n1 = q - p + 1;

int n2 = r - q;

int L[n1+1], R[n2+1];

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

L[i] = v[p + i];

for (j = 0; j < n2; j++)

R[j] = v[q +1 + j];

i = j = 0;

k = p;

while (i < n1 && j < n2)

{

if ((L[i] <= R[j]))

{

v[k] = L[i];

i++;

}

else

{

v[k] = R[j];

j++;

}

k++;

}

while (i < n1)

{

v[k] = L[i];

i++;

k++;

}

while (j < n2)

{

v[k] = R[j];

j++;

k++;

}

}

void mergeSort(int *v, int p, int r) {

int q;//middle

if (p < r) {

q = (p + r) / 2;

mergeSort(v, p, q);

mergeSort(v, q + 1, r);

merge(v, p, q, r);

}

}

void printArray(int *arr, int n) {

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

cout<< arr[i]<<";";

}

int main()

{

int n;

cin>>n;

int *a = new int[n];

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

cin>>a[i];

mergeSort(a,0,n-1);

printArray(a, n);

}

============================
SEE OUTPUT

Filesd main.cpp saved clang version 7.0.0-3-ubuntuo.18.04 > clang++-7 -pthread -o main main.c ? ./main main.cpp 64 void printArray(int *arr, int n) { for (int i = 0; i<n; i++) cout<< arr[i]<<";"; Ровно л о 70 } 1;2;3;4;5;6;} | 75 int main() 77 78 81 82 int n; cin>>n; int *a = new int[n]; for(int i=0;i<n;++i) cin>>a[i]; 84 86 88 mergeSort(a,0,n-1); printArray(a, n);

PLEASE COMMENT if there is any concern.

=============================