Tri manuel d'une liste chaînée en Java (lexicalement)

Question

J'implémente ma propre liste chaînée en Java. La classe de noeud a simplement un champ de chaîne appelé "nom" et un noeud appelé "lien". En ce moment j'ai une classe de pilote de test qui insère seulement plusieurs noms séquentiellement. Maintenant, j'essaie d'écrire une méthode de tri pour classer les nœuds par ordre alphabétique, mais j'ai un peu de mal avec ça. J'ai trouvé ce pseudo-code d'une bulle de la part de quelqu'un d'autre et j'ai essayé de l'implémenter, mais il ne triait pas complètement les entrées. Je ne suis pas vraiment sûr pourquoi. Toutes les suggestions sont appréciées!

private void sort() 
    { 
     //Enter loop only if there are elements in list 
     boolean swapped = (head != null); 

     // Only continue loop if a swap is made 
     while (swapped) 
     { 
      swapped = false; 

      // Maintain pointers 
      Node curr = head; 
      Node next = curr.link; 
      Node prev = null; 

      // Cannot swap last element with its next 
      while (next != null) 
      { 
       // swap if items in wrong order 
       if (curr.name.compareTo(next.name) < 0) 
       { 
        // notify loop to do one more pass 
        swapped = true; 

        // swap elements (swapping head in special case 
        if (curr == head) 
        { 
         head = next; 
         Node temp = next.link; 
         next.link = curr; 
         curr.link = temp; 
         curr = head; 
        } 
        else 
        { 
         prev.link = curr.link; 
         curr.link = next.link; 
         next.link = curr; 
         curr = next; 
        } 
       } 

       // move to next element 
       prev = curr; 
       curr = curr.link; 
       next = curr.link; 
      } 
     } 
    } 

Answer 1

J'ai passé quelques minutes à regarder votre code à la recherche d'erreurs mais n'en ai trouvé aucune.

Je dirais jusqu'à ce que quelqu'un de plus intelligent ou de plus dur travail arrive, vous devriez essayer de déboguer cela par vous-même. Si vous avez un EDI comme Eclipse, vous pouvez faire un seul pas dans le code tout en regardant les valeurs des variables; Sinon, vous pouvez insérer des instructions d'impression dans quelques endroits et vérifiez ce que vous voyez avec ce que vous attendiez.

---

MISE À JOUR Je

Je copiais votre code et testé. Mis à part le fait qu'il trie par ordre décroissant (ce qui n'est peut-être pas ce que vous vouliez), il a parfaitement fonctionné pour un échantillon de 0, 1 et 10 nœuds aléatoires. Alors, où est le problème?

MISE A JOUR II

deviner encore ce qu'on pourrait entendre par « il ne sort pas complètement les entrées. » Il est possible que vous attendiez un tri lexicographique (c'est-à-dire 'a' avant 'B'), et cela ne sort pas comme prévu pour les mots mixtes majuscules/minuscules. La solution dans ce cas est d'utiliser la méthode StringcompareToIgnoreCase(String str).

Answer 2

Ceci peut ne pas être la solution que vous cherchez, mais c'est simple et agréable. Peut-être que vous êtes paresseux comme je suis.

Étant donné que vos nœuds ne contiennent qu'un seul élément de données, vous n'avez pas vraiment besoin de remanier à nouveau vos nœuds; vous pouvez simplement échanger les valeurs sur les nœuds tout en laissant la structure de la liste elle-même intacte. De cette façon, vous êtes libre d'implémenter Bubble Sort tout simplement.

Answer 3

Vous devez utiliser les procédures de tri fournies par le langage.

try this tutorial.

Fondamentalement, vous avez besoin de votre classe d'éléments pour mettre en œuvre java.lang.Comparable, dans lequel vous simplement déléguer à obj.name.compareTo(other.name)

vous pouvez utiliser Collections.sort(yourCollection)

vous pouvez également créer un java.util.Comparator qui sait comment comparer vos objets

Answer 4

Pour obtenir de bonnes performances, vous pouvez utiliser Merge Sort. Sa complexité temporelle est O (n * log (n)) et peut être implémentée sans surcharge de mémoire pour les listes.

