The problem, as expected, comes in method sort():
public void sort() {
if (size > 1) {
for (int i = 0; i < size; i++ ) {
Node currentNode = head;
Node next = head.nextNode;
for (int j = 0; j < size - 1; j++) {
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
currentNode = next;
next = next.nextNode;
}
}
}
}
A minor problem is just do always execute the bubble sort n*n times. It is actually better check whether there was a change between any pair in the list. If it was, then there is the need to run again all over the list; if not, there isn’t. Think of the marginal case in which a list of 100 elements is already sorted when sort() is called. This means that nodes in the list would be run over for 10000 times, even when there is actually nothing to do!
The main problem, though, is that you are exchanging pointers to the nodes in your list.
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
If you translate currentNode by v[i] and next by v[i - 1], as if you were sorting an array, that would do. However, you are just changing pointers that you use to run over the list, without effect in the list itself. The best solution (well, provided you are going to use BubbleSort, which is always the worst solution) would be to exchange the data inside the nodes.
if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}
However, for a matter of illustration of the concept, I’m going to propose changing the links among nodes. These pointers are the ones which actually mark the sorting in the list. I’m talking about the nextNode attribute in the Node class.
Enough chat, here it is:
public void sort() {
if (size > 1) {
boolean wasChanged;
do {
Node current = head;
Node previous = null;
Node next = head.nextNode;
wasChanged = false;
while ( next != null ) {
if (current.data > next.data) {
/*
// This is just a literal translation
// of bubble sort in an array
Node temp = currentNode;
currentNode = next;
next = temp;*/
wasChanged = true;
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
previous = next;
next = current.nextNode;
} else {
previous = current;
current = next;
next = next.nextNode;
}
}
} while( wasChanged );
}
}
The explanation for a “double” code managing the node exchange is that, since you have to change the links among nodes, and this is just a single linked list, then you have to keep track of the previous node (you don’t have a header node, either), which the first time is head.
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
You can find the code in IdeOne, here: http://ideone.com/HW5zw7
Hope this helps.
