9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order


#include <iostream>
#include <vector>

using namespace std;

/*
Missed some basic knowledge!
1.[] operator (and at(), front(), back()) ACCESS and MODIFY an element, BUT they cannot spawn an element for you, this is not perl!!!
2. resize() can shrink and expand a container. When shrinking, every iterator in the new scope are valid, BUT expand invalidates all iterators!!!

Solution is better organized.
*/
void merge(vector<int>& A, vector<int>& B)
{
    if (B.size() == 0) return;
    
    if (A.size() == 0 && (A = B, 1)) return;
    
    int sizeA = A.size(), sizeB = B.size();
    int size = sizeA + sizeB;
    
    A.resize(size);
    
    vector<int>::iterator Aptr = A.begin() + sizeA - 1;
    vector<int>::iterator Bptr = B.end() - 1;
    
    while (size > 0)
    {
        if (*Aptr > *Bptr)
        {
            A[size - 1] = *Aptr;
            
            //from the solution, these segment of data is already in place, no movement is needed
            if (Aptr == A.begin())
            {
                --size;
                while (size > 0)
                {
                    A[size - 1] = *Bptr;
                    --Bptr;
                    --size;
                }
                return;
            }
            --Aptr;
        }
        else
        {
            A[size - 1] = *Bptr;
            if (Bptr == B.begin())
            {
                --size;
                while (size > 0)
                {
                    A[size - 1] = *Aptr;
                    --Aptr;
                    --size;
                }
                return;
            }
            --Bptr;
        }
        --size;
    }
}

int main()
{   
    vector<int> A;
    for (int i = 0; i < 10; i+=2)
    {
        A.push_back(i);
    }
    
    vector<int> B;
    for (int i = 1; i < 10; i+=2)
    {
        B.push_back(i);
    }
    
    merge(A, B);
    
    for (vector<int>::const_iterator cit = A.begin(); cit != A.end(); ++cit)
    {
        cout << *cit << endl;
    }
    return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s