Algoritmos de ordenamiento II. Merge Sort


Dándole continuidad al tema sobre Algoritmos de ordenamiento, en donde vimos en la primera parte qué es un algoritmo de ordenamiento, el objetivo de los mismos y sus principales características, ahora te mostraré otros métodos de ordenamiento más óptimos, donde la complejidad es mucho menor que los vistos anteriormente (Ordenamientos Burbuja y Mínimo Sucesivo).

La complejidad de los algoritmos está dada por la cantidad máxima de iteraciones que hace al ser ejecutado. Partiendo de esto, los métodos que veremos tienen una complejidad equivalente a N*log(N), donde N es la cantidad de elementos con que cuenta la lista que queremos ordenar.

A priori, si comparamos estas complejidades con la de los algoritmos anteriores, que era N*N, no es muy significativa, pero si te fijas en la siguiente tabla puedes notar cómo va creciendo esa diferencia a medida que aumentan los elementos en la lista a ordenar.

N N*N N*log(N)
10 100 10
100 10000 200
1000 1000000 3000
10000 100000000 40000

Es apreciable la diferencia entre ambas complejidades y puedes imaginar lo grande que puede llegar a ser, a medida que la N sea mayor. Es por ello la necesidad de conocer los algoritmos que te voy a mostrar. Pero ¿De qué algoritmos estamos hablando?, pues me refiero a los algoritmos:

  • Merge Sort (Ordenamiento por mezcla)
  • QuickSort (Ordenamiento rápido)

Dado lo complejos que pueden llegar a ser estos métodos de ordenamiento, solo veremos el método Merge Sort en este artículo y en el próximo y último artículo con relación a este tema, veremos la explicación del Quick Sort.

Para llegar a comprender este algoritmo debes tener conocimientos sobre la estrategia Divide y Vencerás, que como vimos, se basa en dividir el problema en sub-problemas y, a partir de ello, dar solución al problema general. Teniendo claro esto, podemos empezar a explicar el funcionamiento del método.

Algoritmo Merge Sort

Es un método de ordenamiento por mezcla, la idea general es que: Dados dos conjuntos ordenados, A y B, si los mezclamos entre ambos, tomando los valores de ellos en orden, entonces nos va quedar el conjunto ordenado C, con los elementos de A y B.

Mezclando dos listas

Fig1: Mezclando dos listas

Partiendo de este punto, aplicaremos la estrategia Divide y Vencerás. La idea es, que si inicialmente tenemos la lista desordenada, y la dividimos a la mitad, nos quedaremos con 2 sub-listas desordenadas, entonces, realizamos otra vez la misma acción: dividimos las sub-listas resultantes en 4 nuevas sub-listas, y así sucesivamente.

Esta operación se realizará hasta que lleguemos a una sub-lista con 1 o 0 elementos en ella, que por defecto va a estar ordenada, y como dicha sub-lista ya está ordenada, la mezclamos con la de al lado, que está ordenada también, y así continuamente vamos ordenando las sub-listas hacia arriba para llegar al caso base.

Si representamos esas operaciones en una imagen (ver Fig2), puedes notar que se forma un árbol, donde, partiendo de las hojas (son los elementos terminales del árbol), se van a ordenar los nodos padres, por medio de la mezcla entre sus dos hijos, hasta llegar al nodo raíz (ver Fig3).

Árbol desordenado

Fig2: Árbol desordenado

Árbol ordenado

Fig3: Árbol ordenado

¿Por qué la complejidad es Logarítmica (N*log(N))?

Bueno, como puedes notar, solo se recorrerá el listado completamente por cada nivel del árbol que se crea, y podemos decir que al ser un árbol binario (son los árboles donde un nodo padre solo puede tener como máximo 2 nodos hijos), entonces el nivel máximo que puede llegar a tener es el logaritmo en base 2 de la cantidad de elementos, o lo que es lo mismo, log2(N). Pero en programación, cuando estudiamos la complejidad de un algoritmo determinado, acotamos las complejidades al peor de los casos que pueda tener, y por ende descartamos la base 2, para convertirla en log(N). Es así como determinamos la complejidad N*log(N) para este algoritmo de ordenamiento.

A continuación te muestro el algoritmo programado en C++, y te explico línea a línea su funcionamiento.

/**
 * Descripción de los parámetros
 *
 * @params:
 *
 * @var inicio: Inicio del intervalo a ordenar
 * @var fin   : Fin del intervalo a ordenar
 * @var lista : La lista en la que ordenaremos el intervalo, [inicio,fin] 
 *
 **/
 
void MergeSort(int inicio,int fin,int *lista){
    /*
    Si la sub-lista es de tamaño 1 o 0, se termina el método, 
    dado que esta sub-lista ya está ordenada.
    */
    if(fin - inicio == 0 || fin - inicio == 1)
        return;
    
    //determinamos el punto medio del intervalo a ordenar.
    int cursor= (inicio + fin)/2;

    //Ordenamos la sub-lista de la izquierda.
    MergeSort(inicio,cursor,lista);

    //Ordenamos la sub-lista de la derecha.
    MergeSort(cursor,fin,lista);

    int puntero1 = inicio,
        puntero2 = cursor,
        puntero3 = 0;

    /*
    Creamos un arreglo donde guardaremos la mezcla 
    de las sub-listas ordenadas.
    */
    int array[fin-inicio];
    
    //Mezclamos las sub-lista de derecha y de izquierda, en el arreglo array.
    while(puntero1<cursor || puntero2<fin){
        if(puntero1<cursor && puntero2<fin){
            if(lista[puntero1]<lista[puntero2]){
                array[puntero3++] = lista[puntero1++];
            }else{
                array[puntero3++] = lista[puntero2++];
            }
        }else if(puntero1<cursor){
            array[puntero3++] = lista[puntero1++];
        }else{
            array[puntero3++] = lista[puntero2++];
        }
    }

    /*
    Para terminar pasamos la sub-lista ordenada 
    que está en el arreglo array para la lista original.
    */
    for(int i=0;i<fin-inicio;i++){
        lista[inicio+i]=array[i];
    }
}

Conclusión

Para la comprensión a fondo de este método es necesario tener un conocimiento básico sobre recursividad, puesto que este recurso es utilizado en el código anterior.

Hasta aquí, hemos visto los principales aspectos del método de ordenamiento Merge Sort, tales como su funcionamiento, complejidad y estrategias que utiliza para llevar a cabo el ordenamiento de una lista. Por ahora me despedimo, pero nos vemos próximamente en un nuevo artículo sobre el algoritmo Quick Sort. No olvides dejar tus dudas y sugerencias en los comentarios. Hasta la próxima.

  • JO

    Muy buena la página en general. Esta sección principalmente.