Duvida Lab 5

[frangupe]

Tenho o lab 5 praticamente pronto, no entanto, para testes com números menores (como aqueles no pdf) meu programa exibe a resposta corretamente, no entanto, quando uso os testes abertos, o valor da minha resposta fica muitíssimo abaixo do esperado.

Por exemplo, para o teste 1, meu programa exibe o valor de "792570" quando a resposta correta seria "2496686030", ou seja, muito maior. Já tentei modificar o código de diversas formas para tentar fazer contar mais vezes as inversões (mesmo que de forma incorreta), mas mesmo assim, o valor encontrado continua sendo muitíssimo abaixo do correto.

Obs: Estou usando um vetor de Long com somente com um espaço, que é onde vou guardando a quantidade de inversões.

[leonardosrodrigues0]

Achei estranho que o número de inversões da fila é maior que seu tamanho. O máximo de inversões necessárias não seria N, já que isso seria suficiente para colocar cada valor em seu lugar?

[frangupe]

@leonardosrodrigues0 Acho que não, pois o problema considera que inversões são feitas apenas em pares lado a lado. Desse jeito o numero de inversões máximo seria N + N-1 + N-2 ... 3 + 2 + 1 ( eu acho). Enfim, de qualquer maneira, não consigo chegar nem próximo do resultado correto.

[leonardosrodrigues0]

No primeiro exemplo de entrada e saída do enunciado, as inversões não são feitas entre vizinhos.

[enoque]

@leonardosrodrigues0 , no enunciado é explicado o passo-a-passo de como é feito (é um pouco confuso de inicio msm). Se temos um vetor [5,4,1,2,3], o elemento '5' está invertidos com todos os outros elementos, pois ele é o maior elemento e está no primeiro índice (então já conta 4), já o elemento '4' está investido com os elementos [1,2,3], pois ele é maior que eles e está em um índice menor (ai já soma mais 3). Totalizando 7 inversões em um vetor de tamanho 5.

Uma outra forma de você pensar é a seguinte: qual o menor número de trocas entre vizinhos é necessário para que minha lista fique ordenada?

Espero que isso ajude você... :)

[enoque]

Agora respondendo o @GFranciscoP , você deve está errando algum detalhe na hora de contabilizar as inversões... Como você está fazendo na hora que junta as duas metades dos vetores (no algoritmo do mergesort)?

[leonardosrodrigues0]

@enoque Consegui entender, obrigado. Acho que não ficou muito claro no enunciado, já que não é dito nada sobre vizinhos, e tem até um exemplo que faz uma inversão entre não vizinhos.

[enoque]

No enunciado tem uma explicação um pouco mais formal, mas não é simples de entender mesmo.

Que bom que ajudou :)

[frangupe]

@enoque Adicionei mais um parâmetro nas funções merge (casca) e mergesort, que no meu caso é um ponteiro para um vetor de Long. Estou fazendo a contagem dentro da função mergesort.

[enoque]

@GFranciscoP Não consegui tirar muita coisa pra lhe ajudar do seu comentário. Como você faz a contagem exatamente? Um detalhes que você tem que se atentar no momento que junta as duas partes do vetor (chamada recursiva), é que se o elemento da segunda metade é menor, então o é necessário contabilizar toda a quantidade de elementos restante da primeira metade.

[enoque]

Pelo que entendi do seu código e da sua explicação, você está considerando uma inversão somente os elementos que mudaram de posição. O próprio exemplo que dei lá em cima pra explicar o problema acho que já vai dá errado.

Se a entrada for [1,2,3,4,0,5,6,7], qual a saída do seu código? Se entendi bem, vai ser 1.

[frangupe]

@enoque De ontem pra hoje modifiquei algumas coisas no programa. Para a entrada [1,2,3,4,0,5,6,7] a saída é 4.

No entanto, para o teste 1, minha saída é "298150101" e o correto seria "2496686030"

Estou chamando uma função contadora dentro da mergesort, que compara o vetor com o vetor auxiliar (antes de copiar os dados) no período entre l e r (l <= r).

Posso enviar o código desta função aqui?

[enoque]

Me envia para o e-mail: enoquealvesufc@gmail.com

Amanhã tiro um tempo pra olhar. Caso eu não responda, pode mandar de novo que as vezes eu acabo perdendo alguns e-mails na caixa de entrada.