Blog

Ordenación (parte 7.0): Combinar ordenación

¡Hola a todos! Esta es la parte 7.0 de mi Clasificación serie. Lo sé, dije la última vez que habría un 6.1, ¡pero no todavía!

Entonces, de todos modos, aquí estamos en 7.0, y me pregunto cuánto tiempo puedo prolongar todo esto …

Merge Sort: el algoritmo bajo el capó

Combinar ordenación (Wiki) es otro divide y conquistaras algoritmo, al igual que Quick Sort.

Una gran diferencia con la ordenación rápida es que la ordenación combinada no elige ningún pivote especial. Más bien, Merge Sort divide la matriz para ordenar arr justo en el medio. Luego, utiliza la recursividad para fusionar ordenar el izquierda = arr[0..k] y derecha = arr[k+1..n-1].

Continuará dividiendo cada pieza de la matriz para ordenar arr en trozos cada vez más pequeños, hasta que los trozos sean del tamaño dos o menos.

Esa es la maravilla de divide y conquistaras: tome un problema abrumador y divídalo en muchas tareas más pequeñas y manejables.

Entonces, llegamos a arreglos muy pequeños que esencialmente siguen este patrón: arr[a..b], dónde 0 <= a <= n - 2, 1 <= b <= n - 1, y b – a <= 1, lo que significa que la pieza de la matriz arr[a..b] tiene una longitud de dos o menos.

Bien, ahora tenemos un montón de matrices que tienen dos o menos elementos de longitud. Dos o menos elementos puede significar una de tres cosas:

  1. No hay elementos en la matriz, por lo que lo devolvemos y pasamos a la siguiente pieza.
  2. La matriz tiene un elemento, así que lo devolvemos y seguimos adelante.
  3. La matriz tiene dos elementos. Aquí, intercambiamos los elementos si están fuera de servicio y luego los devolvemos.
Imagen vía kent.edu

Una vez que hayamos ordenado dos o menoses, tenemos que UNIR cada par de dos o menoses en matrices de tamaño cuatro (o menos).

Eche un vistazo a la imagen de arriba de nuevo. ¿Entiendes lo que quiero decir con fusionar? ¿Llevó la cabeza a la pantalla para examinar la segunda línea? cercanamente? Independientemente de tu respuesta, mírala de nuevo e imagina fusionando los dos matrices de tamaño en el cuatro matrices de tamaño por encima de ellos.

Si el primer elemento de la matriz de la izquierda es más pequeño que el primero de la matriz de la derecha, coloque el primer elemento de la izquierda en el primer lugar de la matriz. cuatro matriz, ahora mire el segundo elemento de la matriz izquierda, pero siga mirando a la derecha. Coloque el más pequeño. Ahora está viendo el último elemento de cada dos formación. Pon el más pequeño, eso es 5 en el lado izquierdo del diagrama. Ahora no tienes más valores para fusionar en esa izquierda. dos matriz, así que agrega el resto de ese derecho dos matriz si todavía tiene valores para fusionar.

Sigues fusionando las piezas hasta que tengas la matriz completa.

Está bien, mira ese video. Tenga en cuenta que primero hace el lado izquierdo antes de hacer cualquier cosa para el lado derecho. Esto se debe a cómo se usa la recursividad. Toda la mergesort (izquierda)s se ejecutará antes de que llegue a un mergesort (derecha) en el mismo nivel.

Complejidad del tiempo

Merge Sort tiene un O (n * log n) Complejidad temporal en el peor y mejor caso.

Implementación de Ruby

Enlace Pastebin; captura de pantalla:

Las líneas 5 a 12 son las condiciones de salida, ya que usamos la recursividad en mergesort () (porque llamamos a la función dentro de sí misma en las líneas 15 y 16).

En esta implementación, extendí Ruby Formación clase para tener un mergesort () método. Por eso lo llamo con notación de puntos.

Si la matriz somos mergesorting tiene más de dos elementos, llamamos mergesort en sus mitades izquierda y derecha de inmediato (líneas 15 y 16). No se lleva a cabo ninguna fusión hasta que la matriz para ordenar uno mismo se corta en pequeños dos o menos piezas. Después de eso, comenzamos a fusionarnos.

Hago una matriz vacía arr para retener el resultado (línea 18). Luego, en la línea 20, digo mientras que la izquierda y la derecha tienen elementos, se fusionan. La fusión tiene lugar en ese tiempo círculo. Lo hago comparando el elemento más pequeño de izquierda A la de derecho. El elemento más pequeño de los dos se “fusiona” agregándolo a arr. Luego, eliminamos ese elemento de izquierda o derecho (de donde vino) llamando Array # shift en las líneas 23 y 27.

Llegamos a la línea 31 después de izquierda o derecho se vacía. Agregamos la matriz no vacía. Nota: solo una matriz tendrá elementos restantes en este punto, y se garantizará que el resultado esté ordenado.

Luego devolvemos la nueva matriz, arr.

Versión C ++

Pastebin; capturas de pantalla (es una galería de dos imágenes):

Hacemos básicamente lo mismo, excepto que no extendí vector como extendí Formación en la versión Ruby. Es solo una vieja función normal. Utilice las anotaciones que he proporcionado anteriormente; de lo contrario, he hecho todo lo posible para explicar Merge Sort.

Conclusión

Eso es todo por este artículo. Las implementaciones anteriores son excelentes en el tiempo, pero un poco más pesadas en memoria de lo que me gustaría, por lo que Merge Sort puede regresar a NB en el futuro, un poco más sabio, un poco más optimizado.

Nuevamente, permanezca atento a las optimizaciones de Quick Sort que se avecinan.

Comente a continuación si tiene un algoritmo de clasificación especial que le gustaría incluir en mi serie.

Mantente ordenado
roble

Publicaciones relacionadas

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Mira también
Cerrar
Botón volver arriba
Cerrar