MergeSort, logic problem

2

Gentlemen, I'm having a problem with my MergeSort sorting algorithm, I feel the problem is in logic.

Merge Code:

static void mergesort(int[] x,int inicio,int fim){
        if(inicio<fim){
            int meio;
            meio=((inicio+fim)/2);
            mergesort(x,inicio,meio);
            mergesort(x,meio+1,fim);
            intercala(x,inicio,fim,meio);
        }
    }
    static void intercala(int x[],int inicio,int fim,int meio){
        int inicio_vetor1,inicio_vetor2,poslivre,i;
        int[] aux = new int[10];
        inicio_vetor1 = inicio;
        inicio_vetor2 = meio+1;
        poslivre = inicio;
        while(inicio_vetor1<=meio && inicio_vetor2<=fim){
            if(x[inicio_vetor1]<=x[inicio_vetor2]){
                aux[poslivre]=x[inicio_vetor1];
                inicio_vetor1+=1;
            }
            else{
                aux[poslivre]=x[inicio_vetor2];
                inicio_vetor2++;
            }
            poslivre+=1;
        }
        for(i = inicio_vetor1;i<=meio;i++){
            aux[poslivre]=x[inicio_vetor1];
            poslivre+=1;
        }
        for(i = inicio_vetor2;i<=fim;i++){
            aux[poslivre]=x[inicio_vetor2];
            poslivre+=1;
        }
        for(i =inicio;i<=fim;i++){
            x[i]=aux[i];
        }
    }

Function main :

public static void main(String[] args) {
    // TODO code application logic here
    int[] x = {6,2,1,3,0};
    mergesort(x,0,x.length-1);
    for(int y:x) System.out.println(y);
}

Output:

0
1
2
2
3

As you can see, the algorithm commands, but it is swallowing numbers and I can not find the error.

    
asked by anonymous 04.11.2017 / 03:37

1 answer

2

There are two errors. The first is here:

       int[] aux = new int[10];

It was meant to be new int[x.length] !

But your big mistake is here:

        for(i = inicio_vetor1;i<=meio;i++){
            aux[poslivre]=x[inicio_vetor1];
            poslivre+=1;
        }
        for(i = inicio_vetor2;i<=fim;i++){
            aux[poslivre]=x[inicio_vetor2];
            poslivre+=1;
        }

Note that you are not using the i variables inside the loops! It should be this:

        for(i = inicio_vetor1;i<=meio;i++){
            aux[poslivre]=x[i];
            poslivre+=1;
        }
        for(i = inicio_vetor2;i<=fim;i++){
            aux[poslivre]=x[i];
            poslivre+=1;
        }

With these changes, it works just fine.

See here working on ideone - I also took advantage of and arranged some code formatting details.

    
04.11.2017 / 05:06