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