Capítulo 15. MergeSort dividiendo cadena en tres partes

Cuando aplicamos MergeSort en capítulos previos, siempre fuimos dividiendo la cadena de entrada en dos partes. ¿Qué pasaría si dividiéramos la cadena en tres o más partes? ¿Mejoraría la complejidad temporal? En este capítulo intentaremos dar respuesta a estas cuestiones.

Enunciado

Dada una cadena S de números enteros, ordenarla en forma creciente. Utilizar el método de ordenamiento Merge-Sort, pero dividiendo la cadena en 3 subcadenas y analizar el costo.

Pseudocódigo

Análisis de Complejidad Temporal

Considerando que el método UnirCadenasOrdenadas tiene un costo lineal O(n), podemos ver que la cantidad de llamadas recursivas es 3 al igual que la cantidad en que se divide la cadena. El resto de asignaciones y comparaciones tienen un costo constante.

Por lo tanto, tenemos que a = 3, b = 3 y k = 1

Siendo a = b^k ya que 3 = 3¹ el orden del algoritmo es O(n^k*log(n)) lo que finalmente se traduce en un costo de O(n*log(n))

 

Así acabamos de mostrar que el hecho de dividir la cadena en una mayor cantidad de partes no mejora la complejidad temporal de MergeSort. Podemos proceder análogamente en el caso que deseemos dividir la cadena de entrada en 4 o más partes y veremos que el resultado no se ve alterado.

Capítulo 12. Métodos de ordenamiento: MergeSort (Parte II)

En el capítulo anterior nos enfocamos en entender cómo funciona el método de ordenamiento denominado MergeSort. En esta oportunidad presentaremos el pseudocódigo y realizaremos el análisis de complejidad temporal para mostrar que esta técnica mejora las estudiadas previamente.

 

Pseudocódigo

 

 

Para mayor claridad se utiliza el método "Merge" que se encarga de combinar las subcadenas

 

 

 

Análisis de Complejidad Temporal

 

Podemos observar que en el algoritmo MergeSort se realizan 2 llamadas recursivas y la entrada va reduciéndose a la mitad en cada instancia. Por lo tanto nos encuadramos en el Caso 2 con un valor de a = 2.

 

Las operaciones no afectadas por la recursividad tienen una complejidad lineal, es decir, orden O(n) dando un valor de 1 para k. Como dijimos, al reducir la entrada por la mitad, el valor de b es 2.

 

Resumiendo, tenemos que a = b^k (ya que 2 = 2¹)  y entonces el costo del algoritmo es O(n*log n).

 

Esto representa una mejora a los algoritmos de inserción y selección que tenían una complejidad cuadrática. En el próximo capítulo veremos el método de ordenamiento QuickSort, también basado en la técnica de DyC.

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 11. Métodos de ordenamiento: MergeSort (Parte I)

MergeSort

 

En este capítulo estudiaremos el método de ordenamiento conocido como MergeSort. Es un ejemplo de aplicación de la técnica de Divide y Conquista y, como veremos, el costo de su algoritmo es menor al de los métodos de selección e inserción vistos previamente.

 

La técnica consiste en dividir la cadena de entrada en dos mitades, ordenar cada una de las mitades y luego mezclar las mitades ordenadas en una nueva cadena ordenada.

 

Centraremos nuestra atención en un ejemplo simple que ayude a comprender el funcionamiento del algoritmo.

 

Se dispone de la siguiente cadena de enteros desordenada:

 

 

Lo que hacemos ahora es ir dividiéndola en mitades cada vez más pequeñas

 

 

En el algoritmo se verá que en cada iteración creamos 2 cadenas (una para la primera mitad y otra para la segunda mitad) y luego realizamos una llamada recursiva para cada una de ellas.

 

 

El caso base del algoritmo recursivo se producirá cuando la cadena de entrada tenga longitud igual a 1.

 

 

Una vez alcanzado el caso base, empezamos a combinar ordenadamente las subcadenas

 

 

 

Para obtener finalmente la cadena ordenada

 

 

 

 

En la próxima entrega veremos el pseudocódigo y analizaremos la complejidad temporal de MergeSort.