Я реализовал классический двусвязный список:
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, спасибо, дополнил вопрос нужной информацией.
В link(...)
код для b == null
неверен, в настоящее время это back = b
, но должно быть back = a
. Не уверен, что есть другие проблемы.
Код должен быть включен в вопрос в виде текста.
@ Marcono1234 Marcono1234, плохо, это опечатка, но в данном случае это не влияет на конечный результат.
I decided to swap the nodes instead of data
С какой стати? И почему без фиктивных/сторожевых узлов до и после списка? Как вы тестировали swapNodes()
?
(begin != end.next
заслуживает комментария.)
@greybeard, Why on earth?
Если у меня есть итераторы, указывающие на определенные элементы списка, путем замены ссылок вместо фактических узлов во время сортировки я также изменю значения этих итераторов. Это нежелательное поведение. Например, так же работает std::list::sort()
.
@greybeard And why without dummy/sentinel node(s) before and after the list?
Я посчитал, что null
достаточно для этой реализации.
(Совершенно не связано: ваше изменение ideone для сортировки слиянием — прекрасный случай для включения важного материала в сообщения stackexchange.)
Не могли бы вы проверить и отладить логику parition(...)
? Похоже, что локальные переменные, которые он использует, указывают на неправильные узлы после того, как узлы были заменены местами. Для некоторых входных значений это даже вызывает NullPointerException
, например. для [2, 0, 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
соответственно.
Получение вагона особых случаев без дозорных узлов до и после списка.
Как это работает не корректно? Пожалуйста, дайте нам вход, фактический результат. Я предполагаю, что ожидаемый результат - это отсортированный ввод. Если бы вы предоставили нам полный код (включая импорт и основной код, который вы тестируете), я бы смог поместить его в отладчик.