O que é estabilidade nos algoritmos de classificação e por que é importante?

Estou muito curioso, por que a estabilidade é ou não importante nos algoritmos de classificação?

Diz-se que um algoritmo de classificação é estável se dois objetos com chaves iguais aparecerem na mesma ordem na saída classificada, como aparecem na matriz de entrada a ser classificada. Alguns algoritmos de classificação são estáveis ​​por natureza, como Classificação de inserção, Classificação de mesclagem, Classificação de bolhas, etc. E alguns algoritmos de classificação não são, como Classificação de pilha, Classificação rápida, etc.

Antecedentes : um algoritmo de classificação "estável" mantém os itens com a mesma chave de classificação em ordem. Suponha que tenhamos uma lista de palavras de 5 letras:

peach
straw
apple
spork

Se ordenarmos a lista apenas pela primeira letra de cada palavra, uma classificação estável produzirá:

apple
peach
straw
spork

Em um algoritmo de classificação instável , strawou sporkpode ser trocado, mas em um estável, eles permanecem nas mesmas posições relativas (ou seja, como strawaparece antes sporkna entrada, também aparece antes sporkna saída).

Poderíamos classificar a lista de palavras usando este algoritmo: classificação estável pela coluna 5, depois 4, depois 3, depois 2 e depois 1. No final, ela será classificada corretamente. Convença-se disso. (a propósito, esse algoritmo é chamado de classificação radix)

Agora, para responder sua pergunta, suponha que tenhamos uma lista de nomes e sobrenomes. Somos solicitados a classificar "pelo sobrenome e depois pelo primeiro". Poderíamos primeiro classificar (estável ou instável) pelo primeiro nome, depois classificar estável pelo sobrenome. Após essas classificações, a lista é classificada principalmente pelo sobrenome. No entanto, onde os sobrenomes são iguais, os primeiros nomes são classificados.

Você não pode empilhar tipos instáveis ​​da mesma maneira.

Um algoritmo de classificação estável é aquele que classifica os elementos idênticos na mesma ordem em que aparecem na entrada, enquanto a classificação instável pode não satisfazer o caso. - _{^{Agradeço ao meu professor de algoritmo, Didem Gozupek, por fornecer informações sobre os algoritmos}} .

Algoritmos de Classificação Estável:

• Classificação de inserção
• Mesclar classificação
• Tipo de bolha
• Tim Sort
• Classificação de contagem
• Classificar bloco
• Quadsort
• Classificação da biblioteca
• Coqueteleira Sort
• Classificação do Gnomo
• Tipo ímpar - par

Algoritmos de classificação instável:

• Classificação da pilha
• Classificação da seleção
• Classificação do shell
• Ordenação rápida
• Introsort (sujeito a Quicksort)
• Classificação da árvore
• Classificação do ciclo
• Smoothsort
• Classificação do torneio (sujeito a Hesapsort)

A estabilidade da classificação significa que os registros com a mesma chave mantêm sua ordem relativa antes e depois da classificação.

Portanto, a estabilidade é importante se, e somente se, o problema que você está resolvendo exige a retenção dessa ordem relativa.

Se você não precisar de estabilidade, poderá usar um algoritmo rápido de absorção de memória de uma biblioteca, como heapsort ou quicksort, e esquecê-lo.

Se você precisa de estabilidade, é mais complicado. Algoritmos estáveis ​​têm maior CPU O-grande e / ou uso de memória do que algoritmos instáveis. Portanto, quando você tem um grande conjunto de dados, precisa escolher entre bater a CPU ou a memória. Se você está restrito à CPU e à memória, tem um problema. Um bom algoritmo estável de comprometimento é uma classificação de árvore binária; o artigo da Wikipedia tem uma implementação C ++ pateticamente fácil com base no STL.

Você pode transformar um algoritmo instável em um estável adicionando o número do registro original como a chave de último lugar para cada registro.

Depende do que você faz.

Imagine que você tem registros de algumas pessoas com um campo de nome e sobrenome. Primeiro você classifica a lista pelo primeiro nome. Se você classificar a lista com um algoritmo estável por sobrenome, terá uma lista classificada por nome E sobrenome.

Existem algumas razões pelas quais a estabilidade pode ser importante. Uma é que, se dois registros não precisarem ser trocados trocando-os, você poderá causar uma atualização de memória, uma página será marcada como suja e precisará ser reescrita no disco (ou em outro meio lento).

Um algoritmo de classificação é considerado estável se dois objetos com chaves iguais aparecerem na mesma ordem na saída classificada, como aparecem na matriz não classificada de entrada. Alguns algoritmos de classificação são estáveis ​​por natureza, como Classificação de inserção, Classificação de mesclagem, Classificação de bolhas, etc. E alguns algoritmos de classificação não são, como Classificação de pilha, Classificação rápida, etc.

