Tri d'une LinkedList

Question

Je n'arrive pas à trier ma liste chaînée. Est-ce que quelqu'un peut m'aider et me dire ce que je fais de mal? J'ai besoin de trier et de le mettre dans une liste. et Si vous pouvez me donner quelques pointeurs pour imprimer la liste à la fin avec une nouvelle méthode public void print().

public class SortedLinkedList<T extends Comparable<? super T>> 
      extends LinkedList<T> 
    { 
     private LinkedList<T> list; //the sorted list 

     //the constructor 
     public SortedLinkedList(LinkedList<T> in) 
     { 
      if(in.isEmpty()) 
      { 
       System.out.println("Empty list"); 
      } 
      else 
      { 
       LinkedList<T> first = new LinkedList<T>(in.subList(0, in.size()/2)); 
       LinkedList<T> second = new LinkedList<T>(in.subList(in.size ()/2,in.size())); 
       LinkedList<T> sortList = new LinkedList<T>(); 

       int i = 0; 
       int j = 0; 
       while(i<first.size() && j<second.size()) 
       { 
        if(first.get(i).equals(second.get(j)) || first.get(i).compareTo(second.get(j))<0) 
        { 
          sortList.add(first.get(i)); 
          i++; 
        } 
        else 
        { 
          sortList.add(second.get(j)); 
          j++; 
        } 
        if(i == first.size()) 
        { 
          for(int k = j; k<second.size(); k++) 
          { 
           sortList.add(second.get(k)); 
          } 
        } 
        else 
        { 
          for(int x = i; x<first.size(); x++) 
          { 
           sortList.add(first.get(x)); 
        } 
       } 

      } 
     } 
    } 
    } 

Answer 1

Avant d'écrire votre propre tri, essayez Collections.sort. Si vous avez besoin de votre propre ordre de tri, utilisez un comparateur. Quelques ajouts: Dans la plupart des cas, LinkedLists est la mauvaise structure de données - en particulier s'il est nécessaire de la trier.

Answer 2

Il semble que vous essayez d'implémenter Mergesort. Si mon hypothèse est correcte, vous oubliez d'appeler mergesort sur les sous-listes. L'algorithme brut, dans le code pseudo, serait:

mergesort(list) 
    left = list[:len(list/2)] 
    right = list[len(list/2):] 

    mergesort(left) 
    mergesort(right) 

    merge(left, right) # that would be your while loop 

Edit: Sauf si vous avez vraiment besoin d'implémenter votre propre algorithme, je suggère d'utiliser Collections.sort, de l'API Java.