O que significa para um algoritmo de classificação ser “estável”?

42

Ao ler sobre vários algoritmos de ordenação, já vi que alguns deles são "estáveis" e outros não. O que isso significa e quais tradeoffs estão envolvidos nessa base ao selecionar um algoritmo?

    
por Daenyth 09.07.2014 / 22:46
fonte

2 respostas

88

Uma classificação estável é aquela que preserva a ordem original do conjunto de entrada, onde o algoritmo de comparação não distingue dois ou mais itens.

Considere um algoritmo de ordenação que ordena cartões por classificação , mas não por naipe. A classificação estável garantirá que a ordem original das cartas com a mesma classificação seja preservada; o tipo instável não.

    
por 09.07.2014 / 22:53
fonte
26

Algoritmos estáveis preservam a ordem relativa dos elementos.

Assim, um algoritmo de classificação estável manterá a ordem relativa dos valores que são comparados como iguais.

Considere um algoritmo de classificação em que classificamos uma coleção de 2d pontos com base na dimensão X deles.

Coleção a ser classificada: {(6, 3), (5, 5), (6, 1), (1, 3)}

estável classificado: {(1, 3), (5, 5), (6, 3), (6, 1)}

Ordenado Regular: {(1, 3), (5, 5), (6, 3), (6, 1)} ou {(1, 3), (5, 5), (6, 1), (6, 3)}

Quanto à desvantagem ... bem, a classificação estável é menos eficiente, mas às vezes é necessário.

Por exemplo, quando um usuário clica no cabeçalho de uma coluna para classificar os valores em uma interface do usuário, é razoável esperar que sua ordem de classificação anterior seja usada no caso de valores iguais.

    
por 09.07.2014 / 22:56
fonte

Tags