No entanto, qualquer item de classificação que não seja estável pode ser modificado para ser estável. Pode haver maneiras específicas de classificar algo para torná-lo estável, mas, em geral, qualquer algoritmo de classificação baseado em comparação que não seja estável por natureza pode ser modificado para ficar estável, alterando a operação de comparação de teclas para que a comparação de duas chaves considere a posição como um fator para objetos com chaves iguais.

Referências: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Eu sei que existem muitas respostas para isso, mas para mim, essa resposta , de Robert Harvey , resumiu muito mais claramente:

Uma classificação estável é aquela que preserva a ordem original do conjunto de entradas, em que o algoritmo [instável] não distingue entre dois ou mais itens.

Fonte

Se você assume que o que está classificando são apenas números e apenas seus valores os identificam / os distinguem (por exemplo, elementos com o mesmo valor são idênticos), então a questão da estabilidade da classificação não tem sentido.

No entanto, objetos com a mesma prioridade na classificação podem ser distintos e, em algum momento, sua ordem relativa é uma informação significativa. Nesse caso, a classificação instável gera problemas.

Por exemplo, você tem uma lista de dados que contém o custo de tempo [T] de todos os jogadores para limpar um labirinto com o Nível [L] em um jogo. Suponha que precisamos classificar os jogadores pela rapidez com que limpam o labirinto. No entanto, uma regra adicional se aplica: jogadores que limpam o labirinto com níveis mais altos sempre têm uma classificação mais alta, não importa quanto tempo o tempo seja.

Claro que você pode tentar mapear o valor emparelhado [T, L] para um número real [R] com algum algoritmo que segue as regras e depois classificar todos os jogadores com o valor [R].

No entanto, se a classificação estável for possível, você pode simplesmente classificar a lista inteira por [T] (jogadores mais rápidos primeiro) e depois por [L]. Nesse caso, a ordem relativa dos jogadores (por custo de tempo) não será alterada depois que você os agrupar por nível de labirinto que eles limparam.

PS: é claro que a abordagem para classificar duas vezes não é a melhor solução para o problema em particular, mas para explicar a questão do poster, deve ser suficiente.

A classificação estável sempre retornará a mesma solução (permutação) na mesma entrada.

Por exemplo, [2,1,2] serão classificados usando classificação estável como permutação [2,1,3] (primeiro é o índice 2, depois o índice 1 e o índice 3 na saída classificada) Isso significa que a saída é sempre embaralhada da mesma maneira. Outra permutação não estável, mas ainda correta, é [2,3,1].

A ordenação rápida não é uma classificação estável e as diferenças de permutação entre os mesmos elementos dependem do algoritmo para a escolha do pivô. Algumas implementações são selecionadas aleatoriamente e podem ser classificadas rapidamente, produzindo permutações diferentes na mesma entrada, usando o mesmo algoritmo.

O algoritmo de ordenação estável é determinístico necessário.

Mais alguns exemplos do motivo de querer tipos estáveis. Bancos de dados são um exemplo comum. Considere o caso de um banco de dados de transações que inclua sobrenome, data, hora da compra, número do item, preço. Digamos que a base de dados seja normalmente classificada por data | hora. Em seguida, é feita uma consulta para fazer uma cópia ordenada do banco de dados pelo sobrenome | primeiro nome, uma vez que uma classificação estável preserva a ordem original, mesmo que a comparação da consulta envolva apenas o sobrenome, as transações para cada sobrenome | estar na ordem dos dados | tempo.

Um exemplo semelhante é o Excel clássico, que limita as classificações a 3 colunas por vez. Para classificar 6 colunas, uma classificação é feita com as 3 colunas menos significativas, seguida por uma classificação com as 3 colunas mais significativas.

Um exemplo clássico de uma classificação de raiz estável é um classificador de cartões, usado para classificar por um campo de base 10 colunas numéricas. Os cartões são classificados do dígito menos significativo para o dígito mais significativo. Em cada passagem, um baralho de cartas é lido e separado em 10 posições diferentes, de acordo com o dígito nessa coluna. Em seguida, os 10 compartimentos de cartões são recolocados no alimentador de entrada em ordem (cartões "0" primeiro, cartões "9" por último). Em seguida, outra passagem é feita pela próxima coluna, até que todas as colunas sejam classificadas. Os classificadores de cartões reais têm mais de 10 compartimentos, uma vez que existem 12 zonas em um cartão, uma coluna pode ficar em branco e há uma bandeja de leitura incorreta. Para classificar as letras, são necessárias 2 passagens por coluna, 1ª passagem para dígito, 2ª passagem para a zona 12 11.

Mais tarde (1937), havia máquinas de agrupar cartões (mesclar) que podiam mesclar dois baralhos de cartas comparando campos. A entrada eram dois baralhos já classificados, um baralho mestre e um baralho de atualização. O ordenador mesclou os dois decks em uma nova bandeja de materiais e uma de arquivo, que era opcionalmente usada para duplicatas mestre, para que a nova bandeja mestre tivesse apenas cartões de atualização em caso de duplicatas. Essa foi provavelmente a base da ideia por trás da classificação de mesclagem original (de baixo para cima).