Error in MergeSort sorting algorithm in Java

Question

Error in MergeSort sorting algorithm in Java

Navigation

#1 by (3 votes)
#2 by (1 votes)
#3 by (0 votes)

3

I was doing the MergeSort sorting algorithm in Java for study purposes and every time it runs it gives error. I have already reviewed the logic of the algorithm, I already replace the array of integers with a ArrayList , I already tried to change the parsing logic but nothing.

public static void main(String[] args) {

    ArrayList<Integer> array = new ArrayList<>();

    array.add(0);
    array.add(3);
    array.add(9);
    array.add(18);
    array.add(5);
    array.add(4);
    array.add(6);
    array.add(10);

    MergeSortClass.dividir( array, 0, array.size() );

    System.out.println( array.toString() );

}

public static void dividir( ArrayList<Integer> array, int inicio, int fim ){

    if( inicio < fim ){

        int meio = ( inicio + ( fim - 1 ) ) / 2;

        dividir( array, inicio, meio );
        dividir( array, meio + 1, fim );
        intercalar( array, inicio, meio, fim );

    }

} 

 public static void intercalar( ArrayList<Integer> array, int inicio, int meio, int fim ){

    int i = inicio;
    int j = meio + 1;

    ArrayList<Integer> temp = new ArrayList<>();

    while( i < j && j < fim ){

        if( array.get(i) < array.get(j) ){

            temp.add( array.get(i) );
            i++;

        } else {

            temp.add( array.get(j) );
            j++;

        }

    }

    //No caso da árvore recursiva estar desbalanceada e um dos lados terminar de comparar, o restante do outro lado será copiado para o array temporário

    while( i < j ){

        temp.add( array.get(i) );
        i++;

    }

    while( j < fim ){

        temp.add( array.get(j) );
        j++;

    }

    for( i = 0; i < temp.size(); i++ ){

        array.set( i + inicio, temp.get(i) );

        //código abaixo só para testar
        System.out.println( array.get(i + inicio) );

    }

    System.out.println("");

}

After I run the code, at the exit prompt along with the error message, I get this:

The array was almost completely ordered.

I want to know what the problem is with my code and what the possible solution is.

java algoritmo

asked by anonymous 20.03.2018 / 20:55

3 answers

1

The most important thing in situations like this is knowing how to read the error output. It is a very simple thing, but one that people generally ignore.

First, it should be noted that the error output is given in the form of a stack. This means that the first line of the error represents the last method that was called and where actually the exception occurred.

In your case, the error occurred in this section:

at java.util.ArrayList.rangeCheck(ArrayList.java:657)

rangeCheck is a method of class ArrayList that checks whether a given index ( int ) is within the bounds of the vector. If it is not, then an exception of type IndexOutOfBoundsException is thrown.

See here an implementation of the ArrayList for OpenJDK . The code snippet below is the rangeCheck method.

/**
 * Checks if the given index is in range.  If not, throws an appropriate
 * runtime exception.  This method does *not* check if the index is
 * negative: It is always used immediately prior to an array access,
 * which throws an ArrayIndexOutOfBoundsException if index is negative.
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

Continuing the error analysis ...

Note that rangeCheck is called by the java.util.ArrayList.set(ArrayList:448) method, another method of ArrayList . This, in turn, is called by the intercalar method of its MergeSortClass class. The intercalar is called by dividir and this by main .

The error, within intercalar , happens on this line:

array.set( i + inicio, temp.get(i) );

So this call to set is generating the IndexOutOfBoundsException exception. In short, the first parameter i+inicio is outside the vector limit (the internal structure of the ArrayList).

20.03.2018 / 21:26

0

Try MergeSortClass.dividir( array, 0, array.size()-1 ); because the size of ArrayList is the number of elements, but since it starts at 0 the last valid position is size-1.

20.03.2018 / 21:09

Tree menu - Error when selecting element (ul: onclick) PHP Return AD user

score 3 · Accepted Answer

Your program has some problems:

If you are working with lists, it does not make sense to call the list of array , since it is not an array but a list.

It is easier to work with fim being the last element of the list ( lista.size() - 1 ) and not the size of the list that would be the first item after the end of it. You even try to work with it being the first item after the end (using ( fim - 1 ) in the dividir method), but the code gets more complicated with that.

Your biggest problem was using i < j in the intercalar method. What you wanted was i <= meio . With i < j you end up adding the elements of the second half of each merge twice in the resulting draft list, and then at the time of copying it back to the original list, you bust the size of it.

Your dividir method should be called ordenar .

Prefer to use the types that are the most abstract possible, avoiding using too specific types. This way, in many places where you use ArrayList as type, you could simply use List .

See it fixed here:

import java.util.ArrayList;
import java.util.List;

class MergeSortClass {
    public static void main(String[] args) {
        List<Integer> lista = new ArrayList<>();
        lista.add(0);
        lista.add(3);
        lista.add(9);
        lista.add(18);
        lista.add(5);
        lista.add(4);
        lista.add(6);
        lista.add(10);
        ordenar(lista);
        System.out.println(lista.toString());
    }

    public static void ordenar(List<Integer> lista) {
        ordenar(lista, 0, lista.size() - 1);
    }

    private static void ordenar(List<Integer> lista, int inicio, int fim) {
        if (inicio >= fim) return;

        int meio = (inicio + fim) / 2;

        ordenar(lista, inicio, meio);
        ordenar(lista, meio + 1, fim);
        intercalar(lista, inicio, meio, fim);
    }

    private static void intercalar(List<Integer> lista, int inicio, int meio, int fim) {

        int i = inicio;
        int j = meio + 1;

        List<Integer> temp = new ArrayList<>(fim - inicio + 1);

        while (i <= meio && j <= fim) {
            int a = lista.get(i);
            int b = lista.get(j);
            if (a < b) {
                temp.add(a);
                i++;
            } else {
                temp.add(b);
                j++;
            }
        }

        while (i <= meio) {
            temp.add(lista.get(i));
            i++;
        }

        while (j <= fim) {
            temp.add(lista.get(j));
            j++;
        }

        for (int k = 0; k < temp.size(); k++) {
            lista.set(k + inicio, temp.get(k));
        }
    }
}

See here working on ideone.