Algoritmos

Algoritmos de Ordenamiento
Fernando A. Lagos B.
Copyleft 2007
INDICE
1 Introduccion Pag. 3
2 Tipos de Algoritmos Pag. 4
2.1 Algoritmos iterativos Pag. 5
2.2 Algoritmos recursivos Pag. 6
3 Metodo de la Burbuja Pag. 7
3.1 Burbuja Simple Pag. 8
3.2 Burbuja Mejorada Pag. 9
3.3 Burbuja Optimizada Pag. 10
4 Insercion y seleccion Pag. 11
5 Ordenamiento por Mezcla Pag. 12
6 Metodo ShellsortPag. 14
7 Metodo Rapido (quicksort) Pag. 15
8 Complejidad Pag. 17
1 - INTRODUCCION
Los algoritmos de ordenamiento nos permite, como su nombre lo dice, ordenar. En
este caso, nos serviran para ordenar vectores o matrices con valores asignados
aleatoriamente. Nos centraremos en los metodos mas populares, analizando la
cantidad de comparaciones que suceden, el tiempo que demora y revisando elcodigo,
escrito en Java, de cada algoritmo.
Este informe nos permitira conocer mas a fondo cada metodo distinto de
ordenamiento, desde uno simple hasta el mas complejo. Se realizaran comparaciones
en tiempo de ejecucion, pre-requisitos de cada algoritmo, funcionalidad, alcance, etc.
2 – TIPOS DE ALROGITMOS
Para poder ordenar una cantidad determinada de numeros almacenadas en un vector omatriz, existen distintos metodos (algoritmos) con distintas caracteristicas y
complejidad.
Existe desde el metodo mas simple, como el Bubblesort (o Metodo Burbuja), que son
simples iteraciones, hasta el Quicksort (Metodo Rapido), que al estar optimizado
usando recursion, su tiempo de ejecucion es menor y es mas efectivo.
2.1 – METODOS ITERATIVOS
Estos metodos son simples de entender y deprogramar ya que son iterativos, simples
ciclos y sentencias que hacen que el vector pueda ser ordenado.
Dentro de los Algoritmos iterativos encontramos:
– Burbuja
– Insercion
– Seleccion
– Shellsort
2.2 - METODOS RECURSIVOS
Estos metodos son aun mas complejos, requieren de mayor atencion y conocimiento
para ser entendidos. Son rapidos y efectivos, utilizan generalmente la tecnica Divide
yvencerás, que consiste en dividir un problema grande en varios pequenos para que
sea mas facil resolverlos.
Mediante llamadas recursivas a si mismos, es posible que el tiempo de ejecucion y de
ordenacion sea mas optimo.
Dento de los algoritmos recursivos encontramos:
– Ordenamiento por Mezclas (merge)
– Ordenamiento Rapido (quick)
3 – METODO DE LA BURBUJA
El metodo de la burbuja es uno delos mas simples, es tan facil 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 posicion.
Por ejemeplo, imaginemos que tenemos los siguientes valores:
5 6 1 0 3
Lo que haria 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 el0 y con el 3, si
es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se
intercambian de posicion. 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 condicion
que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.
3. 1 – BURBUJA SIMPLE
Como lo describimos enel item anterior, la burbuja mas 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
el, ya que supuestamente, ya estan ordenados.
for (i=1; i 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 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 segun corresponda:
private static void merge(int[ ] matrix, int init, int n1, int n2)
{
int[ ]...