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

28

Está escrito en Wikipedia que "... el tipo de selección casi siempre supera al de burbuja y al de gnomos". ¿Alguien puede explicarme por qué el ordenamiento por selección se considera más rápido que el ordenamiento por burbujas aunque ambos tengan:

  1. La peor complejidad del tiempo del caso :O(n2)

  2. Número de comparaciones : O(n2)

  3. Mejor complejidad del tiempo del caso :

    • Tipo de burbuja:O(n)
    • Tipo de selección:O(n2)
  4. Complejidad de tiempo promedio del caso :

    • Tipo de burbuja:O(n2)
    • Tipo de selección:O(n2)
RYO
fuente

Respuestas:

32

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

Para responder a su pregunta, debemos centrarnos en un análisis detallado de esos dos algoritmos. Este análisis se puede hacer a mano o en muchos libros. Usaré los resultados de Knuth's Art of Computer Programming .

Número promedio de comparaciones:

  • Tipo de burbuja :12(N2NlnN(γ+ln21)N)+O(N)
  • Tipo de inserción :14(N2N)+NHN
  • selección :(N+1)HN2N

Ahora, si trazas esas funciones obtienes algo como esto: trama plot2

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

Este análisis se basa en el supuesto de que la entrada es aleatoria, lo que podría 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 la complejidad del tiempo porque depende de la implementación, pero se pueden usar métodos similares.

Bartosz Przybylski
fuente
Tengo un problema con "podemos permutar aleatoriamente la secuencia de entrada para obtener un caso de avarage". ¿Por qué se puede hacer eso más rápido que el tiempo requerido para ordenar?
Sasho Nikolov
1
Puede permutar cualquier secuencia de números, llevará tiempo donde es la longitud de la secuencia. Es obvio que cualquier algoritmo de clasificación basado en la comparación debe tener al menos la complejidad por lo que incluso si agrega a su complejidad no cambiará tanto. De todos modos, estamos hablando de la comparación, no del tiempo, la complejidad del tiempo depende de la implementación y la máquina en ejecución, como mencioné en la respuesta. N O ( N log N ) NNNO(NlogN)N
Bartosz Przybylski
Supongo que tenía sueño, tienes razón, la secuencia se puede permutar en tiempo lineal.
Sasho Nikolov
Dado que , ¿es su comparación enlazada correcta para el tipo de selección? Parece que estás insinuando que hace comparaciones O (n log n) en promedio. HN=Θ(logN)
templatetypedef
Gamma = 0.577216 es la constante de Euler-Mascheroni. El capítulo relevante es "El arte de la programación" 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))? ¿Acabas de descuidarlo?
mxmlnkn
11

El costo asintótico, o notación matemática , describe el comportamiento limitante de una función ya que su argumento tiende al infinito, es decir, su tasa de crecimiento.O

La función en sí misma, por ejemplo, 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 ordenación de burbujas requiere, en promedio, intercambios por entrada (cada entrada se mueve en función de los elementos desde su posición inicial a su posición final, y cada intercambio implica dos entradas), mientras que la selección de selección requiere solo (una vez que se ha encontrado el mínimo / máximo, se intercambia una vez al final de la matriz).1n/41

En términos del número de comparaciones, la clasificación de burbujas requiere comparaciones, donde es la distancia máxima entre la posición inicial de una entrada y su posición final, que generalmente es mayor que para valores iniciales distribuidos uniformemente. Sin embargo, la selección de selección siempre requiere comparaciones.k n / 2 ( n - 1 ) × ( n - 2 ) / 2k×nkn/2(n1)×(n2)/2

En resumen, el límite asintótico le brinda 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.

Pedro
fuente
1
esta es incluso una muy buena respuesta
Grijesh Chauhan
¿Qué libro prefieres?
Grijesh Chauhan
@GrijeshChauhan: los libros son una cuestión de gustos, así que tome cualquier recomendación con un grano de sal. Personalmente, me gusta la "Introducción a los algoritmos" de Cormen, Leiserson y Rivest, que ofrece una buena visión general de varios temas, y la serie "El arte de la programación de computadoras" de Knuth si necesita más / todos los detalles sobre un tema específico. Es posible que desee verificar si la pregunta de los libros ya se ha hecho aquí antes, o publicar esa pregunta si no es así.
Pedro
Para mí, el tercer párrafo en su respuesta es la respuesta real. No las gráficas para entradas grandes, dadas en otra respuesta.
intercambio excesivo el
3

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

Cuando se utiliza la selección ordenar, intercambia nveces como máximo. pero cuando se usa el tipo burbuja, casi se intercambia n*(n-1). Y obviamente, el tiempo de lectura es menor que el tiempo de escritura incluso en la memoria. Se puede ignorar el tiempo de comparación y otro tiempo de ejecución. Por lo tanto, los tiempos de intercambio son el cuello de botella crítico del problema.

simonmysun
fuente
Creo que la otra respuesta de Bartek es más razonable, pero no puedo votar ni comentar ... Por cierto, todavía creo que el tiempo de escritura afecta más y espero que pueda tener esto en cuenta si lo ve y está de acuerdo.
simonmysun
No puede simplemente ignorar el número de comparaciones, ya que hay casos de uso en los que el tiempo dedicado a comparar dos elementos puede exceder con creces el tiempo dedicado a intercambiar dos elementos. Considere una lista vinculada de cadenas extremadamente largas (digamos 100k caracteres cada una). La lectura en cada cadena llevaría mucho más tiempo que la reasignación del puntero.
Irvin Lim
@IrvinLim Creo que puede que tengas razón, pero es posible que tenga que ver los datos estadísticos antes de cambiar de opinión.
simonmysun