Método De Ordenacion

1 – TIPOS DE ALROGITMOS

Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad.

Existe desde el método mas 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.

1.1 – 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

1.2 - METODOS RECURSIVOS

Estos métodos son aun 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 mas fácil resolverlos.

Mediante llamadas recursivas a sí mismos, es posible que el tiempo de ejecucion y de ordenación sea más optimo.

Dentro de los algoritmos recursivos encontramos:

– Ordenamiento por Mezclas (merge)

– Ordenamiento Rápido (quick)

2 – METODO DE LA 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 izquierda 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 ascendiente o descendiente) 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.

2. 1 – BURBUJA SIMPLE

Como lo describimos en el ítem anterior, la burbuja más simple de todas es la que compara todos con todos, generando comparaciones extras, por ejemplo, no tiene sentido que se compare con sigo mismo o que se compare con los valores anteriores a él, ya que supuestamente, ya están ordenados.

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;

2. 2- BURBUJA MEJORADA

Una nueva versión del método de la burbuja seria limitando el numero de comparaciones, dijimos que era inútil que se compare consigo misma. Si tenemos una lista de 10.000 elementos, entonces son 10.000 comparaciones que están sobrando.

Imaginemos si tenemos 1.000.000 de elementos. El método seria mucho mas optimo con “n” comparaciones menos (n = total de elementos).

2. 3- BURBUJA OPTIMIZADA

Si al cambio anterior (el de la burbuja mejorada) le sumamos otro cambio, el hecho que los elementos que estan detras del que se esta comparando, ya estan ordenados, las comparaciones serian aun menos y el metodo seria aun mas efectivo.

Si tenemos una lista de 10 elementos y estamos analizando el quinto elemento, que sentido tiene que el quinto se compare con el primero, el segundo o el tercero, si supuestamente, ya estan ordenados? Entonces optimizamos mas aun el algoritmo, quedando nuestra version final del algoritmo optimizado de la siguiente manera:

Bubblesort(int matriz[])

{

int buffer;

int i,j;

for(i = 0; i < matriz.length; i++)

{

for(j = 0; j < i; j++)

{

if(matriz[i] < matriz[j])

{

buffer = matriz[j];

matriz[j] = matriz[i];

matriz[i] = buffer;

}

}

}

}

3 – INSERCION Y SELECCION

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-esimo, e inserta cada uno en el lugar adecuado entre sus precedesores 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.

4 – ORDENAMIENTO POR MEZCLA

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

...