¿Cuál es más rápido: clasificación rápida o burbuja, y por qué?

No es una mala pregunta, en realidad.

Quicksort (simplificado):

1. Elija el elemento de partición en la matriz
2. Asegúrese de que solo los elementos más pequeños que la partición estén a la izquierda
3. Recurrir en submatrices izquierda, derecha que contienen elementos menores y mayores respectivamente

Ordenamiento de burbuja:

1. Para cada elemento A en la matriz
2. —- Para cada elemento B en la matriz
3. ——– Si el elemento más pequeño de A y B no está a la izquierda, intercambie los dos
4. —- Si no se han realizado intercambios en esta carrera, hemos terminado.

Entonces, ¿cuáles son los tiempos de ejecución más desfavorables aquí?

• Quicksort: [matemáticas] n ^ 2 [/ matemáticas]
• Bubblesort: [matemáticas] n ^ 2 [/ matemáticas]

Quicksort termina siendo … ¿igual de lento? No exactamente. Recuerde que el peor de los casos no siempre es un buen indicador del rendimiento del mundo real. En el caso promedio,

• Quicksort: [matemáticas] n \ log (n) [/ matemáticas]
• Bubblesort: [matemáticas] n ^ 2 [/ matemáticas]

Por lo general, esto significa que Quicksort tenderá a ser más rápido que Bubblesort.

Sin embargo, Quicksort maneja mal los casos degenerados: cuando la lista ya está en un orden casi ordenado, Quicksort seguirá recurriendo. Bubblesort se detendrá tan pronto como termine, gracias a la condición (4), haciendo que Bubblesort sea más rápido en tales casos.

Siempre empiezo con una consideración: no compare soluciones si no conoce el problema. Por ejemplo, ¿es mejor ir en automóvil o en bicicleta? No puedo responder hasta que me diga a dónde quiere ir, qué tan rápido quiere ir allí, cuánto quiere gastar … Nunca tomaría el automóvil para un viaje de 1 km a un lugar donde el estacionamiento más cercano está a 150 m. de mi destino, y ahora describo por qué.

Está relacionado con la idea de “gastos generales” a la que se refiere Daniel.

Debe tener en cuenta que la comparación de algoritmos generalmente se realiza en condiciones asintóticas . Esto significa que está asumiendo que sus datos son abundantes, muy abundantes; de hecho, tan abundante que puedes decir que son infinitos.

Con datos infinitos, todas las operaciones de costo fijo (abrir la puerta de su garaje, conducir hasta la carretera, cerrar la puerta, alcanzar el automóvil nuevamente; buscar un estacionamiento, llegar a su destino a pie) eventualmente se vuelven irrelevantes. Lo único que importa es qué tan rápido puede cubrir cualquier distancia dada con un automóvil o la bicicleta, porque esta medida depende del tamaño del problema, que usted supone que crece indefinidamente.

Sin embargo, si los datos son finitos, entonces las cosas pueden ser muy diferentes.

Si los costos fijos de su automóvil ascienden, por ejemplo, a 5 minutos para un viaje de 2 minutos, mientras que en bicicleta toma 7 minutos para el viaje real más aproximadamente cero por encima (puede dejarlo en la cerca a las afueras de su destino), entonces usted puedo decir que, para su problema particular, una bicicleta es tan eficiente como un automóvil . Por supuesto, si tiene en cuenta los costos de combustible y estacionamiento (y salud y contaminación), entonces su bicicleta podría ser no solo equivalente, sino una solución mucho mejor.

Por lo tanto, para comparar dos algoritmos en un problema específico , debe evaluar el tiempo real que lleva resolver el problema con sus implementaciones: la cantidad de operaciones elementales y su costo (por ejemplo, el costo del acceso a la memoria puede ser diferente entre la lista vinculada y formación).

También puede consultar los datos específicos que espera, si sabe de antemano algo al respecto. Un ejemplo: si existe una alta probabilidad de que los datos ya estén casi ordenados, preferirá un algoritmo que aproveche esto. En su caso, bubbleort es lineal para datos ordenados, por lo que puede ser su mejor amigo; por la misma razón, es cuadrático para datos invertidos o aleatorios, por lo tanto, aléjese si es probable que sea así.