Algoritmo de ordenação que pode manipular algum erro

5

Suponha que você queira classificar sua coleção de filmes, do favorito ao odiado. Você aplica as regras de algum algoritmo de ordenação fazendo muitas perguntas no formulário: "Eu gostei mais de A ou B?"

Agora está resolvido, certo? Logicamente, toda pergunta necessária foi solicitada para provar que quando o índice (A) < índice (B), A > B. Mas você pode mostrar que isso é falso para pelo menos um par A e B. Certamente, o algoritmo deveria ter feito mais perguntas.

A opinião é difícil de entender, e se uma comparação estiver desativada, toda a operação de classificação pode resultar em algo de fora.

Qual algoritmo de classificação você escolheria para garantir que a lista classificada não seja muito afetada por uma comparação ruim?

    
por Hypershadsy 17.11.2015 / 02:56
fonte

1 resposta

5

A principal coisa aqui é evitar fazer a mesma comparação mais de uma vez. E há um tipo que realmente atende a esse critério de uma maneira factível para um ser humano classificando sua coleção de filmes.

Mesclar a classificação .

Com a classificação de mesclagem, você divide de forma recursiva o tamanho do conjunto para 2 (ou 1). E então você classifica cada um desses. Agora, você pega dois conjuntos de 2 (o algoritmo real reduz para conjuntos de 1, mas estamos fazendo isso manualmente e, portanto, podemos evitar esse nível de exatidão) e, em seguida, comparar o primeiro elemento de cada um deles. Se você tiver 3 6 e 2 4 - você já comparou 3 e 6 , você não irá compará-los novamente. O conjunto resultante então se torna 2 3 4 6 e então você continua mesclando com o próximo conjunto de quatro.

Na página da Wikipédia:

Achaveaquiéque,acadacomparação,vocênãoestáreavaliandoascomparaçõesanteriores.Assim,sevocêdecidirquegostamaisdoSubmarinoAmarelodoquedaNoitedosDiasDifíceis,nãovaireavaliarissoeelesnãovãoacabarmuitolongeumdooutronofinal.

Oproblemacommuitosoutrostiposéquevocêestáconstantementeperguntando"eu gosto mais do que Papai Noel Conquista os Marcianos" cada vez com um tipo de seleção / inserção / bolha. E outros tipos tornam-se complicados demais para serem capazes de raciocinar.

Uma maneira de testar isso, o que tornaria algumas postagens interessantes, é implementar você mesmo os diferentes tipos e substituir > ou compareTo no idioma escolhido. Nesse método, adicione um pouco de aleatoriedade, digamos, +/- 10% do valor. ou +/- 1% do valor.

Depois, classifique os números 1 .. 100 100x e veja o quão longe cada método de classificação resulta.

    
por 17.11.2015 / 03:29
fonte

Tags