Métodos Recursivos

Ordenamiento por mezclas (Merge)

Este algoritmo consiste básicamente en dividir en partes iguales la lista de números y luego mezclarlos comparándolos, dejándolos ordenados.

Si se piensa en este algoritmo recursivamente, podemos imaginar que dividirá la lista hasta tener un elemento en cada lista, luego lo compara con el que está a su lado y según corresponda, lo sitúa donde corresponde.

El algoritmo de ordenamiento por mezcla (Mergesort) se divide en dos procesos, primero se divide en partes iguales la lista:

public static void mergesort(int[ ] matrix, int init, int n) {

    int n1;

    int n2;

    if (n > 1){

        n1 = n / 2;

        n2 = n - n1;

        mergesort(matrix, init, n1);

        mergesort(matrix, init + n1, n2);

        merge(matrix, init, n1, n2);

    }

}

Y el algoritmo que nos permite mezclar los elementos según corresponda:

private static void merge(int[ ] matrix, int init, int n1, int n2) {

    int[ ] buffer = new int[n1+n2];

    int temp = 0;

    int temp1 = 0;

    int temp2 = 0;

    int i;

    while ((temp1 < n1) && (temp2 < n2)) {

        if (matrix[init + temp1] < matrix[init + n1 + temp2])

            buffer[temp++] = matrix[init + (temp1++)];

        else

            buffer[temp++] = matrix[init + n1 + (temp2++)];

    }

    while (temp1 < n1)

        buffer[temp++] = matrix[init + (temp1++)];

        while (temp2 < n2)

            buffer[temp++] = matrix[init + n1 + (temp2++)];

        for (i = 0; i < n1+n2; i++)

            matrix[init + i] = buffer[i];

}

Ordenamiento Rápido (Quick)

Sin duda, este algoritmo es uno de los mas eficientes. Este metodo es el mas rápido gracias a sus llamadas recursivas, basandose en la teoria de divide y vencerás.

Lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales, indicando un elemento de inicio, fin y un pivote (o comodin) que nos permitirá segmentar nuestra lista. 

Una vez dividida, lo que hace, es dejar todos los mayores que el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros elementos estan ordenados.

Por ejemplo, si tenemos 3 5 4 8 basicamente lo que hace el algoritmo es dividir la lista de 4 elementos en partes iguales, por un lado 3, por otro lado 4 8 y como comodin o pivote el 5. 

Luego pregunta, 3 es mayor o menor que el comodin? Es menor, entonces lo deja al lado izq. Y como se acabaron los elementos de ese lado, vamos al otro lado. 4 Es mayor o menor que el pivote? Menor, entonces lo tira a su izq. Luego pregunta por el 8, al ser mayor lo deja donde esta, quedando algo asi:

3

4

5

8

En esta figura se ilustra de mejor manera un vector con mas elementos, usando como pivote el primer elemento:

El algoritmo de este método de ordenamiento es el siguiente:

public void _Quicksort(int matrix[], int a, int b) {

    this.matrix = new int[matrix.length];

    int buf;

    int from = a;

    int to = b;

    int pivot = matrix[(from+to)/2];

    do {

         while(matrix[from] < pivot){

         from++;

    }

    while(matrix[to] > pivot){

        to--;

    }

    if(from <= to){

        buf = matrix[from];

       matrix[from] = matrix[to];

       matrix[to] = buf;

       from++; to--;

    }

}while(from <= to);

if(a < to){

    _Quicksort(matrix, a, to);

}

if(from < b) {

    _Quicksort(matrix, from, b);

}

this.matrix = matrix;

}