3

O que define um algoritmo de ordenação estável?

Nessa pergunta já foi falado um pouco sobre o que é ordenação estável e instável, porém ainda não percebo a vantagem de utilizar uma instável.

Em que casos podemos usar uma ordenação instável? É sempre preferível usar uma estável?

Dependendo da estrutura de dados que utilizemos é preciso ter cuidado com a ordenação instável?


Um algoritmo de ordenação é considerado estável quando consegue preservar a ordem de registro de chaves iguais, em outras palavras se os registros aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial.


Essa explicação não percebi, o que seria os registros? Ex:

int vec[5]={4,2,5,1,7};

Se eu quisesse ordenar esse vetor o que seria preservar a ordem dos registros?

5
  • 1
    Em uma ordenação estável, em caso de "empate" (2 elementos iguais), a ordem relativa entre eles não é alterada. No seu array {4,2,5,1,7} não faz diferença pq não tem elementos repetidos. Mas suponha que tenho usuários com nome e idade, e quero ordenar somente pela idade: {(João,30),(Maria,25),(José,20),(Ana,25)}- com um algoritmo estável, em casos de empate (Maria e Ana tem a mesma idade), a ordem entre elas é mantida, então o resultado seria {(José,20),(Maria,25),(Ana,25),(João,30)} - Maria estava antes de Ana no array original, e o algoritmo estável manteve esta ordem.
    – hkotsubo
    27/08/2018 às 0:54
  • 1
    E creio que nesse caso "registros" signifique "elementos". No seu array, 4 é um registro, 2 é outro, etc. No meu exemplo, cada usuário é um registro. Por isso em um algoritmo estável "os registros (os elementos/números/usuários) aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial", mas só em caso de empate, ou seja, quando há "registros de chaves iguais" (chave seria o valor que está sendo considerado na ordenação - no seu exemplo é o próprio número, no meu exemplo é a idade), então "registros de chaves iguais" são números iguais ou usuários com a mesma idade.
    – hkotsubo
    27/08/2018 às 1:34
  • Eu essa definição sei, mas qual era o mal de trocar Maria e Ana, é isso que nao entendo, penso que não será algo grave. 27/08/2018 às 10:39
  • Creio que isso já está explicado na resposta do Maniero abaixo e na pergunta que vc linkou. Em resumo, se a manter a ordem original é um requisito, use um algoritmo estável. Se tanto faz, escolha o que achar melhor. Não é questão de ser "mal"
    – hkotsubo
    27/08/2018 às 11:57
  • @hkotsubo Sim, depois é que reparei que estava la explicado. Obrigado mais uma vez 27/08/2018 às 11:58

1 Resposta 1

5

Aqui eu vou pela Navalha de Occam: se todas as soluções dão o mesmo resultado escolho a mais simples. Que pode ser a mais eficiente.

Em geral se você tem 2 "josé" e mais nada que os diferencie tanto faz quais deles entra primeiro depois de classificado e, portanto, tanto faz que algoritmo usar. Mas se a lista classificada que está sendo montada precisa considerar a ordem de entrada na lista então o algoritmo estável é obrigatório. Basicamente a pergunta que deve fazer é se a posição na listagem original faz parte do desempate ou não, se ele é uma informação importante precisa usar o algoritmo estável.

Todo algoritmo de classificação instável pode ser transformado em estável se modificar a chave de classificação adicionando manualmente a posição, desde que ela esteja disponível.

Como sempre, é uma questão de quais garantias você precisa e quais comprometimentos você aceita. Alguns algoritmos abrem mão de alguma eficiência para oferecer estabilidade. Mas isto não é garantido, dependendo da comparação o estável pode ter mais eficiência que o instável.

Não é que precise cuidado com determinada estrutura de dados, e sim cuidado com a necessidade desejada.

Por exemplo, uma tabela de espalhamento não tem posição clara, então não faz sentido requerer estabilidade se esta for a fonte.

Lembrando que só pode haver instabilidade em caso de empate. Se a estrutura garante ter chave única a estabilidade é garantida para qualquer algoritmo. Então o exemplo citado tanto faz se o algoritmo é estável ou não, afinal não existe empate em 2 elementos dele. Leia novamente a pergunta linkada porque ainda não entendeu o que é a estabilidade citada.

Particularmente prefiro o estável sempre que não faz diferença ou que ela não importa, mas é comum fazer alguma diferença.

Pode ser que no futuro você precise da ordem original, mesmo que não precise agora, aí teria que refazer a classificação no original, se estiver disponível.

Além disso algoritmos estáveis tendem ter mais previsibilidade de consumo de recursos.

Coloquei no GitHub para referência futura.

1
  • Muito obrigado, este assunto de ordenação parece ter muito que falar, eu por norma escolho sempre o mais facil de implementar e com bom desempenho, como disse não olho muito se é estável ou não, provavelmente terei de me informar mais sobre isto. Como todos os algoritmos de ordenação já estão feitos eu faço um copy paste e altero apenas o necessário, sendo bastante facil de implementar um QuickSort como por exemplo 27/08/2018 às 11:16

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .