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.
No hay comentarios:
Publicar un comentario