1. Introduction
"Merging Arrays II" is an interesting variant of array merging problems. It involves merging two sorted arrays when one array, X[], has vacant cells (represented by 0s) and is large enough to hold all elements from the second array, Y[]. The challenge lies in merging them into X[] while maintaining sorted order and utilizing vacant cells.
Problem
Given two sorted integer arrays X[] and Y[], where X[] has a size m (including n vacant cells represented by 0s) and Y[] has a size n, merge Y[] into X[] in a sorted manner. The resulting array X[] should contain all elements from both arrays, sorted in ascending order.
2. Solution Steps
1. Move all non-zero elements of X[] to the end of the array.
2. Use two pointers: one for the non-zero elements of X[] and one for Y[].
3. Compare elements from the end of the non-zero section of X[] and from Y[].
4. Place the larger element at the end of X[] and move the pointers accordingly.
5. Continue this process until all elements from Y[] are merged into X[].
3. Code Program
#include <iostream>
#include <vector>
using namespace std;
// Function to merge Y[] into X[]
void merge(int X[], int Y[], int m, int n) {
// Move non-zero elements of X[] to the end
int k = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (X[i] != 0) {
X[k--] = X[i];
}
}
// Merge elements of Y[] and X[]
int i = n; // Index of the non-zero start of X[]
int j = 0; // Index of Y[]
k = 0; // Index for the resultant X[]
// Merge until Y[] is exhausted
while (j < n) {
if (i < m && X[i] <= Y[j]) {
X[k++] = X[i++];
} else {
X[k++] = Y[j++];
}
}
}
int main() {
int X[] = {0, 2, 0, 3, 0, 5, 6, 0, 0};
int Y[] = {1, 8, 9, 10, 15};
int m = sizeof(X) / sizeof(X[0]);
int n = sizeof(Y) / sizeof(Y[0]);
merge(X, Y, m, n);
// Print merged array
for (int i = 0; i < m; i++) {
cout << X[i] << " ";
}
cout << endl;
return 0;
}
Output:
1 2 3 5 6 8 9 10 15
Explanation:
The program starts by moving all non-zero elements of X[] to its end. This creates space at the beginning of X[] to merge elements from Y[].
Using two pointers, it compares elements from Y[] and the non-zero section of X[], placing the smaller of the two elements into the correct position in X[].
This process continues until all elements of Y[] are merged into X[], resulting in a sorted merged array.
The approach efficiently utilizes the available space in X[] and merges the arrays in place.
Comments
Post a Comment