Le tri par bulles n'est pas une bonne méthode de tri. Vous pouvez lire le What is a bubble sort good for? pour plus de détails.

Answer 5

Cela peut être un peu trop tard. Je construirais la liste en insérant tout pour commencer car trier une liste chaînée n'est pas amusant.

Je suis sûr que votre professeur ou professeur ne veut pas que vous utilisiez la bibliothèque native de java. Cependant, cela étant dit, il n'y a pas de moyen vraiment rapide de recourir à cette liste.

Vous pouvez lire tous les nœuds dans l'ordre dans lequel ils se trouvent et les stocker dans un tableau. Triez le tableau, puis reconnectez les noeuds. Je pense que la complexité Big-Oh de ce serait O (n^2) donc en réalité une sorte de bulle avec une liste liée est suffisante

Answer 6

J'ai fait un tri de fusion sur la liste des liens simples et ci-dessous est le code.

public class SortLinkedList { 

public static Node sortLinkedList(Node node) { 

    if (node == null || node.next == null) { 
     return node; 
    } 
    Node fast = node; 
    Node mid = node; 
    Node midPrev = node; 
    while (fast != null && fast.next != null) { 
     fast = fast.next.next; 
     midPrev = mid; 
     mid = mid.next; 
    } 
    midPrev.next = null; 
    Node node1 = sortLinkedList(node); 
    Node node2 = sortLinkedList(mid); 
    Node result = mergeTwoSortedLinkedLists(node1, node2); 
    return result; 
} 

public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) { 
    if (null == node1 && node2 != null) { 
     return node2; 
    } else if (null == node2 && node1 != null) { 
     return node1; 
    } else if (null == node1 && null == node2) { 
     return null; 
    } else { 

     Node result = node1.data <= node2.data ? node1 : node2; 
     Node prev1 = null; 
     while (node1 != null && node2 != null) { 
      if (node1.data <= node2.data) { 
       prev1 = node1; 
       node1 = node1.next; 
      } else { 
       Node next2 = node2.next; 
       node2.next = node1; 
       if (prev1 != null) { 
        prev1.next = node2; 
       } 
       node1 = node2; 
       node2 = next2; 
      } 
     } 
     if (node1 == null && node2 != null) { 
      prev1.next = node2; 
     } 
     return result; 
    } 
} 

public static void traverseNode(Node node) { 
    while (node != null) { 
     System.out.print(node + " "); 
     node = node.next; 
    } 
    System.out.println(); 

} 

public static void main(String[] args) { 
    MyLinkedList ll1 = new MyLinkedList(); 

    ll1.insertAtEnd(10); 
    ll1.insertAtEnd(2); 
    ll1.insertAtEnd(20); 
    ll1.insertAtEnd(4); 
    ll1.insertAtEnd(9); 
    ll1.insertAtEnd(7); 
    ll1.insertAtEnd(15); 
    ll1.insertAtEnd(-3); 
    System.out.print("list: "); 
    ll1.traverse(); 
    System.out.println(); 
    traverseNode(sortLinkedList(ll1.start)); 

} 

}

La classe Node:

public class Node { 
int data; 
Node next; 

public Node() { 
    data = 0; 
    next = null; 
} 

public Node(int data) { 
    this.data = data; 
} 

public int getData() { 
    return this.data; 
} 

public Node getNext() { 
    return this.next; 
} 

public void setData(int data) { 
    this.data = data; 
} 

public void setNext(Node next) { 
    this.next = next; 
} 

@Override 
public String toString() { 
    return "[ " + data + " ]"; 
} 

}

La classe MyLinkedList:

public class MyLinkedList { 
Node start; 

public void insertAtEnd(int data) { 
    Node newNode = new Node(data); 
    if (start == null) { 
     start = newNode; 
     return; 
    } 
    Node traverse = start; 
    while (traverse.getNext() != null) { 
     traverse = traverse.getNext(); 
    } 
    traverse.setNext(newNode); 
} 

public void traverse() { 
    if (start == null) 
     System.out.println("List is empty"); 
    else { 
     Node tempNode = start; 
     do { 
      System.out.print(tempNode.getData() + " "); 
      tempNode = tempNode.getNext(); 
     } while (tempNode != null); 
     System.out.println(); 
    } 
} 

}