Pelo fato de eu estar usando o quicksort recursivo, a possibilidade de q estoure a pilha do sistema é grande caso tenha muitos filmes na lista? C sim, qual seria mais ou menos essa qntde? A solução seria implementar quicksort com pilha?
É normal o arquivos rating.list não carregar? São muitos filmes...
Não consigo entender pq o quicksort (do bonus) funciona para alguns casos e para outros ele acusa falha de segmentação... Revi todo o código e não encontro o problema...
Sim, é possível que o quicksort recursivo estoure a pilha de recursão, mas é um caso bastante particular e depende do número de filmes na lista. O pior caso mesmo, seria ter muitos filmes e o pivô separar as duas metades da lista de maneira muito desigual (por exemplo, um elemento à esquerda, todo o resto à direita). Acreditando que isso aconteça recursivamente para todas as separações, a pilha de recursão alcançaria um tamanho de n-1, aproximadamente. O melhor caso do quicksort é ele pegar o pivô sempre no meio, separando a lista de maneira igual. Isso gera log2
elementos na pilha recursiva, o que é um bom número, mesmo para um número bem grande de filmes. O número exato de estouro da pilha de recursão depende de computador para computador. E eu nunca fiz isso ocorrer, então não serei de muita ajuda. Sinceramente, acho que não há a necessidade de fazer um quicksort iterativo só para não fazer a pilha estourar. A não ser que os professores ou o enunciado especifique o contrário.
O quicksort bônus é mais difícil pelo fato de que ele é mais eficiente porém mais difícil de ser implementado. Você precisa cercar todos os casos possíveis do algoritmo e ver o que está dando de errado. Por exemplo, seu programa funciona para elementos em um dos cantos da lista? Há vários outros casos também. Pense bastante e depois volte a revisar o seu código.
Abraços!
O quicksort bônus é mais difícil pelo fato de que ele é mais eficiente porém mais difícil de ser implementado. Você precisa cercar todos os casos possíveis do algoritmo e ver o que está dando de errado. Por exemplo, seu programa funciona para elementos em um dos cantos da lista? Há vários outros casos também. Pense bastante e depois volte a revisar o seu código.
Abraços!
Então, cheguei a conclusão que são, no mínimo 8 casos:
1) trocando células seguidas, ou seja, quando o i->prox = j;
Subdivide em 4 casos:
1a) Trocando o início e o fim (nesse caso, a lista terá no máximo 2 células)
1b) Trocando o início com alguém que não seja o fim
1c) Trocando alguém que não seja o início com o fim
1d) Trocando o alguém que não seja o início com alguém que não seja o fim
2) trocando células "não seguidas", ou seja, quando o i->prox != j
Mesmo caso do 1
Não sei c ficou faltando algum caso... Estranho que pra algumas listas funciona, mas pra lista dezfilmes.list, ele chega a ordenar, mas por algum motivo, ele "continua" a ordenar, passando a desordenar e dá uma falha de segmentação...
Uma coisa que não sei c poderia estar dando problema: pelo fato de trocarmos os ponteiros de lugar, qndo precisamos verificar c duas células são iguais, não será possivel verificar mais pelo endereço, né?
Outra coisa, não sei c pode, mas posso usar uma lista ligada com índices?
1) trocando células seguidas, ou seja, quando o i->prox = j;
Subdivide em 4 casos:
1a) Trocando o início e o fim (nesse caso, a lista terá no máximo 2 células)
1b) Trocando o início com alguém que não seja o fim
1c) Trocando alguém que não seja o início com o fim
1d) Trocando o alguém que não seja o início com alguém que não seja o fim
2) trocando células "não seguidas", ou seja, quando o i->prox != j
Mesmo caso do 1
Não sei c ficou faltando algum caso... Estranho que pra algumas listas funciona, mas pra lista dezfilmes.list, ele chega a ordenar, mas por algum motivo, ele "continua" a ordenar, passando a desordenar e dá uma falha de segmentação...
Uma coisa que não sei c poderia estar dando problema: pelo fato de trocarmos os ponteiros de lugar, qndo precisamos verificar c duas células são iguais, não será possivel verificar mais pelo endereço, né?
Outra coisa, não sei c pode, mas posso usar uma lista ligada com índices?
Os casos mesmo acho que não convém listar... cada um está usando a sua própria lógica. O grande barato desse EP é você tentar achar uma resposta a mais eficiente possível, que diminua ao máximo os casos. Se você diminui o número de casos, consequentemente diminui a possibilidade de erro.
Se seu EP não funciona para o dezfilmes, muito provavelmente o seu programa está funcionando conforme o esperado para um número pequeno de passos, mas para alguns casos específicos não. Dica: rode seu programa para funcionar para esses casos e verifique por quais subcasos ele está passando. Muito provavelmente eles estão certo, revise os outros.
Quando precisar ver a igualdade de dois endereços, tente usar um auxiliar que fique permanentemente olhando para a célula cujo endereço você posteriormente perder. É a única maneira de fazer isso sem perder ponteiros, acredito.
Se você usar listas ligadas com índices, não será nada diferente de um vetor. Não sei a posição dos professores, mas se você estiver concorrendo ao bônus, então não faça isso. Para efeito de debugação, pode até usar, mas se você enviar o EP com esses índices e a ordenação usando eles, então você indiretamente estará usando um vetor.
Abraços!
Se seu EP não funciona para o dezfilmes, muito provavelmente o seu programa está funcionando conforme o esperado para um número pequeno de passos, mas para alguns casos específicos não. Dica: rode seu programa para funcionar para esses casos e verifique por quais subcasos ele está passando. Muito provavelmente eles estão certo, revise os outros.
Quando precisar ver a igualdade de dois endereços, tente usar um auxiliar que fique permanentemente olhando para a célula cujo endereço você posteriormente perder. É a única maneira de fazer isso sem perder ponteiros, acredito.
Se você usar listas ligadas com índices, não será nada diferente de um vetor. Não sei a posição dos professores, mas se você estiver concorrendo ao bônus, então não faça isso. Para efeito de debugação, pode até usar, mas se você enviar o EP com esses índices e a ordenação usando eles, então você indiretamente estará usando um vetor.
Abraços!