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;

}

Metodos Iterativos

Método de Burbuja

El método de la burbuja es uno de los más simples, es tan fácil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de posición.

Por ejemplo, imaginemos que tenemos los siguientes valores:

5

6

1

0

3

Lo que haría una burbuja simple, seria comenzar recorriendo los valores de izq.  a derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3, si es mayor o menor (dependiendo si el orden es ascendente o descendente) se intercambian de posición. Luego continua con el siguiente, con el 6, y lo compara con todos los elementos de la lista, esperando ver si se cumple o no la misma condición que con el primer elemento. Así, sucesivamente, hasta el último elemento de la lista.

La estructura de este método es la siguiente:

 for (i=1; i<LIMITE; i++){

     for j=0 ; j<LIMITE - 1; j++){

         if (vector[j] > vector[j+1]){

             temp = vector[j];

             vector[j] = vector[j+1];

             vector[j+1] = temp;

         }

    }

}

Métodos de Inserción y Selección

El bucle principal de la ordenación por inserción va examinando sucesivamente todos los elementos de la matriz desde el segundo hasta el n-ésimo, e inserta cada uno en el lugar adecuado entre sus predecesores dentro de la matriz.

La ordenación por selección funciona seleccionando el menor elemento de la matriz y llevándolo al principio; a continuación selecciona el siguiente menor y lo pone en la segunda posición de la matriz y así sucesivamente.

La estructura de estos métodos es la siguiente:

Insercion(int matrix[]){

    int i, temp, j;

    for (i = 1; i < matrix.length; i++){

        temp = matrix[i];

        j = i - 1;

        while ( (matrix[j] > temp) && (j >= 0) ){

            matrix[j + 1] = matrix[j];

            j--;

        }

        matrix[j + 1] = temp;

    }

}

Seleccion(int[]matrix){

    int i, j, k, p, buffer, limit = matrix.length-1;

    for(k = 0; k < limit; k++){

        p = k;

        for(i = k+1; i <= limit; i++)

            if(matrix[i] < matrix[p]) p = i;

                if(p != k){

                    buffer = matrix[p];

                    matrix[p] = matrix[k];

                    matrix[k] = buffer;

                }

            }

         }

El bucle principal de la ordenación por inserción va examinando sucesivamente todos los elementos de la matriz desde el segundo hasta el n-ésimo, e inserta cada uno en el lugar adecuado entre sus predecesores dentro de la matriz.

La ordenación por selección funciona seleccionando el menor elemento de la matriz y llevándolo al principio; a continuación selecciona el siguiente menor y lo pone en la segunda posición de la matriz y así sucesivamente.

Método Shell Short

Este método es una mejora del algoritmo de ordenamiento por Inserción (Insertsort).

Si tenemos en cuenta que el ordenamiento por inserción es mucho más eficiente si nuestra lista de números esta semi-ordenada y que desplaza un valor una única posición a la vez.

Durante la ejecución de este algoritmo, los números de la lista se van casi-ordenando y finalmente, el último paso o función de este algoritmo es un simple método por inserción que, al estar casi-ordenados los números, es más eficiente.

El algoritmo de este método es el siguiente:

public void shellSort(int[] matrix) {

    for ( int increment = matrix.length / 2; increment > 0; increment =

    (increment == 2 ? 1 : (int) Math.round(increment / 2.2)))

    {

            for (int i = increment; i < matrix.length; i++)

        {

                for (int j = i; j >= increment && matrix[j - increment] >

                matrix[j]; j -= increment)

            {

                     int temp = matrix[j];

                     matrix[j] = matrix[j - increment];

                     matrix[j - increment] = temp;

            }

        }

    }

}

Métodos de Ordenamiento de Vectores en Java

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En

este caso, nos servirán para ordenar vectores o matrices con valores asignados

aleatoriamente. Nos centraremos en los métodos más populares, analizando la

cantidad de comparaciones que suceden, el tiempo que demora y revisando el código,

escrito en Java, de cada algoritmo.

Este blog nos permitirá conocer mas a fondo cada método distinto de

ordenamiento, desde uno simple hasta el mas complejo. Se realizaran comparaciones

en tiempo de ejecución, pre-requisitos de cada algoritmo, funcionalidad, alcance, etc.

Existe desde el método más simple, como el Bubblesort (o Método Burbuja), que son Simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

METODOS ITERATIVOS

Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

Dentro de los Algoritmos iterativos encontramos:

• Burbuja
• Inserción
• Selección
• Shellsort

Para mas información acerca de los métodos iterativos has click en el subtitulo o busca el artículo en la parte derecha de este blog ;)

METODOS RECURSIVOS

Estos métodos son aún más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos.

Mediante llamadas recursivas a sí mismas, es posible que el tiempo de ejecución y de ordenación sea más óptimo.

Dentó de los algoritmos recursivos encontramos:

• Ordenamiento por Mezclas (merge)
• Ordenamiento Rápido (quick)

Para mas información acerca de los métodos recursivos has click en el subtitulo o busca el artículo en la parte derecha de este blog ;)