Алгоритм MergeSort — Java

У меня проблема с реализацией MergeSort в Java. Мой код выглядит так, и я понятия не имею, где я сделал ошибку.

public List sort(List list) {
        return mergesort(list, 0, list.size() - 1);
    }

    private List mergesort(List list, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            List temp = new ArrayList();
            temp.add(list.get(0));
            return temp;
        }
        int splitIndex = ((startIndex + endIndex) / 2);
        List list1 = mergesort(list, startIndex, splitIndex);
        List list2 = mergesort(list, (splitIndex + 1), endIndex);
        return merge(list1, list2);
    }

    private List merge(List left, List right) {
        List result = new ArrayList();
        ListIterator l = new ListIterator(left);
        ListIterator r = new ListIterator(right);
        l.first();
        r.first();
        while (!l.isDone() && !r.isDone()) {
            if (comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }
        while (!l.isDone()) {
            result.add(l.current());
            l.next();
        }
        while (!r.isDone()) {
            result.add(r.current());
            r.next();
        }
        return result;

    }

Чтобы проверить свой алгоритм, я использовал список людей и отсортировал их по возрасту:

0. Jan, Kowalski, 60
1. Jerzy, Adamczewski, 59
2. Jan, Kowalski, 48
3. Adam, Malysz, 40
4. Bartosz, Tusk, 50
5. Zygmunt, Jacewicz, 41

И вывод выглядит так:

0. Adam, Malysz, 40
1. Adam, Malysz, 40
2. Adam, Malysz, 40
3. Adam, Malysz, 40
4. Adam, Malysz, 40
5. Adam, Malysz, 40

java sorting algorithm mergesort
person DominikS    schedule 15.04.2017    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Этот блок выглядит неправильно.

if (startIndex == endIndex) {
    List temp = new ArrayList();
    temp.add(list.get(0));
    return temp;
}

Возможно, вы имели в виду temp.add(list.get(startIndex)); ?

person phatfingers    schedule 15.04.2017

arrow_upward
0
arrow_downward

Кажется, что функция слияния всегда принимает одни и те же наименьшие элементы, пока списки не станут пустыми. Это создает у меня впечатление, что есть проблема с использованием вами "ListIterator::current()" и "ListIterator::next()".

Я не очень хорошо разбираюсь в ListIterators, поэтому я предлагаю работать непосредственно со списками. Это также упрощает добавление оставшихся элементов двух списков после того, как в одном из них закончатся элементы:

private List merge(List left, List right) {
    List result = new LinkedList();

    while (!left.isEmpty() && !right.isEmpty()) {
        if (comparator.compare(left.get(0), right.get(0)) <= 0) {
            result.add(left.remove(0));
        } else {
            result.add(right.remove(0));
        }
    }

    // add what is left in the lists
    result.addAll(left);
    result.addAll(right);

    return result;
}

PS: я не проверял этот код в своей IDE, поэтому используйте его с осторожностью. В идеале у вас должны быть готовые тесты, которые проверяют ваш код — TDD — действительно хороший подход, которому должен следовать каждый разработчик программного обеспечения :)

person Ray    schedule 15.04.2017