Requirement: Based on the code provided below, implement the merge sort algorithm to rearrange an array with N elements. While running the algorithm, print array A after each merge of two subarrays.
Input
Output
Input
10
800 728 703 671 628 625 518 508 392 331
Output
[ 728 800 ] 703 671 628 625 518 508 392 331
[ 703 728 800 ] 671 628 625 518 508 392 331
703 728 800 [ 628 671 ] 625 518 508 392 331
[ 628 671 703 728 800 ] 625 518 508 392 331
628 671 703 728 800 [ 518 625 ] 508 392 331
628 671 703 728 800 [ 508 518 625 ] 392 331
628 671 703 728 800 508 518 625 [ 331 392 ]
628 671 703 728 800 [ 331 392 508 518 625 ]
[ 331 392 508 518 625 628 671 703 728 800 ]
I'm having trouble finding a way to print out the remaining elements of the array after each merge. this is my code, hope any one can help me:
#include <iostream>
using namespace std;
void printArray(int arr[], int start, int end) {
cout << "[ ";
for (int i = start; i <= end; ++i) {
cout << arr[i];
if (i < end) {
cout << " ";
}
}
cout << " ] ";
}
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int* L = new int[n1];
int* R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
// In ra mảng sau mỗi lần trộn hai mảng con
printArray(arr, left, right);
cout << endl;
delete[] L;
delete[] R;
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
int N;
cin >> N;
int* arr = new int[N];
for (int i = 0; i < N; ++i)
cin >> arr[i];
mergeSort(arr, 0, N - 1);
delete[] arr;
return 0;
}
After running my code, this is the output of example :
[ 728 800 ]
[ 703 728 800 ]
[ 628 671 ]
[ 628 671 703 728 800 ]
[ 518 625 ]
[ 508 518 625 ]
[ 331 392 ]
[ 331 392 508 518 625 ]
[ 331 392 508 518 625 628 671 703 728 800 ]
As you can see, this is not contain the entire array but only print the elements already be merged, i want it look like the output example.
The underlying problem is that printArray is not designed to print the entire array. It only knows to print the elements between start and end. It has no idea to print the elements before start, and the elements after end.
For printArray to print all of the elements, you must pass the information to printArray that there are N elements in total, not just start and end. Once that's done, then all printArray needs to do is
start.start and end.end.The simplest way to do this is add an extra argument to the merge, mergeSort and printArray function that denotes the number of elements in the array:
void merge(int arr[], int left, int mid, int right, int numElements)
void mergeSort(int arr[], int left, int right, int numElements)
void printArray(int arr[], int start, int end, int numElements)
In main, you would call mergeSort like this:
mergeSort(arr, 0, N - 1, N);
and all the calls to mergeSort, merge and printArray would pass the value of numElements, eventually ending up in printArray.
Then for printArray, the function is very simple:
void printArray(int arr[], int start, int end, int numElements) {
for (int i = 0; i < start; ++i)
std::cout << arr[i] << " ";
cout << "[ ";
for (int i = start; i <= end; ++i) {
cout << arr[i];
if (i < end) {
cout << " ";
}
}
cout << " ] ";
for (int i = end + 1; i < numElements; ++i)
std::cout << arr[i] << " ";
}