Необычная ошибка сортировки слиянием

У меня необычная проблема. Я реализовал сортировку слиянием и столкнулся со следующим: метод работает правильно, за исключением последнего прохода. При наличии случайного массива Integer в качестве входных данных возвращается массив Integer, в котором первая половина и вторая половина сортируются отдельно. Слияние работает правильно, за исключением последнего прохода. После нескольких часов возни с отладчиком я понял, что «точка упоминания» всегда оценивается как false на последнем проходе, хотя это не должно основываться на значениях.

Вся помощь приветствуется.

public static Integer[] mergeSort(Integer[] input)
{
    if (input.length == 1) return input;

    int splittle = input.length / 2;

    Integer[] first = new Integer[splittle];
    Integer[] second = new Integer[input.length - splittle];

    for (int i = 0; i < splittle; i++)
        first[i] = input[i];
    for (int i = splittle; i < input.length; i++)
        second[i - splittle] = input[i];

    mergeSort(first);
    mergeSort(second);

    LinkedList<Integer> returner = new LinkedList<Integer>();

    PriorityQueue<Integer> sFirst = new PriorityQueue<Integer>();
    PriorityQueue<Integer> sSecond = new PriorityQueue<Integer>();

    for (int i = 0; i < first.length; i++)
        sFirst.offer(first[i]);
    for (int i = 0; i < second.length; i++)
        sSecond.offer(second[i]);

    // while (!sFirst.isEmpty()&&!sSecond.isEmpty())
    // returner.add((sFirst.peek()>=sSecond.peek() ?
    // sFirst.poll():sSecond.poll()));

    // expansion of line above for debugging purposes

    while (!sFirst.isEmpty() && !sSecond.isEmpty())
    {
        int temp = 0;

        if (sFirst.peek() >= sSecond.peek())
            temp = sFirst.poll(); // Mention point
        else
            temp = sSecond.poll();
        returner.add(temp);

    }

    while (!sFirst.isEmpty())
        returner.add(sFirst.poll());
    while (!sSecond.isEmpty())
        returner.add(sSecond.poll());

    return returner.toArray(new Integer[0]);
}

java mergesort
person Techrocket9    schedule 12.05.2011    source источник
comment
Вероятно, вам следует просто использовать int[] и позволить Java заниматься автоупаковкой, когда придет время использовать LinkedList и PriorityQueue.   -  person Matt Ball    schedule 12.05.2011

Ответы (2)


arrow_upward
5
arrow_downward

Проблема внутри вашего кода while и более конкретна, когда вы используете метод poll().

Ты имел:

if (sFirst.peek() >= sSecond.peek())
    temp = sFirst.poll(); // Mention point
else
    temp = sSecond.poll();

когда вы должны были:

if (sFirst.peek() >= sSecond.peek())
    temp = sSecond.poll(); // Mention point
else
    temp = sFirst.poll();

Раньше при таком вводе:

sFirst = [-9, 1, 2, 9, 89] and  sSecond =  [4, 15, 18, 23, 31, 123]

у вас было бы if (-9 >= 4), что было бы ложным, поэтому вы бы сделали часть else, которая была бы poll() из sSecond, хотя вы должны были бы poll() из sFirst. -9 должен быть первым элементом, добавляемым в список returner, а не 4.

Кроме того (на основе ответа ccoakley) изменение, вы должны использовать возвращаемый массив из mergeSort(), что можно легко сделать:

first = mergeSort(first);
second = mergeSort(second);

Вы можете посмотреть рабочий код (после изменений) здесь.

person insumity    schedule 12.05.2011
comment
Спасибо, это устранило проблему. - person Techrocket9; 13.05.2011

arrow_upward
3
arrow_downward

Я надеюсь, что это поможет: почему у вас есть функция mergeSort, возвращающая массив Integer, но затем не использующая возвращаемое значение в вызове функций mergeSort(first) и mergeSort(second)?

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

person ccoakley    schedule 12.05.2011