0

Estoy haciendo un merge sort con una clase llamada Monitor, utiliza un array de int y tiene los siguientes metodo: size, isEmpty, add, pop, peek. La cuestión es cuando hago el método merge sort me aparece el error "Stack Overflow Error", merge funciona bien, por lo menos paso el test.

public MonitorArray merge(MonitorArray left, MonitorArray right) {
    MonitorArray nuevaLista = new MonitorArray();

    while(!left.isEmpty() && !right.isEmpty()) {
        if(left.peek() <= right.peek())
            nuevaLista.add(left.pop());
        else
            nuevaLista.add(right.pop());
    }

    addAll(nuevaLista, left);
    addAll(nuevaLista, right);

    return nuevaLista;
}


private void addAll(MonitorArray nuevaLista, MonitorArray listaOrdenada) {
    while(!listaOrdenada.isEmpty()) {
        nuevaLista.add(listaOrdenada.pop());
    }
}


public void mergeSort(MonitorArray array) {
    if(array.size() <= 1);
    else {
        MonitorArray left  = firstHalf(array); 
        MonitorArray right = array;

        mergeSort(left);
        mergeSort(right);
        array = merge(left, right);
    }
}


private MonitorArray firstHalf(MonitorArray array) {
    MonitorArray half = new MonitorArray();
    int mid = array.size() / 2;
    while(array.size() >= mid) 
        half.add(array.pop());
    return half;
}

1 respuesta 1

0

Me parece que estás ejecutando tu método mergeSort indefinidamente a través de tu variable right, ya que el array que le pasas es siempre del mismo tamaño.

public void mergeSort(MonitorArray array) {
    if(array.size() <= 1);
    else {
        MonitorArray left  = firstHalf(array); 
        MonitorArray right = array;

        mergeSort(left);
        mergeSort(right); // Esta llamada te provoca el overflow
        array = merge(left, right);
    }
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.