Блог

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

 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
}
 

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

 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 amp;amp; begin != end amp;amp; 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:

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

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

 /** doubly linked list node */
static class Node<T> {
    …
   /** constructs a <code>Node</code> given data, next amp; 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) amp;amp; 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 amp;amp; begin != end amp;amp; 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 это не остается концом правой части — как бы он выбирал элемент pivot в разделе Lomuto.
Также не begin остается начало левой части — вам, похоже, нужен преемник begin предшественника и предшественник end преемника соответственно.
В результате возникает вагон особых случаев без контрольных узлов до и после списка.