Ir para o conteúdo
cyberops

quicksort e heap sort estaveis

Mensagens Recomendadas

cyberops    0
cyberops

boas,

estes algoritmos sao por natureza instaveis (nao preservam a ordens das chaves repetidas ). alguem tem alguma ideia como por isto estavel? obrigado desde já

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrotuga    31
pedrotuga

Quando comparas dois elementos usa a ordem das chaves como segundo critério de comparação caso os elementos sejam iguais.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

No caso do quicksort é fácil tornar a implementação estável (aliás, não o considero por natureza instável, depende da implementação). Basta utilizar como pivot o primeiro elemento, e separar o resto em menores, e maiores ou iguais, mantendo a ordem. É claro que escolher sempre este elemento como pivot não é boa opção...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

Visto a maior parte das linguagens de relativo alto-nível fornecem algum modo de usar estes algoritmos sem os termos de escrever, a solução mais vezes usada é alterar a função de comparação para o caso de empate

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

Visto a maior parte das linguagens de relativo alto-nível fornecem algum modo de usar estes algoritmos sem os termos de escrever, a solução mais vezes usada é alterar a função de comparação para o caso de empate

Isso pode não ser suficiente... Por exemplo, há implementações do quicksort que para escolherem o pivot, trocam um elemento de uma posição aleatória do vector a ordenar, com o último elemento, o que faz desde logo com que o algoritmo não seja estável. A forma como se trocam os elementos de posição também influencia. Mais uma vez, há implementação em que vamos percorrendo o array das extremidades para o centro, e procurando elemento menores/maiores do que o pivot no "início"/"fim" do array, e quando são necessárias trocas, os elementos que passam do início para o fim que apareceram primeiro, passam a aparecer em último e vice-versa.

Não sei como é que as funções estão implementadas nas várias linguagens, mas a função de ordenação pode não ser suficiente, tudo depende da implementação do algoritmo. E sobretudo em linguagens do nível do C, a optimização do algoritmo incentiva a não o implementar de forma estável.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Eu acho que o Warrior pensou no mesmo que eu: adicionar o indice original do elemento no vector e em caso de igualdade usar esse indice original para desempatar (na função de comparação).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

Isso não influencia Rua Carlos, seja qual for o método usado, se mudares a função de comparação para não existirem igualdades os elementos irão aparecer ordenados no final.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

A menos que se guarde a posição original do valor (tal como o mogers sugeriu, o que não me parece muito prático), não estou a ver onde irias buscar a informação que precisarias na função de ordenação, de modo a que tal não dependesse da implementação.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
cyberops    0
cyberops

A menos que se guarde a posição original do valor (tal como o mogers sugeriu, o que não me parece muito prático), não estou a ver onde irias buscar a informação que precisarias na função de ordenação, de modo a que tal não dependesse da implementação.

pois, foi essa soluçao q encontrei. usando programacao orientada a objectos torna-se bastante simples, o problema é q aumenta a complexidade pq no final temos q percorrer o array todo e para grandes quantidades de dados existe o prob adicional de memoria

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

o problema é q aumenta a complexidade pq no final temos q percorrer o array todo

Se usares uma função de comparação como já foi aqui sugerido ou definires o operador menor da classe/struct, não tens este problema.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade