Что не так с моим слиянием двух отсортированных массивов?

Question

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);
    }

Я получаю вывод как 1 2 3 7 8 0 вместо 1 2 2 3 7 8 с добавлением и без добавления третьего условия.

Answer 1

Вы начинаете e слишком низко, оно должно быть m + n + 1.

Подумайте об этом, для двух трехэлементных массивов m и n - это два. Это означает, что вы начнете с четырех с m + n, тогда как с результатом из шести элементов вы должны начать с пяти.

Это относительно простая ошибка, связанная с ошибкой.

Вы также можете решить другую проблему потери значений, когда они равны, просто игнорируя равенство. Выберите a, если оно больше или равно, в противном случае выберите b.

И ваша логика продолжения цикла неверна, что вы увидите, если сначала исчерпаете a (используйте a = {2, 2, 3} и b = {1, 7, 8}, чтобы понять, что я имею в виду). Вы продолжите, только если у a и b остались элементы. Вы должны продолжить, пока либо из них имеют оставшиеся элементы.

Вы можете исправить это, оставив этот цикл как есть, но добавив два других цикла (только один из которых на самом деле будет делать что-либо), чтобы исчерпать другой список.

В качестве поддержки я предоставляю следующий код на C (поскольку я быстрее использую его, чем Java, но сама процедура сортировки должна быть практически идентична):

#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--];
}

И тестовый код:

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;
}

Вывод этого:

1 2 2 3 7 8

как и ожидалось.

---

И эквивалентный код Java:

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--];
    }

вместе с набором тестов:

    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]);
    }
}  

---

На самом деле, поскольку вы в любом случае пишете в a, вы можете фактически пропустить этот средний цикл (while (m >= 0)). Это потому, что в этой ситуации вы просто переносите элементы на себя.

Я оставлю это, так как это важно, если массив, в который вы пишете, не на месте, но вы можете удалить его, если хотите для своей конкретной ситуации.

Answer 2

Это ваше еще заявление. Элементы из a и b одинаковы, поэтому вы должны вставить оба, и порядок не имеет значения. Вместо этого вы только вставляете значение из b. Или вы можете изменить второе условие и изменить его, как показано ниже:

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--;
            }

        }
    }