Algorithme MergeSort - Java

Question

J'ai un problème avec l'implémentation de MergeSort en Java. Mon code ressemble à ceci et je n'ai aucune idée d'où j'ai fait une erreur.

public List sort(List list) { 
     return mergesort(list, 0, list.size() - 1); 
    } 

    private List mergesort(List list, int startIndex, int endIndex) { 
     if (startIndex == endIndex) { 
      List temp = new ArrayList(); 
      temp.add(list.get(0)); 
      return temp; 
     } 
     int splitIndex = ((startIndex + endIndex)/2); 
     List list1 = mergesort(list, startIndex, splitIndex); 
     List list2 = mergesort(list, (splitIndex + 1), endIndex); 
     return merge(list1, list2); 
    } 

    private List merge(List left, List right) { 
     List result = new ArrayList(); 
     ListIterator l = new ListIterator(left); 
     ListIterator r = new ListIterator(right); 
     l.first(); 
     r.first(); 
     while (!l.isDone() && !r.isDone()) { 
      if (comparator.compare(l.current(), r.current()) <= 0) { 
       result.add(l.current()); 
       l.next(); 
      } else { 
       result.add(r.current()); 
       r.next(); 
      } 
     } 
     while (!l.isDone()) { 
      result.add(l.current()); 
      l.next(); 
     } 
     while (!r.isDone()) { 
      result.add(r.current()); 
      r.next(); 
     } 
     return result; 

    } 

Pour tester mon algorithme je liste des personnes et les trier par ordre croissant par âge:

0. Jan, Kowalski, 60 
1. Jerzy, Adamczewski, 59 
2. Jan, Kowalski, 48 
3. Adam, Malysz, 40 
4. Bartosz, Tusk, 50 
5. Zygmunt, Jacewicz, 41 

Et la sortie ressemble à ceci:

0. Adam, Malysz, 40 
1. Adam, Malysz, 40 
2. Adam, Malysz, 40 
3. Adam, Malysz, 40 
4. Adam, Malysz, 40 
5. Adam, Malysz, 40 

Answer 1

Ce bloc ne semble pas droite.

if (startIndex == endIndex) { 
    List temp = new ArrayList(); 
    temp.add(list.get(0)); 
    return temp; 
} 

Peut-être que vous vouliez dire temp.add(list.get(startIndex));?

Answer 2

Il semble que vous fusionnez la fonction prend toujours les mêmes éléments les plus petits jusqu'à ce que les listes soient vides. Cela me donne l'impression qu'il y a un problème avec votre utilisation de "ListIterator :: current()" et "ListIterator :: next()".

Je ne suis pas très compétent avec ListIterators, donc ma proposition est d'opérer directement sur les listes. Cela simplifie également l'ajout des éléments restants des deux listes après l'un d'eux ne s'écoule d'éléments:

private List merge(List left, List right) { 
    List result = new LinkedList(); 

    while (!left.isEmpty() && !right.isEmpty()) { 
     if (comparator.compare(left.get(0), right.get(0)) <= 0) { 
      result.add(left.remove(0)); 
     } else { 
      result.add(right.remove(0)); 
     } 
    } 

    // add what is left in the lists 
    result.addAll(left); 
    result.addAll(right); 

    return result; 
} 

PS: Je n'ai pas vérifié ce code dans mon IDE, donc à utiliser avec précaution. Idéalement, vous devriez avoir des tests prêts à vérifier votre code - TDD est une très bonne approche que tout développeur de logiciel devrait suivre :)