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

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

3 голосов
/ 12 мая 2011

У меня необычная проблема. Я реализовал сортировку слиянием и обнаружил следующее: метод работает правильно, за исключением последнего прохода. Если в качестве входных данных использовать случайный массив 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]);
}

Ответы [ 2 ]

5 голосов
/ 12 мая 2011

Проблема заключается в вашем 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);

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

3 голосов
/ 12 мая 2011

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

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

...