Le problème que je rencontre est que j'essaie de faire exécuter mon implémentation de tri de fusion, mais j'obtiens toujours une erreur d'exception qui indique que l'index Array est hors limites. Il s'agit d'une erreur d'exécution car je suis capable de compiler le programme sans problème et il fonctionnera jusqu'à ce qu'il atteigne mon appel de tri de fusion. Une chose que j'ai essayée était de changer l'une de mes variables pour qu'elle corresponde à l'autre dans la méthode de fusion (int k = 0; // ligne 39). Quand j'ai fait cela, le code s'est exécuté, cependant, le tableau trié par fusion n'était pas correct. J'ai même essayé de déboguer le code, mais je n'ai pas vu de problème avec celui-ci. Voici mon code:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 15 at HW3.merge(HW3.java:60) at HW3.merge_sort(HW3.java:17) at HW3.main(HW3.java:160) //this line is where I call the method within the main
Et voici l'erreur:
public static void merge_sort(int A[], int l, int r){
if(l < r){
int m = (l + r)/2;
merge_sort(A, l, m);
merge_sort(A, m + 1, r);
merge(A, l, m, r);//Line17
}
}
public static void merge(int A[], int l, int m, int r){
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int [n1];
int R[] = new int [n2];
for(int i = 0; i < n1; i++){
L[i] = A[l + i];
}
for(int j = 0; j < n2; j++){
R[j] = A[m + 1 + j];
}
int i = 0;
int j = 0;
int k = 1; //line39
while(i < n1 && j < n2){
if(L[i] <= R[j]){
A[k] = L[i];
i++;
}
else{
A[k] = R[j];
j++;
}
k++;
}
while(i < n1){
A[k] = L[i];
i++;
k++;
}
while(j < n2){
A[k] = R[j]; //line60
j++;
k++;
}
}
Je comprends que cela signifie que le tableau sort du définir la taille de 15 mais je ne sais pas comment résoudre ce problème. J'ai essayé d'examiner des problèmes similaires, mais je n'ai pas vu de solution au problème que je rencontrais.
3 Réponses :
Comment appelez-vous votre fonction? Assurez-vous que vous utilisez object.sort (arr, 0, A.length-1); dans main lorsque vous passez la valeur maximale de l'index du tableau.
Donc je l'appelle juste comme merge_sort (array, 0, 14);
Tout le reste est bien dans votre code.
Sauf pour cette ligne
int k = 1; // line39
cela devrait être k = l (La lettre 'L' en petites majuscules)
Vous pouvez vous référer au code suivant
public class StackExchange {
public static
void mergeSort(int A[], int l , int r) {
if (l < r) {
int m = (l+r)/2;
mergeSort(A, l , m);
mergeSort(A, m+1, r);
merge(A, l, m, r);
}
}
private static void merge(int[] A, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0 ; i < n1; i++) {
L[i] = A[l+i];
}
for (int j = 0 ; j < n2; j++) {
R[j] = A[m + 1 + j];
}
int i = 0, j = 0 , k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
A[k] = L[i];
i++;
} else {
A[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
A[k] = L[i];
i++;
k++;
}
while (j < n2) {
A[k] = R[j];
j++;
k++;
}
}
public static void main (String...s) {
int array[] = new int[] {12, 21, 32, 36, 14, 10, 11, 5, 55, 16, 31, 7, 57, 89, 78};
mergeSort(array, 0, array.length - 1);
printArray(array);
}
private static void printArray(int array[]) {
for (int i : array) {
System.out.println(i + " -- ");
}
}
}
ressembler à un problème peut être à la ligne 60 A [k] parce que k index commence à 1.
vous pouvez comparer ici geeksforgeeks.org/merge-sort
Je l'avais changé pour commencer à 0, mais le tableau ne s'est pas imprimé correctement. Voici un exemple: Voici la liste saisie: [12, 21, 32, 36, 14, 10, 11, 5, 55, 16, 31, 7, 57, 89, 78] Veuillez saisir une valeur que vous souhaitez rechercher pour dans la liste. 5 Tableau trié rapide: [5, 7, 10, 11, 12, 14, 16, 21, 31, 32, 36, 55, 57, 78, 89] Tableau trié par fusion: [31, 31, 32, 32, 36 , 36, 55, 55, 57, 57, 78, 78, 89, 21, 89] Recherche binaire => Élément introuvable. Recherche d'interpolation => Élément introuvable.
remplacez celui-ci int m = l + (r-l) / 2;
Pouvez-vous expliquer pourquoi? Je suis un peu confus
Je viens de faire ce changement et c'est toujours la même erreur.
référez-vous à ce lien geeksforgeeks.org/merge-sort ils vous donnent une bonne explication.
continuons cette discussion dans le chat .