MergeSort de inteiro recursivo em java

Java

13/04/2017

Fala galera, tudo certo com vocês?
Tenho um trabalho para fazer mas estou estagnado e não consigo resolver. Tampouco o professor me ajudou, então vim aqui em busca de outra ajuda.
Preciso fazer um MergeSort em java, recursivo e usando for, não while, partindo de um pseudocódigo que o professor disponibilizou.
Vocês poderiam me ajudar?
Grato.

Pseudocódigo e explicações:
Podemos então dividir ele em duas funções:
mergeSort ();
intercala();

O mergeSort é o responsável por fazer a divisão do vetor em vetores cada vez menores então ele tem a seguinte estrutura

mergeSort(vetor)
mergeSort(meio_vetor_1)
mergeSort(meio_vetor_2)
Intercala(meio_vetor_1, meio_vetor_2)

O intercala é o responsável por receber dois vetores, e retornar um vetor que possua os dados de ambos os vetores ordenado.

Mergesort (A, p, r)
se p < r então
q ← parte inteira de (p+r)/2
Mergesort (A, p, q)
Mergesort (A, q+1, r)
Intercala (A, p, q, r)

Intercala (A, p, q, r)
para i crescendo de p até q faça
B[i] ← A[i]
para j crescendo de q+1 até r faça
B[r+q+1−j] ← A[j]
i ← p
j ← r
para k crescendo de p até r faça
se B[i] ≤ B[j]
então A[k] ← B[i]
i ← i+1
senão A[k] ← B[j]
j ← j−1

A = vetor
P = início do vetor
Q = meio do vetor
R = fim do vetor

package mergesort;

import java.util.*;

public class MergeSort {
    
    int vetor[];
    int vetorB[];

    public static void main(String[] args) {
        int v[] = {6, 8, 2, 234, 23, 90, 97, 5};
        mergeSort(v, 0, 7);
        for (int z = 0; z < v.length; z++) {
            System.out.print(v[z] + ", ");
        }

    }

    public static void mergeSort(int vetor[], int inicio, int fim) {
        int meio;
        if (inicio < fim) {
            meio = (inicio + fim) / 2;
            mergeSort(vetor, inicio, meio);
            mergeSort(vetor, meio + 1, fim);
            intercala(vetor, inicio, meio, fim);
        }
    }

    public static void intercala(int vetor[], int inicio, int meio, int fim) {
        int i, j, k;
        int vetorB[] = new int[vetor.length];
        for (i = inicio; i < meio; i++) {
            vetorB[i] = vetor[i];
        }
        for (j = meio + 1; j < fim; j++) {
            vetorB[fim + meio + 1 - j] = vetor[j];
        }
        i = inicio;
        j = fim;
        for (k = inicio; k < fim; k++) {
            if (vetorB[i] <= vetorB[j]) {
                vetor[k] = vetorB[i];
                i = i + 1;
            } else {
                vetor[k] = vetorB[j];
                j = j - 1;
            }
        }
    }

}
André

André

Curtidas 0
POSTAR