Trier par fusion: Pourquoi ma méthode de fusion ajoute-t-elle seulement un numéro à la file d'attente?

Question

Voici mon code:

void mergeHelper(Queue<T> input1, Queue<T> input2, Queue<T> output) { 
      // TODO 4 
      if(!input1.isEmpty()) 
      { 
       T ip1 = input1.dequeue(); 
       if(!input2.isEmpty()) 
       { 
        T ip2 = input2.dequeue(); 
        if(ip1.compareTo(ip2)<=0) 
         output.enqueue(ip1); 
        else 
         output.enqueue(ip2); 
       } 
       else 
       { 
        output.enqueue(ip1); 
       } 
       mergeHelper(input1, input2, output); 
      } 
      else if(!input2.isEmpty()) 
      { 
       T ip2 = input2.dequeue(); 
       if(!input1.isEmpty()) 
       { 
        T ip1 = input1.dequeue(); 
        if(ip1.compareTo(ip2)<=0) 
         output.enqueue(ip1); 
        else 
         output.enqueue(ip2); 
       } 
       else 
       { 
        output.enqueue(ip2); 
       } 
       mergeHelper(input1, input2, output); 
      } 

    } 

Voici un pilote temporaire:

public class MergeDriver { 

    public static void main(String[] args) { 

     MergeSorter<Integer> ms = new MergeSorter<>(); 
     Queue<Integer> one = new Queue<>(); 
     Queue<Integer> two = new Queue<>(); 
     one.enqueue(new Integer(2)); 
     two.enqueue(new Integer(1)); 
     Queue<Integer> res = ms.merge(one, two); 
     System.out.println("The size of res is: "+ res.size()); 
     System.out.println("The value stored is: "); 
     while(!res.isEmpty()) 
      System.out.println((int)res.dequeue()); 
    } 

} 

Seulement 1 est ajouté à la file d'attente de sortie et le reste est pas.

La taille de la file d'attente résultante est toujours une et le seul élément le plus petit est ajouté à la file d'attente. Qu'est-ce que je fais mal?

Answer 1

Votre algorithme est incorrect car il supprime les deux éléments pour les comparer, mais n'en ajoute qu'un seul à la sortie.

Vous pouvez résoudre ce problème en utilisant la méthode peek() avant de procéder à la mise en file d'attente, en comparant les résultats, puis en supprimant la file d'attente du plus petit des deux éléments et en le déplaçant dans la sortie.