erreur java de tri de fusion (apprentissage à partir de edX.org
C'est le tableau que je veux fusionner tri, situé dans static void main:
int[] lst = {6, 5, 4, 7, 2, 1, 9}
Voici la fonction mergeSort:
static int[] mergeSort(int[] lst) {
int n = lst.length;
int[] left;
int[] right;
// create space for left and right subarrays
if (n % 2 == 0) {
left = new int[n/2];
right = new int[n/2];
}
else {
left = new int[n/2];
right = new int[n/2+1];
}
// fill up left and right subarrays
for (int i = 0; i < n; i++) {
if (i < n/2) {
left[i] = lst[i];
}
else {
right[i-n/2] = lst[i];
}
}
// **ERROR B**
// recursively split and merge
left = mergeSort(left);
right = mergeSort(right);
// merge
return merge(left, right);
}
Voici la fonction merge:
// the function for merging two sorted arrays
static int[] merge(int[] left, int[] right) {
// create space for the merged array
int[] result = new int[left.length+right.length];
// running indices
int i = 0;
int j = 0;
int index = 0;
// add until one subarray is deplete
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[index++] = left[i++];
{ // **ERROR A** [ see description below ]
else {
result[index++] = right[j++];
}
}
// add every leftover elelment from the subarray
while (i < left.length) {
result[index++] = left[i++];
}
// only one of these two while loops will be executed
while (j < right.length) {
result[index++] = right[j++];
}
return result;
}
ERREUR d'UN: j'obtiens une erreur ici en disant else avec pas si. Si je supprime l'accolade sous result[index++] = left[i++], elle s'exécutera et me donnera une erreur de: Exception in thread "main" java.lang.StackOverflowError et pointera l'erreur vers le code ci-dessus qui est l'ERREUR B.
2 answers
C'est très proche. Tout ce qui vous manque, c'est votre cas de base récursif dans votre tri de fusion, qui, comme écrit, se récurse sans cesse jusqu'à ce que la pile explose. Il dit: "Liste de 0 ou 1 éléments? Garder le fractionnement!"
La réalisation clé de Merge sort est qu'un tableau à un seul élément ou un tableau à zéro élément est déjà trié. C'est le cas de base. Coder comme suit:
if (n <= 1) {
return lst; // this list is already sorted
}
Quant à votre autre erreur, c'est juste une parenthèse dépareillée et la réparer devrait vous donner le erreur de débordement de pile, qui était votre problème principal et n'était pas lié au problème de parenthèse. Voici le code de travail complet:
class Main {
public static void main(String[] args) {
int[] lst = {6, 5, 4, 7, 2, 1, 9};
System.out.println(java.util.Arrays.toString(mergeSort(lst)));
}
static int[] mergeSort(int[] lst) {
int n = lst.length;
if (n <= 1) {
return lst;
}
int[] left;
int[] right;
if (n % 2 == 0) {
left = new int[n/2];
right = new int[n/2];
}
else {
left = new int[n/2];
right = new int[n/2+1];
}
for (int i = 0; i < n; i++) {
if (i < n / 2) {
left[i] = lst[i];
}
else {
right[i-n/2] = lst[i];
}
}
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length+right.length];
int index = 0;
int i = 0;
int j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[index++] = left[i++];
}
else {
result[index++] = right[j++];
}
}
while (i < left.length) {
result[index++] = left[i++];
}
while (j < right.length) {
result[index++] = right[j++];
}
return result;
}
}
Voici un repl.
Votre méthode mergeSort() manque une condition. Si votre liste n'a qu'une longueur de 1, vous devez arrêter d'essayer de la diviser davantage et la renvoyer pour fusionner.