Dúvida em recursividade2 | Programação | Alura

Queria saber se o meu passo a passo do Merge-Sort e dos Merge feitos a mão estão corretos. Tenho uma dúvida: Tem alguma fórmula para determinar o número de trocas ocorridas em um array decrescente com 6 elementos? Ex: quantas trocas ocorrem para ordenar esse array decrescente: A[5,4,3,2,1,0]? No meu código deu 16 trocas, porém quando faço a mão dá 9 trocas.

Código:

public static  void mergeSort(int[] A, int p, int r) {
        
        if (p < r) {
            int q = (p + r) / 2; // Em Java, a divisão de inteiros já arredonda para baixo
            System.out.println("+Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge-Sort1(A, " +p +", " +q +")");
            cont++;
            mergeSort(A, p, q);
            System.out.println("-Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge-Sort2(A, " +(q+1) +", " +r +")");
            cont++;
            mergeSort(A, q + 1, r);
            System.out.println(";Passo" +cont + "\nP = " +p + "\nQ = " +q + "\nR = " +r +"\nMerge(A, " +p + ", " +q + ", " +r + ")");
            cont++;
            merge(A, p, q, r);
        }
    }
    
    public static void merge(int[] A, int p, int q, int r) {
        System.out.println("Passo 1 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int n1 = q - p + 1;
        int n2 = r - q;
        System.out.println("P = " + p);
        System.out.println("Q = " + q);
        System.out.println("R = " + r);
        System.out.println("N1 = " + n1);
        System.out.println("N2 = " + n2);
        // Criando arrays temporários
        System.out.println("Passo 2 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = A[p + i];
            System.out.println("L["+i+"] = " +L[i]);}
        
        System.out.println("Passo 3 - Merge(A, " +p + ", " +q + ", " +r + ")");
        for (int j = 0; j < n2; j++) {
            R[j] = A[q + 1 + j];
            System.out.println("R["+j+"] = " +R[j]);}
        
        System.out.println("Passo 4 - Merge(A, " +p + ", " +q + ", " +r + ")");
        int i = 0, j = 0, k = p;
        System.out.println("i = " +i + "\nj = " +j + "\nk = " +k);

        System.out.println("Passo 5 - Merge(A, " +p + ", " +q + ", " +r + ")");
        mostrarArray(A);
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                System.out.println(A[k] + " Troca com " +R[j]);
                System.out.println("A = [" +A[k] + "(idx " + k + ")" + ", " +R[j] + "]");
                A[k] = R[j];
                System.out.println("A = [" +A[k] + "(idx " + k + ")" + ", " +R[j] + "]");
                mostrarArray(A);
                j++;
              
            }
            k++;
            numeroTrocas++;
        }
        
        System.out.println("Passo 6 - Merge(A, " +p + ", " +q + ", " +r + ")");
        System.out.println("i = " +i + "\nj = " +j + "\nk = " +k);
        mostrarArray(A);
        while (i < n1) {
            System.out.println(A[k] + " Troca com " +L[i]);
            System.out.println("A = [" +A[k] + "(idx " + k + ") " + ", " +L[i] + "]");
            A[k] = L[i];
            System.out.println("A = [" +A[k] + "(idx " + k + ") " + ", " +L[i] + "]");
            mostrarArray(A);
            i++;
            k++;
            numeroTrocas++;
        }

        System.out.println("Passo 7 - Merge(A, " +p + ", " +q + ", " +r + ")");
        while (j < n2) {
            A[k] = R[j];
            j++;
            k++;
            numeroTrocas++;
        }
    }

Trocas feitas a mão:

https://drive.google.com/file/d/1AtmyymyQp2q3aaPyG3cvjGtZSGlA73s0/view?usp=sharing

Passo a passo do Merge-Sort:

https://drive.google.com/drive/folders/1VHeDUj5EM_ImQMxgkSbH8_So4iA7hTkV?usp=drive_link

Passo a passo de todos os Merge:

https://drive.google.com/drive/folders/1Y1L345mJ308bdA0YfunV3a1o06Ne1W1e?usp=drive_link

Olá, Luidi!

O seu código parece estar correto, mas para verificar se o número de trocas está correto, vamos analisar o exemplo que você deu: o array decrescente A[5,4,3,2,1,0].

No Merge-Sort, o número de trocas é determinado pelo número de inversões no array. Uma inversão ocorre quando um elemento maior é colocado antes de um elemento menor durante a ordenação. Vamos analisar o passo a passo do Merge-Sort para o array A[5,4,3,2,1,0]:

No primeiro passo, o array é dividido em duas partes: A[5,4,3] e A[2,1,0]. Nesse caso, não há inversões.
No segundo passo, cada parte é dividida novamente: A[5] e A[4,3]; A[2] e A[1,0]. Nesse caso, também não há inversões.
No terceiro passo, ocorre o merge das partes. Ao comparar o elemento 5 com o elemento 4, há uma inversão, pois o 5 é maior que o 4. Portanto, ocorre uma troca. Em seguida, o elemento 5 é comparado com o elemento 3, novamente ocorrendo uma troca. O mesmo acontece com o elemento 4 e o elemento 3. Portanto, nesse passo, ocorrem 3 trocas.
No quarto passo, ocorre o merge das partes restantes. Ao comparar o elemento 2 com o elemento 1, ocorre uma troca. Em seguida, o elemento 2 é comparado com o elemento 0, novamente ocorrendo uma troca. O mesmo acontece com o elemento 1 e o elemento 0. Portanto, nesse passo, ocorrem mais 3 trocas.

Portanto, no total, ocorrem 3 trocas no terceiro passo e 3 trocas no quarto passo, totalizando 6 trocas.

No seu código, você está contando 16 trocas, o que pode indicar um erro na implementação. Sugiro revisar o seu código e verificar se todas as trocas estão sendo contabilizadas corretamente.

Espero ter ajudado e bons estudos!

Mergulhe em programação