la fusion de deux listes

Question

Salut J'ai vraiment problème avec la fusion de deux listes dans le code tel que mergesort voici mon code et il lancera une exception, mais je ne sais pas pourquoi! S'il vous plaît aidez-moi

private void solve(List<Point> upperHull) { 
    list = upperHull; 
    number = upperHull.size(); 
    dcHullForUpperHull(0, number-1); 
} 

private void dcHullForUpperHull(int low, int high) { 
    /*System.out.println(list);*/ 
    if (low<high) { 
     // Get the index of the Object which is in the middle 
     int mid = (low + high)/2; 
     // Sort the left side of the list 
     dcHullForUpperHull(low, mid); 

     // Sort the Right side of the list 
     dcHullForUpperHull(mid +1 , high); 

     //combine them both. 

     mergeForUpperHull(low, mid, high); 
    } 
} 

private void mergeForUpperHull(int low, int mid, int high) { 


    List<Point> auxiliaryList = new ArrayList<Point>(); 
    List<Point> auxiliaryListTow = new ArrayList<Point>(); 
    for (int i = low; i <= mid; i++) { 
    auxiliaryList.add(upperHull.get(i)); 
    } 
    for (int i = mid + 1; i <= high; i++) { 
    auxiliaryListTow.add(upperHull.get(i)); 
    } 

    System.out.println(auxiliaryList.get(mid)); 
    System.out.println(auxiliaryList.get(low)); 
    } 

l'exception ci-dessous pour la ligne: System.out.println(auxiliaryList.get(mid)); exception:

X :166.0 Y: 104.0angle0.0 
X :166.0 Y: 104.0angle0.0 
Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: Index: 2, Size: 1 
    at java.util.ArrayList.RangeCheck(ArrayList.java:547) 
    at java.util.ArrayList.get(ArrayList.java:322) 
    at ConvexHull.DCHullVersion.mergeForUpperHull(DCHullVersion.java:142) 
    at ConvexHull.DCHullVersion.dcHullForUpperHull(DCHullVersion.java:126) 
    at ConvexHull.DCHullVersion.dcHullForUpperHull(DCHullVersion.java:122) 

Answer 1

for (int i = mid + 1; i <= high; i++) { 
    auxiliaryListTow.add(upperHull.get(i)); 
} 

Je suppose que c'est la ligne provoquant l'ex ception? Essayez de chaning i = < élevé i < haute

Il n'a rien à voir avec votre fonction .. le problème est que you'r essayant d'accéder au champ d'un tableau qui n'est pas présente.

En Java, les tableaux commencent par un index 0.

acclamations

Answer 2

Si je ne me trompe pas, si la liste est de taille, permet de dire, puis 3 éléments ou plus la méthode

private void mergeForUpperHull(int low, int mid, int high) 

seront appelés, à un moment donné, avec le bas et milieu paramètres tous les deux ayant la même valeur, supérieure à 0. Cela causera certainement l'exception que vous rencontrez lorsque vous essayez de le faire System.out.println(auxiliaryList.get(mid));
Essayez de déboguer votre code, ligne par ligne, il pourrait vous aider.
Je ne suis que des curiosités, pourquoi faites-vous cela? Votre extrait de code laisse beaucoup à deviner et pour être honnête, cela n'a pas beaucoup de sens (du moins pas pour moi).

Answer 3

La raison pour laquelle vous obtenez une exception IndexOutOfBoundsException est que vous créez un nouveau List<Point> auxiliaryList chaque fois que mergeForUpperHull est appelée. Ainsi, dans le scénario où, low = mid = 2, vous n'aurez ajouté (ajouté) qu'un seul élément dans la nouvelle liste auxiliaire, qui ne correspondra pas à l'index que vous essayez d'obtenir à partir de la liste auxiliaryList dans le système.

Il existe d'autres problèmes avec le code, mais je suppose que vous êtes simplement en mode Bloc-notes. Mais pour vous donner une direction valide, je n'utiliserais pas deux listes auxiliaires dans une méthode de fusion, mais j'utiliserai la liste principale pour effectuer des opérations de comparaison et d'échange. Souvenez-vous que si vous ajoutez simplement à une liste auxiliaire pour chaque opération de fusion, vous aurez plus de données dans la liste finale à la suite de bulles provenant des appels dcHullForUpperHull récursifs.

Pour être plus précis, vous finirez par avoir (Log2(size of list)+1)*(size of list) éléments de la fusion que vous effectuez (en supposant que vous ne créez pas une marque nouvelle liste à chaque fois)

Divide and Conquer algorithmes sont grands exercices d'apprentissage, donc je ne cracherai pas le code complet ici, mais ce qui précède devrait être direction décente pour que vous complétiez le tri ci-dessus fusionné