2

Um algoritmo de classificação (sorting) é dito estável se ele mantém a ordem relativa dos elementos com chaves iguais.

Creio que minha pergunta é, qual o benefício de manter essa ordem relativa?

Alguém pode dar um exemplo?

Fonte

12
  • Isso? pt.stackoverflow.com/q/188646/101 OU isso? pt.stackoverflow.com/q/325088/101
    – Maniero
    Commented 29/01/2019 às 15:58
  • 1
    Mas o benefício é só este, não tem nada demais.
    – Maniero
    Commented 29/01/2019 às 16:06
  • 1
    Só enfeitaram o exemplo, mas em essência é o mesmo, porque não tem o que inventar
    – Maniero
    Commented 29/01/2019 às 16:10
  • 1
    Se a ordem relativa das chaves iguais for importante pra você, utilizar um algoritmo estável te garante previsibilidade no resultado. Acho que é só esse o benefício.
    – bfavaretto
    Commented 29/01/2019 às 17:04
  • 1
    Também acho que é só esse, acho que o espírito da pergunta era conhecer uma situação (na medida do possível não-inventada) em que isso é posto em prática.
    – Piovezan
    Commented 29/01/2019 às 17:07

1 Resposta 1

2

Existem casos onde um novo elemento numa estrutura tem mesmo valor de chave de ordenação que outro já existente e que é mais conveniente seja colocado logo depois dele, como em casos onde é mais justo quando o que vem primeiro é priorizado. Mas e se na hora da inserção a chave de ordenação não é conhecida ainda, somente mais tarde será determinada?

Pois é, alternativamente pode-se inserir os elementos no final, ou seja, em ordem de inserção na estrutura para só depois então aplicar uma ordenação pela chave desejada, mas ainda assim levando em conta como desempate essa ordem de inserção, da qual de fato a ordenação partiu. Para isso, existem duas opções.

(1) Adicionar a cada elemento um campo que é o índice de começo de ordenação para utilizá-lo como desempate.

(2) Usar um algoritmo estável, assim não precisando desse campo.

Um exemplo de problema que sugere uma ordenação com prioridade dos primeiros sobre os últimos numa estrutura é o ranqueamento de candidatos concorrentes a vagas. Se restar apenas uma vaga para dois candidatos de mesmo desempenho nos exames, é mais justo que seja dada ao que se antecipou na inscrição ou ao que demorou mais para se inscrever? Numa concorrência a um cargo normalmente se utilizam vários critérios de desempate, mas se as notas nas avaliações são todas iguais então no final das contas é mais justo que quem se inscreve primeiro tenha prioridade na recepção de vagas, correto?

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 .