CODEWITHSUNDEEP
javaarraysmerge
noMAD
noMAD

Reputation: 7844

What's wrong with my merging of two sorted arrays?

void sort(int a[], int b[], int m, int n)
    {
        int e = m + n;
        while(m >=0 && n >=0)
        {
            if(a[m] > b[n])
            {
                a[e] = a[m];
                m--;
                e--;
            }
            else if(a[e] < b[n])
            {
                a[e] = b[n];
                n--;
                e--;
            }
            else
            {
                a[e] = b[n];
                e--;
                n--;
                m--;
            }
        }
    }

public static void main(String[] args) {
        SortSorted obj = new SortSorted();
        int a[] = new int [6];
        int b[] = new int [3];
        a[0] = 1;
        a[1] = 2;
        a[2] = 3;
        b[0] = 2;
        b[1] = 7;
        b[2] = 8;
        obj.sort(a,b, 2, 2);
    }

I get the output as 1 2 3 7 8 0 instead of 1 2 2 3 7 8 with and without adding the 3rd else condition.

Upvotes: 0

Views: 197

Answers (2)

paxdiablo
paxdiablo

Reputation: 882028

You start e too low, it should be m + n + 1.

Think about it, for two three-element arrays, m and n are both two. That means that you'll start at four with m + n whereas, with a six-element result, you should be starting at five.

This is a relatively simple off-by-one error.

You can also fix the other problem of losing values when they're equal by simply ignoring the equality. Choose a if it's greater than or equal, otherwise choose b.

And your loop continuation logic is wrong, which you would see if you exhausted a first (use a = {2, 2, 3} and b = {1, 7, 8} to see what I mean). You only continue if both a and b have elements left. You should continue while either of them have elements left.

You can fix this by leaving that loop as-is but adding two other loops (only one of which will actually do anything) to exhaust the other list.

As support, I provide the following C code (since I'm faster with that than Java, but the sort routine itself should be pretty much identical):

#include <stdio.h>

void sort (int a[], int b[], int m, int n) {
    // Start at correct offset for target array.

    int e = m + n + 1;

    // Until one list empty, choose the correct value.

    while (m >= 0 && n >= 0)
        if (a[m] >= b[n])
            a[e--] = a[m--];
        else
            a[e--] = b[n--];

    // If b was empty, just transfer a.

    while (m >= 0)
        a[e--] = a[m--];

    // If a was empty, just transfer b.

    while (n >= 0)
        a[e--] = b[n--];
}

And some test code:

int main(void) {
    int a[6] = {2,2,3};
    int b[] = {1,7,8};
    sort (a, b, 2, 2);
    printf ("%d %d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4], a[5]);
    return 0;
}

The output of this is:

1 2 2 3 7 8

as expected.

And the equivalent Java code:

class Test {
    static void sort (int a[], int b[], int m, int n) {
        // Start at correct offset for target array.

        int e = m + n + 1;

        // Until one list empty, choose the correct value.

        while (m >= 0 && n >= 0)
            if (a[m] >= b[n])
                a[e--] = a[m--];
            else
                a[e--] = b[n--];

        // If b was empty, just transfer a.

        while (m >= 0)
            a[e--] = a[m--];

        // If a was empty, just transfer b.

        while (n >= 0)
            a[e--] = b[n--];
    }

along with its test suite:

    static public void main(String[] args) {
        int a[] = new int[6];
        a[0] = 2; a[1] = 2; a[2] = 3;
        int b[] = new int[3];
        b[0] = 1; b[1] = 7; b[2] = 8;
        sort (a, b, 2, 2);
        for (int i = 0; i < 6; i++)
            System.out.println (a[i]);
    }
}

In fact, since you're writing to a anyway, you can actually leave out that middle loop (the while (m >= 0) one). That's because, in that situation, you're simply transferring elements to themselves.

I'll leave it in since it becomes important if the array you're writing to is not in-place but you can remove it if you wish for your particular situation.

Upvotes: 1

jlewis42
jlewis42

Reputation: 933

It's your else statement. The elements from a and b are the same, so you should insert both and the order doesn't matter. Instead you only insert the value from b. Or you can chuck the second condition and change it as below: 

void sort(int a[], int b[], int m, int n)
    {
        int e = m + n + 1;
        while(m >=0 && n >=0)
        {
            if(a[m] > b[n])
            {
                a[e] = a[m];
                m--;
                e--;
            }
            else 
            {
                a[e] = b[n];
                n--;
                e--;
            }

        }
    }

Upvotes: 0

Related Questions