forked from MahaKoala/cracking-the-coding-interview
-
Notifications
You must be signed in to change notification settings - Fork 3
/
11.1-sortingAndSearching.cxx
41 lines (34 loc) · 936 Bytes
/
11.1-sortingAndSearching.cxx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <assert.h>
#include <iostream>
using namespace std;
/*
* 11.1
* You are given two sorted arrays, A and B, where A has a large
* enough buffer at the end to hold B. Write a method to merge B into
* A in sorted order.
*/
void mergeArrays(int a[], int b[], int aSize, int bSize) {
int iA = aSize - 1;
int iB = bSize - 1;
int im = aSize + bSize - 1;
while (iA >= 0 && iB >= 0) {
if (a[iA] > b[iB]) {
a[im] = a[iA];
iA--;
} else {
a[im] = b[iB];
iB--;
}
im--;
}
}
void test11_1() {
int a[] = {0, 1, 2, 2, 3, 4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int b[] = {2, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9};
int sorted[] = {0, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 8, 8, 9};
mergeArrays(a, b, 7, 11);
for (int i = 0; i < 18; i++) {
assert(a[i] == sorted[i]);
}
cout << "11.1 passed!" << endl;
}