Algoritmos de ordenamiento: el mergesort y más

Algoritmo de ordenamiento mergesort

0

En este episodio de Code Time continuamos con el camino de la programación explorando el campo de los algoritmos de ordenamiento. Hasta ahora se han analizado algoritmos clásicos como el de la burbuja, de inserción y selección. Luego se exploraron otras opciones más avanzadas como el Quicksort. Gracias a estos algoritmos es posible ordenar secuencias. En esta ocasión nos centraremos en estudiar en particular un un último algoritmo: el mergesort.

Nota: Antes de continuar con la lectura sugerimos leer la nota anterior referida al tema y escuchar su respectivo podcast. Así se podrán entender más los algoritmos y permitirá tener un panorama más amplio. Si estás interesado en hacerlo puedes accederlo mediante este enlace directo.

Volviendo al Quicksort ¿Qué pivot escoger?

duda
Listen to “Code Time (65): Algoritmos de ordenamiento PT 3” on Spreaker.

Esta es una pregunta que hay que hacerse a la hora de plantear una implementación del algoritmo. ¿Por qué decimos esto? Esto se debe a que se tiene que tender a dar soluciones óptimas para la resolución del problema. Por algo es llamado quicksort ¿verdad?.

Si se escogiera el primer elemento como pivote podríamos caer en casos como ser la secuencia ordenada en orden ascendente o descendente. En sos cosas nos encontraríamos con el peor resultado. Al particionarse tendríamos una partición con todos los elementos de la secuencia menos uno y otra vacía. Esto se repetiría hasta terminar el ordenamiento. De esta forma un algoritmo que debería de ser más óptimo que los que ya hemos visto es tan malo como el de inserción o selección.

Si elegir el primero podría terminar en un resultado mejorable, con el último elemento ocurre algo similar. Escoger el elemento del medio como pivote no mejora en mucho esto ya que siempre existen algunas configuraciones que sin importar el lugar del pivot caen en el peor de los casos. De esta manera no es posible hacer una optimización a este respecto sin afectar a la eficiencia.

El Mergesort

El quicksort presentaba una forma de trabajar ya conocida: divide y vencerás. El Mergesort es un algoritmo de ordenamiento que también utiliza esta técnica pero resulta más simple de entenderse que el caso anterior.

Este algoritmo consta de dos partes: el particionado y la mezcla:

  1. Si la longitud de la secuencia es 0 ó 1, entonces ya está ordenada.
  2. En otro caso dividir la secuencia desordenada en dos subsecuencias de aproximadamente la mitad del tamaño.
  3. Ordenar cada sublista recursivamente aplicando el ordenamiento.
  4. Mezclar las dos subsecuencias en una sola secuencia ordenada.

La mezcla

A esta altura cada subsecuencia está ordenada. El objetivo de esta parte es reconstruir la secuencia de manera que el resultado también está ordenado. Para explicar esto mejor supondremos que se desea tener un orden ascendente de izquierda a derecha.

Como cada secuencia está ordenada se sabe que el mínimo se encuentra siempre a la izquierda. Así pues se procede a reconstruir una secuencia que reúne ambas subsecuencias de forma tal que el resultado esté ordenado.

Se procede de esta manera hasta reconstruir toda la secuencia.

Un poco de pseudocódigo

El siguiente pseudocódigo refleja el comportamiento del mergesort

  • mergesort(s)
  •        si longitud(s) <= 1
  •                devolver s
  •        en caso contrario
  •                (s1, s2) = dividir(s)
  •                ord1 = mergesort(s1)
  •                ord2 = mergesort(s2)
  •                ordenado = mezcla(ord1, ord2)
  •                devuelve ordenado
  •        
  • mezcla (s1, s2)
  •        resultado = []
  •        mientras longitud(s1) > 0 y longitud(s2) > 0
  •                si primero(s1) <= primero(s2)
  •                        agregar primero(s1) a resultado
  •                        eliminar primero(s1) a s1
  •                sino
  •                        agregar primero(s2) a resultado
  •                        eliminar primero(s2) a s2
  •        si longitud(s1) > 0
  •                agregar primero(s1) a resultado
  •        si longitud(s2) > 0
  •                agregar primero(s2) a resultado
  •        devuelve resultado

   

Una imagen puede ayudar

Obviamente con teoría pura pueden surgir algunas dudas así que incorporamos la siguiente imagen con un ejemplo de ordenamiento.

Ejemplo de aplicación del mergesort

¿Qué complejidad tiene el mergesort?

Para analizar qué tan óptimo es este algoritmo ignoraremos el costo de la división o consideraremos que esta es constante. Este estudio requiere de ciertos conocimientos algebraicos que no asumiremos por lo que la explicación será bastante informal.

El algoritmo al trabajar subdivide la secuencia a la mitad lo que significa que el tamaño del problema se reduce a la mitad. Esto se repite hasta que la secuencia tiene tamaño 1. Esta forma de decrecimiento es llamada logarítmica. Luego es necesario mezclar de a dos subsecuencias lo que requiere recorrerlas teniendo como costo la suma de ambas longitudes.

Si consideramos todas las cosas que son necesarias para completar el ordenamiento concluimos que la complejidad del mergesort es n* (log n).

Existe una demostración más formal la cual requiere aplicar entre otras cosas el teorema maestro. Para simplificar la nota no profundizaremos más aunque es muy recomendable hacerlo.

Para finalizar…

BandaGeek no almacena ni distribuye el software aquí expuesto y la responsabilidad de su uso recae en el usuario.

Esperamos que les haya gustado el tutorial, y más que nada les haya resultado útil. No olviden dejarnos saber su opinión en los comentarios, lo apreciaremos mucho.
Recuerda que si quieres aprender Swift 3 desde Cero totalmente Gratis puedes hacerlo aquí.
Mis medios de contacto

Twitter    Gmail

Contenido

Spreaker    iTunes    Ivoox    Canal de Telegram    Soundcloud    Youtube

También podría gustarte Más del autor

Comentarios

Loading...