¿Por qué la clasificación por selección es más rápida que la clasificación por burbujas?

Todas las complejidades que proporcionó son verdaderas, sin embargo, se dan en notación Big O , por lo que se omiten todos los valores aditivos y constantes.

Para responder a su pregunta, necesitamos d centrarse en un análisis detallado de esos dos algoritmos. Este análisis se puede hacer a mano o se puede encontrar en muchos libros. Utilizaré los resultados de El arte de la programación informática de Knuth .

Número promedio de comparaciones:

• Clasificación de burbujas : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Orden de inserción : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Orden de selección : $ (N + 1) H_N – 2N $

Ahora, si traza esas funciones, obtiene algo como esto:

Como puede ver, la clasificación de burbujas es mucho peor a medida que aumenta el número de elementos, aunque ambos métodos de clasificación tienen la misma asintótica complejidad.

Este análisis se basa en la suposición de que la entrada es aleatoria, lo que puede no ser cierto todo el tiempo. Sin embargo, antes de comenzar a ordenar, podemos permutar aleatoriamente la secuencia de entrada (usando cualquier método) para obtener el caso promedio.

Omití el análisis de complejidad temporal porque depende de la implementación, pero se pueden usar métodos similares.

Comentarios

• Tengo un problema con » podemos permutar aleatoriamente la secuencia de entrada para obtener el caso promedio «. ¿Por qué se puede hacer eso más rápido que el tiempo requerido para ordenar?
• Puede permutar cualquier secuencia de números que tomará $ N $ tiempo donde $ N $ es la longitud de la secuencia. Es ‘ obvio que cualquier algoritmo de ordenación basado en comparaciones debe tener al menos $ \ mathcal O (N \ log N) $ complejidad, así que incluso si le agregas $ N $ ‘ La complejidad ‘ no cambiará tanto. De todos modos, estamos hablando de comparación, no de tiempo, la complejidad del tiempo depende de la implementación y la máquina en ejecución, como mencioné en la respuesta.
• Supongo que tenía sueño, tienes razón, la secuencia se puede permutar en tiempo lineal .
• Dado que $ H_N = \ Theta (log N) $, ¿el límite de comparación es correcto para la clasificación por selección? Parece que ‘ está insinuando que hace O (n log n) comparaciones en promedio.
• Gamma = 0.577216 es Euler-Mascheroni ‘ s constante. El capítulo relevante es » El arte de programar » vol 3 sección 5.2.2 pág. 109 y 129. ¿Cómo trazó el caso de clasificación de burbujas exactamente, especialmente el término O (sqrt (N))? ¿Lo descuidó?

El costo asintótico, o $ \ mathcal O $ -notation, describe el comportamiento limitante de una función ya que su argumento tiende al infinito, es decir, su tasa de crecimiento.

La función en sí, p. ej. el número de comparaciones y / o intercambios, puede ser diferente para dos algoritmos con el mismo costo asintótico, siempre que crezcan con la misma tasa.

Más específicamente, la clasificación de burbujas requiere, en promedio, $ n / 4 $ intercambios por entrada (cada entrada se mueve por elementos desde su posición inicial a su posición final, y cada intercambio incluye dos entradas), mientras que la clasificación por selección requiere solo $ 1 $ (una vez que se ha encontrado el mínimo / máximo, se intercambia una vez hasta el final de la matriz).

En términos del número de comparaciones, la clasificación de burbujas requiere $ k \ veces n $ comparaciones, donde $ k $ es la distancia máxima entre la posición inicial de una entrada y su posición final, que suele ser mayor que $ n / 2 $ para valores iniciales distribuidos uniformemente. Sin embargo, la ordenación por selección siempre requiere comparaciones $ (n-1) \ times (n-2) / 2 $.

En resumen, el límite asintótico le da una buena idea de cómo crecen los costos de un algoritmo con respecto al tamaño de entrada, pero no dice nada sobre el rendimiento relativo de diferentes algoritmos dentro del mismo conjunto.

Comentarios

• esta es incluso una muy buena respuesta
• ¿Qué libro prefieres?
• @GrijeshChauhan: Los libros son cuestión de gustos, así que tome cualquier recomendación con un grano de sal. Personalmente, me gusta Cormen, Leiserson y Rivest ‘ s » Introducción a los algoritmos «, que ofrece una buena descripción general sobre varios temas, y Knuth ‘ s » El arte de la programación informática » si necesita más / todos los detalles sobre un tema específico. Si lo desea, puede verificar si la pregunta de los libros se ha hecho aquí antes, o publicar esa pregunta si no ‘ t.
• Para mí, el tercer párrafo tu respuesta es la respuesta real. No las gráficas para entradas grandes, dadas en otra respuesta.

La clasificación de burbujas usa más tiempos de intercambio, mientras que la ordenación por selección evita esto.

Al seleccionar ordenar, cambia n veces como máximo. pero cuando se usa la clasificación de burbujas, cambia casi n*(n-1). Y, obviamente, el tiempo de lectura es menor que el tiempo de escritura, incluso en la memoria. El tiempo de comparación y otros tiempos de ejecución se pueden ignorar. Por lo tanto, los tiempos de intercambio son el cuello de botella crítico del problema.

Comentarios

• Creo que la otra respuesta de Bartek es más razonable, pero no puedo ‘ votar o comentar … Por cierto, sigo pensando que el tiempo de escritura afecta más y espero que pueda tener esto en cuenta si ve esto y está de acuerdo.
• No puede simplemente ignorar el número de comparaciones, ya que hay casos de uso en los que el tiempo gastado para comparar dos elementos puede superar con creces el tiempo dedicado a intercambiar dos elementos. Considere una lista vinculada de cadenas extremadamente largas (digamos 100k caracteres cada una). Leer cada cadena tomaría mucho más tiempo que hacer la reasignación del puntero.
• @IrvinLim Creo que puede tener razón, pero es posible que tenga que ver los datos estadísticos antes de cambiar de opinión.