# Doubly Linked List QuickSort Implementation Problem

I’ve implemented a classic Doubly Linked List:

```class Node<T> {
protected T data;

protected Node<T> next, prev;
}

protected Node<T> front;
protected Node<T> back;
protected int size;

// methods
}
```

Now in order to be able to sort it I then added the following methods implementing a classic QuickSort algorithm:

```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;
}
```

The code above produces correct results, however, I decided to swap the nodes instead of data, so I introduced these methods:

```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;

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

} else {
var aPrev = a.prev;
var aNext = a.next;
var bPrev = b.prev;
var bNext = b.next;

}
}

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;
}
```

And added these changes to the `partition` method:

```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;
}
```

At this point the code is not working correctly and I can’t figure out why. What am I missing?

Edit:

The expected output is the sorted input which in the second case it is not.

Example:

```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]
```

A working example can be found here: https://ideone.com/UQrzY1

Edit2:

Provided a shorter example and input/output.

There is a reason the bug in the “swap-nodes variant” is hard to pin down:
You don’t support debugging. Make it a habit to have classes provide a basic `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);
}
}
```

It’s a bit more complicated with the lists –

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

@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);
}
}
```

Using above intrusive debugging, you can see that `end` doesn’t stay the end of the right part – how would it being picked the pivot element in a Lomuto partition.
Nor does `begin` stay the beginning of the left part – you’d seem to need successor of `begin`‘s predecessor and predecessor of `end`‘s successor respectively.
Ensuing a wagonload of special cases without sentinel nodes before and after the list.

User contributions licensed under: CC BY-SA
3 People found this is helpful