Tri à bulles Manuellement une Liste Liée dans Java

Le problème, comme prévu, vient dans la méthode 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;                   
} 
}
}
}

Un problème mineur est juste de faire toujours exécuter le tri à bulles n*n fois. Il est effectivement mieux de vérifier s'il y a un changement entre toutes les paires dans la liste. Si c'était le cas, il est nécessaire d'exécuter à nouveau tous les cours de la liste; sinon, il n'y en a pas. Pensez à la marginales cas dans lequel une liste de 100 éléments est déjà trié quand sort() est appelé. Cela signifie que les noeuds de la liste serait courir plus de 10000 fois, même quand il n'y a effectivement rien à faire!

Le principal problème, cependant, est que vous échangez des pointeurs vers les nœuds de votre liste.

if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
} 

Si vous traduire currentNode par v[i] et prochaine par v[i - 1], comme si vous étiez le tri d'un tableau, cela ne serait. Cependant, vous êtes juste de changer les pointeurs que vous utilisez pour exécuter sur la liste, sans effet dans la liste elle-même. La meilleure solution (enfin, à condition que vous allez utiliser BubbleSort, qui est toujours la pire des solutions) serait d'échanger des données à l'intérieur des nœuds.

if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}

Toutefois, pour une question de l'illustration du concept, je vais proposer de changer les liens entre les nœuds. Ces pointeurs sont ceux qui, en fait, marque le tri dans la liste. Je parle de la nextNode attribut dans la Nœud classe.

Assez de chat, elle est ici:

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

L'explication pour un "double" code de gérer le nœud d'échange, c'est que, depuis que vous avez à changer les liens entre les nœuds, et ce est juste une seule liste liée, alors vous devez garder une trace de la précédente nœud (vous n'avez pas une tête de nœud, soit), dont le premier temps est 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;
}

Vous pouvez trouver le code dans IdeOne, ici: http://ideone.com/HW5zw7

Espère que cette aide.

vous pouvez écrire cette methode comme ceci:

class Node {
int data = 0;
Node next;
public Node(int data) {
this.data = data;
}
}
public void sort() {
Node current = head;
while (current != null) {
Node second = current.next;
while (second != null) {
if (current.data > second.data) {
int tmp = current.data;
current.data = second.data;
second.data = tmp;
}
second = second.next;
}
current = current.next;
}
}