quicksort e heap sort estaveis

[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á

[pedrotuga]

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

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

[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

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

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

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

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

[Warrior]

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

[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

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