Jump to content
Fórum Script Brasil
  • 0
Sign in to follow this  
palliativos

[C] Número de inversões no Mergesort

Question

Olá amigos, boa tarde!

Abaixo descrevo o código que tenho que faz a ordenação de um vetor pelo método de MergeSort. Meu problema é que preciso retornar no main o número de inversões do processo. Na verdade eu não sei como identificar as inversões e também tenho problemas com recursividade. Segue o código abaixo e desde já fico agradecido. Qualquer informação será bem vinda!

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
 
void Intercala (int p; int q; int r; int v[]) {
    int i, j, k, *w;
    w = malloc ((r-p) * sizeof (int));
    i = p; j = q; k = 0;
    while (i < q && j < r) {
        if (v[i] <= v[j]) w[k++] = v[i++];
        else w[k++] = v[j++];
    }
    while (i < q) w[k++] = v[i++];
    while (j < r) w[k++] = v[j++];
    for (i = p; i < r; i++) v[i] = w[i-p];
    free (w);
}
 
void Mergesort (int p; int r; inr v[]) {
    if (p < r-1) {
        int q = (p + r)/2;
        Mergesort (p, q, v);
        Mergesort (q, r, v);
        Intercala (p, q, r, v);
    }
}
 
int main() {
 
    int t, i, n, j;
    scanf("%d", &t);
    
    for (i=0; i<t; i++) {
        scanf("%d", &n);
        int a[n], inversoes = 0;
        
        for (j=0; j<n; j++) {
            scanf("%d", &a[j]);
        }
        
        printf("\n");
        
        Mergesort (0, n, a);
        
        printf("%d\n", inversoes);
        
    }
    return 0;
}

Share this post


Link to post
Share on other sites

1 answer to this question

Recommended Posts

  • 0

Boa tarde, não sou bom em margesort mais posso te falar que pelo que eu entendi é que você quer um ++ a cada inversão correto? você pode colocar uma variável global dando um ++ dentro da função recursiva, Pelo menos comigo funciona ou ate mesmo no main uma variável+=função mais na função tem que dar um return 1 assim que ele trocar ou no caso a cada troca ++ e no return variavel(que recebeu um ++ a cada troca) Qualquer coisa eu testo seu código e tento ajudar. É que estou com um problema em um programa também aqui :\. Um abraço

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  



  • Forum Statistics

    • Total Topics
      148586
    • Total Posts
      644292
×
×
  • Create New...