Ambos son algoritmos de clasificación basados en la estrategia de dividir y conquistar.
Mergesort
El verdadero trabajo de mergesort se realiza mediante la operación de merge . Dadas dos sub-matrices ordenadas, que juntas tienen un total de n elementos, la operación de merge utiliza una matriz auxiliar de tamaño n para fusionarlas en una sola matriz ordenada en tiempo lineal, es decir, O (n) en notación Big Oh.
Al tener esta operación de fusión, mergesort funciona de la siguiente manera. Dada una matriz de elementos A, clasifica las sub-matrices izquierda y derecha usando mergesort en sí, y luego las combina en una sola matriz ordenada. El caso base es una sub-matriz de tamaño 1, que se ordena implícitamente por definición.
- ¿Qué hace exactamente node = node-> next en una lista vinculada?
- ¿Existe un algoritmo para aplicar a una imagen que muestre lo que vería alguien que necesita corrección de la visión?
- Cómo analizar los detalles del problema en el concurso de codificación
- Ayúdame con el problema TopCoder SRM - 599, div - I, level - 3?
- ¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria?
Si analizamos la complejidad temporal de mergesort, veremos que es O (n log n) en todos los casos. Es decir, el tiempo necesario para ordenar n elementos crece proporcionalmente a n log n. La ordenación por fusión también necesita una matriz adicional de tamaño n para la operación de fusión. Entonces su complejidad espacial es O (n) .
Ordenación rápida
Quicksort es otro algoritmo de clasificación de divide y vencerás, propuesto por CAR Hoare. Aquí, el caballo de batalla es la operación de partition . Dada una matriz de n elementos, la partition toma un elemento (conocido como pivote) y lo coloca en la posición correcta. Es decir, la matriz no se ordenará, pero todos los elementos inferiores al pivote estarán a la izquierda del pivote, y todos los elementos mayores que el pivote estarán a la derecha. La operación de partition se puede realizar en tiempo lineal.
Quicksort luego funciona de la siguiente manera. Primero, realiza la operación de partición en la matriz de entrada. Suponga que el pivote se coloca en la posición p . Ahora, la ordenación rápida clasifica las submatrices A [0: p – 1] y A [p + 1: n – 1], utilizando la ordenación rápida en sí. Aquí nuevamente, el caso base es una matriz de tamaño 1.
Hay varias formas de seleccionar el pivote. Lo más simple es simplemente tomar el elemento más a la izquierda como pivote. Pero, esto lleva a una debilidad fatal. En este caso, si la matriz ya está ordenada, el pivote se colocará siempre en la posición más a la izquierda, y quicksort ordenará sublistas de tamaño 0 yn – 1. Esto lleva a una complejidad temporal de [matemáticas] O (n ^ 2) [/ math], que no es mejor que el tipo de burbuja.
Esto puede mitigarse eligiendo un elemento aleatorio como pivote o utilizando la mediana de tres elementos. En este caso, el peor de los casos de [matemáticas] O (n ^ 2) [/ matemáticas] es extremadamente improbable (límite imposible).
En el mejor de los casos, cuando el pivote siempre se coloca en el medio, la complejidad del tiempo será O (n log n) . Además, si el pivote siempre se coloca en algún lugar en la parte media del 50% (25% – 75%) de la matriz, la ordenación rápida tomará un tiempo proporcional a O (n log n), incluso en el mejor de los casos.
La mayor ventaja de la clasificación rápida es que, aunque las complejidades asintóticas son O (n log n) , el multiplicador constante (oculto por la notación Big Oh) es mucho más pequeño para la clasificación rápida, que posteriormente es apreciablemente más rápida que la combinación en casi todos los casos. .
En cuanto a la complejidad del espacio, la complejidad del espacio de la clasificación rápida es O (log n), teniendo en cuenta el espacio de pila utilizado para la recursividad.
Además, quicksort no se puede implementar de forma iterativa, a diferencia de mergesort, donde es posible una implementación iterativa, a veces llamada mergesort de abajo hacia arriba .
