Проблема реализации двусвязного списка QuickSort

Я реализовал классический двусвязный список:

class Node<T> {
    protected T data;

    protected Node<T> next, prev;
}

class DoublyLinkedList<T extends Comparable<T>> {
    protected Node<T> front;
    protected Node<T> back;
    protected int size;

    // methods
}

Теперь, чтобы иметь возможность сортировать его, я добавил следующие методы, реализующие классический алгоритм QuickSort:

public void sort(Comparator<T> comparator) {
    quickSort(front, back, comparator);
}

private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    if (end != null && begin != end && begin != end.next) {
        var temp = partition(begin, end, comparator);
        quickSort(begin, temp.prev, comparator);
        quickSort(temp.next, end, comparator);
    }
}

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            swapData(i, j);
        }
    }

    i = (i == null) ? begin : i.next;
    swapData(i, end);

    return i;
}

private void swapData(Node<T> a, Node<T> b) {
    var temp = a.data;
    a.data = b.data;
    b.data = temp;
}

Приведенный выше код выдает правильные результаты, однако я решил поменять местами узлы вместо данных, поэтому ввел следующие методы:

private void swapNodes(Node<T> a, Node<T> b) {
    if (a == b) return;

    if (a == null || b == null) {
        throw new NullPointerException();
    }

    if (a.next == b) {
        var before = a.prev;
        var after = b.next;

        link(before, b);
        link(b, a);
        link(a, after);
    } else if (b.next == a) {
        var before = b.prev;
        var after = a.next;

        link(before, a);
        link(a, b);
        link(b, after);
    } else {
        var aPrev = a.prev;
        var aNext = a.next;
        var bPrev = b.prev;
        var bNext = b.next;

        link(aPrev, b);
        link(b, aNext);
        link(bPrev, a);
        link(a, bNext);
    }
}

private void link(Node<T> a, Node<T> b) {
    if (a != null)
        a.next = b;
    else
        front = b;
    if (b != null)
        b.prev = a;
    else
        back = a;
} 

И добавил эти изменения в метод partition:

private Node<T> partition(Node<T> begin, Node<T> end, Comparator<T> comparator) {
    var pivot = end.data;

    var i = begin.prev;
    Node<T> next;

    for (var j = begin; j != end; j = next) {
        next = j.next;
        if (comparator.compare(j.data, pivot) < 0) {
            i = (i == null) ? begin : i.next;

            //swapData(i, j);
            swapNodes(i, j);
            i = j;
        }
    }

    i = (i == null) ? begin : i.next;
    //swapData(i, end);
    swapNodes(i, end);

    //return i;
    return end;
}

На данный момент код работает неправильно, и я не могу понять, почему. Что мне не хватает?

Редактировать:

Ожидаемый результат — это отсортированный ввод, которого во втором случае нет.

Пример:

Initial :[2, 9, 8, 3, 6, 2, 4, 1, 7, 6]
Expected:[1, 2, 2, 3, 4, 6, 6, 7, 8, 9]
Actual:  [1, 3, 2, 4, 2, 6, 9, 6, 7, 8]

Рабочий пример можно найти здесь: https://ideone.com/UQrzY1

Редактировать2:

Приведен более короткий пример и ввод/вывод.

Как это работает не корректно? Пожалуйста, дайте нам вход, фактический результат. Я предполагаю, что ожидаемый результат - это отсортированный ввод. Если бы вы предоставили нам полный код (включая импорт и основной код, который вы тестируете), я бы смог поместить его в отладчик.

NomadMaker 18.12.2020 20:21

@NomadMaker, спасибо, дополнил вопрос нужной информацией.

Trider 18.12.2020 21:00

В link(...) код для b == null неверен, в настоящее время это back = b, но должно быть back = a. Не уверен, что есть другие проблемы.

Marcono1234 18.12.2020 22:01

Код должен быть включен в вопрос в виде текста.

NomadMaker 18.12.2020 22:19

@ Marcono1234 Marcono1234, плохо, это опечатка, но в данном случае это не влияет на конечный результат.

Trider 19.12.2020 08:30
I decided to swap the nodes instead of data С какой стати? И почему без фиктивных/сторожевых узлов до и после списка? Как вы тестировали swapNodes()?
greybeard 19.12.2020 10:21

(begin != end.next заслуживает комментария.)

greybeard 19.12.2020 10:35

@greybeard, Why on earth? Если у меня есть итераторы, указывающие на определенные элементы списка, путем замены ссылок вместо фактических узлов во время сортировки я также изменю значения этих итераторов. Это нежелательное поведение. Например, так же работает std::list::sort().

Trider 19.12.2020 11:27

@greybeard And why without dummy/sentinel node(s) before and after the list? Я посчитал, что null достаточно для этой реализации.

Trider 19.12.2020 11:29

(Совершенно не связано: ваше изменение ideone для сортировки слиянием — прекрасный случай для включения важного материала в сообщения stackexchange.)

greybeard 19.12.2020 11:37

Не могли бы вы проверить и отладить логику parition(...)? Похоже, что локальные переменные, которые он использует, указывают на неправильные узлы после того, как узлы были заменены местами. Для некоторых входных значений это даже вызывает NullPointerException, например. для [2, 0, 1]

Marcono1234 19.12.2020 19:19
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
11
81
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Есть причина, по которой ошибку в «варианте swap-nodes» трудно определить:
Вы не поддерживаете отладку. Сделайте привычкой, чтобы занятия давали базовые toString():

/** doubly linked list node */
static class Node<T> {
    …
   /** constructs a <code>Node</code> given data, next & prev */
    public Node(T d, Node…
    
    @Override
    public String toString() {
        return String.valueOf(data);
    }
}

Со списками немного сложнее -

    /** Append string representations of <code>node</code>s 
     * <code>data</code> to <code>head</code>, following 
     * <code>next</code>s til <code>end</code> (or <code>null</code>)
     * (inclusive)
     */
    Appendable append(Node<T> node, final Node<T> end,
        CharSequence separator, Appendable head) {
        try {
            while (end != node) {
                head.append(String.valueOf(node));
                if (null == node
                    || null == (node = node.next) && null == end)
                    return head;
                head.append(separator);
            }
            head.append(String.valueOf(node));
        } catch (IOException e) {
            e.printStackTrace();
        }
        return head;
    }

    @Override
    public String toString() {
        return ((StringBuilder)append(front, null, ", ",
            new StringBuilder("["))).append(']').toString();
    }

    void bug(String label, Node<T> node, final Node<T> end) {
        System.out.append(((StringBuilder)append(node, end, ", ",
            new StringBuilder(label).append('('))).append(")\n"));
    }
    String verbose(Node<T> n) {
        return "+" + n.prev + "<-" + n + "->" + n.next;
    }
    
    private void quickSort(Node<T> begin, Node<T> end, Comparator<T> comparator) {
        bug("quicksort", begin, end);
        if (end != null && begin != end && begin != end.next) {
            Node<T> temp = partition(begin, end, comparator);
            System.out.println("begin: " + begin + ", temp: "
                + verbose(temp) + ", temp == end: " + (temp == end));
            quickSort(begin, temp.prev, comparator);
            bug("between", begin, temp.prev);
            quickSort(temp.next, end, comparator);
        }
    }

Используя приведенную выше навязчивую отладку, вы можете видеть, что end не остается концом правой части - как бы он был выбран опорным элементом в разделе Lomuto.
begin также не остается началом левой части - вам, похоже, нужен преемник предшественника begin и предшественник преемника end соответственно.
Получение вагона особых случаев без дозорных узлов до и после списка.

Другие вопросы по теме