Limitaciones de las técnicas de clasificación basadas en comparación

Question

La clasificación por comparación se utiliza en la mayoría de los escenarios donde los datos deben ordenarse. Las técnicas como tipo de fusión, ordenación rápida, clasificación por inserción y otras clases de comparación pueden manejar diferentes tipos de datos y eficiencia con un límite inferior de O (nLog (n)).

Mis preguntas son

1. ¿Hay alguna limitación de comparación basados ​​en técnicas de clasificación?
2. ¿Algún tipo de escenarios donde se usarían técnicas de clasificación no comparativas?

aplausos

Answer 1

su respuesta es más o menos a sí mismo. Las técnicas de clasificación basadas en comparación están limitadas al límite inferior de O (n Log (n)). Las técnicas de clasificación no basadas en comparación no sufren este límite. El problema general con los algoritmos que no clasifican es que el dominio debe ser mejor conocido y por esa razón no son tan versátiles como las técnicas basadas en la comparación.

Pigeonhole sort es un ejemplo genial y bastante simple, que es bastante rápido, siempre y cuando el número de valores clave posibles sea similar al número de elementos.

Answer 2

Obviamente, las limitaciones de los géneros de comparación es el factor de tiempo - some are better than others, pero dado un conjunto de datos lo suficientemente grande, todos se volverán demasiado lentos en algún momento. El truco es elegir el correcto, dado el tipo y la combinación de datos que está ordenando.

La clasificación sin comparación se basa en otros factores que ignoran los datos, por ejemplo, counting sort ordenará una recopilación de datos, inspeccionando cada elemento - no comparándolo con ningún otro valor en la colección. El conteo por orden es útil para ordenar una colección basada en algunos datos, si tuvieras una colección de enteros, los ordenaría tomando todos los elementos con un valor de 1 y poniéndolos primero en el destino, luego todos los elementos de valor 2, etc. (ok, usa una matriz "dispersa" para acercar rápidamente la colección y reordenar los valores, dejando espacios pero ese es el principio básico)

Answer 3

Es fácil ver por qué la comparación requiere de N log N comparaciones. ¡No hay! permutaciones y como sabemos ln (N!) es aproximadamente N ln N - N + O (ln N). En la notación O grande, podemos descuidar los términos inferiores a N ln N, y como ln y log difieren solo por constante, obtenemos el resultado final O (N log N)