• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

cyberops

quicksort e heap sort estaveis

11 mensagens neste tópico

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á

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É exactamente isso que normalmente se faz, e é bastante prático.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

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