MergeSortFilmes

MergeSortFilmes

por Shayenne Luz Moura -
Número de respostas: 15

Na descrição da função mergeSortFilmes está escrito:

mergeSortFilmes(lst, criterio)

Ordena uma lista de filmes utilizando o algoritmo quickSort (???)adaptado para listas encadeadas duplamente ligadas. 

Não seria mergeSort?

E também tem:

A funcao so deve utilizar espaco extra O(1).
Hmmm, ok, sem levar em consideracao o espaco O(lg n)
utilizado pela pilha da recursao).
Em outras palavras, a funcao pode conter apenas declaracoes
de umas poucas variaveis (um vetor v[0..n] conta como
n variaveis).

Eu poderia criar uma nova célula cabeça e depois desalocá-la?

O merge deve ser iterativo ou pode-se usar recursão?

Em resposta à Shayenne Luz Moura

Re: MergeSortFilmes

por José Coelho de Pina -

Não seria mergeSort?

Opsss.
Sem dúvida. olho roxo
Vou corrigir isso.
É para implementar o MergeSort adaptado para listas duplamente ligadas circulares com cabeça.

Do enunciado: "... A funcao so deve utilizar espaco extra O(1)...."

Eu poderia criar uma nova célula cabeça e depois desalocá-la?

Sim, pode (deve) sim.
O que não pode fazer e movimentar o conteúdo das células para um vetor, ordenar o vetor e copia os conteúdos devolta para as células. A idéia de listas ligadas é não movimentar conteúdos e apenas alterar ponteiros.

Em resposta à José Coelho de Pina

Re: MergeSortFilmes

por Shayenne Luz Moura -
Ok! :D Obrigada.
Em resposta à Shayenne Luz Moura

Re: MergeSortFilmes

por Edgar Bernardi Righi -

A função pode ser recursiva? 

Em resposta à Edgar Bernardi Righi

Re: MergeSortFilmes

por Renato de Souza -

Pode, na descrição está para nao considerarmos como espaço extra o espaço gasto pela pilha de recursão.

 

Aproveitando, eu não posso declarar um vetor auxiliar, mas posso declarar uns 2~3 ponteiros para percorrer, facilitar na hora de fazer as mudanças, certo?

Outra coisa, na hora da intercalação eu teria duas listas, cada uma com uma cabeça. Posso alocar mais uma cabeça (ficaria com 3 no momento) para ir 'recebendo' as células em ordem correta?

Em resposta à Renato de Souza

Re: MergeSortFilmes

por José Coelho de Pina -

Oi Renato,

Aproveitando, eu não posso declarar um vetor auxiliar, mas posso declarar uns 2~3 ponteiros para percorrer, facilitar na hora de fazer as mudanças, certo?

Sim, pode sim.
Você pode declarar quantas cabeça desejar. Esse número de cabeças deve ser fixo (3, 4,...).
Isto é espaço extra O(1) (independe do tamanho da lista).

Em resposta à Edgar Bernardi Righi

Re: MergeSortFilmes

por José Coelho de Pina -

Oi Edgar,

A função pode ser recursiva?

O João e o Renato já responderam.
Só estou  escrevendo para avisar que agora coloquei de uma maneira mais explícita no comentário da função mergeSort() que o algoritmo implementado deve ser o Mergesort recursivo.

Em resposta à José Coelho de Pina

Re: MergeSortFilmes

por João Henrique Luciano -

Então a cabeça que nós podemos alocar faz o papel do nosso vetor auxiliar das notas de aula? Acho que essa é a peça que tava faltando pra eu entender o que fazer!

Em resposta à João Henrique Luciano

Re: MergeSortFilmes

por José Coelho de Pina -

Então a cabeça que nós podemos alocar faz o papel do nosso vetor auxiliar das notas de aula?

Legal né?! boca aberta
Isto fará com que o Mergesort adaptado para listas seja "in-place".
Não teremos movimentações de dados (como no Mergesort para vetores), mas apenas alterações nos ponteiros.
O espaço extra necessário será bem pouco. Basicamente, umas poucas cabeças/ponteiros em cada nível da recursão.

Em resposta à José Coelho de Pina

Re: MergeSortFilmes

por Fernanda de Camargo Magano -

Na função mergeSortFilmes está escrito:

Se criterio == NOTA, então a lista deve ser ordenada  em ordem decrescente de nota.

Mas nas funções mostrePioresFilmes(lst) e mostreMelhoresFilmes(lst) está:

Pre-condição: a função supõe que a lista de filmes está em ordem crescente de nota.

Devo seguir a ordem crescente ou decrescente na ordenação?

 

 

Em resposta à Fernanda de Camargo Magano

Re: MergeSortFilmes

por Fernanda de Camargo Magano -

Ou posso ordenar de forma decrescente e apenas mudar a cabeça da lista quando chamar a função mostreMelhoresFilmes?

Em resposta à Fernanda de Camargo Magano

Re: MergeSortFilmes

por Renato de Souza -

Como a lista e duplamente encadeada e circular, acho que basta começar a partir de cab->ant, cab->ant->ant, .... até retornar na cabeça.
Fazer o caminho inverso, no caso.

Em resposta à Fernanda de Camargo Magano

Re: MergeSortFilmes

por João Henrique Luciano -

Acho que no caso, antes de chamar a mostre(Melhores/Piores)Filmes(), você chama o (merge/quick)sort com criterio NOTA.

Dá para ordenar de forma decrescente?

EDIT: esquece essa pergunta, agora que eu li direito o enunciado.