La tarea de la
programación esta ligada al objetivo de obtener algoritmos que resuelvan un
problema con la mayor eficiencia posible; de hecho es sorprendente comprobar
las múltiples formas como podemos resolver un mismo problema y las ventajas que
conseguimos , en términos de eficiencia , al buscar soluciones alternativas a
las ya conocidas o consideradas como evidentes.
Para comparar y analizar la eficiencia de los algoritmos , estos los
consideramos escritos en un lenguaje de programación de alto nivel ,
pero aun empleando la misma representación , establecer
una medida precisa de la eficiencia de un algoritmo no
es fácil.En efecto
, fijémonos en que una definición de eficiencia podría ser
el numero de instrucciones que tiene el programa ; sin embargo esto no
se correspondería , con el concepto intuitivo que tenemos de
eficiencia(según el cual,el algoritmo mas eficiente seria
aquel que tardase menos tiempo en resolver el problema sobre una misma
maquina), dado que todas las instrucciones no utilizan el mismo tiempo de
procesador aun realizando la misma función.
MÉTODOS DE ORDENACIÓN:
En computación y
matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de
una lista o un vector en una secuencia dada por una relación de orden, es
decir, el resultado de salida ha de ser una permutación o reordenamiento
de la entrada que satisfaga la relación de orden dada. Los ordenamientos
eficientes son importantes para optimizar el uso de otros algoritmos (como los
de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida.
También es útil para poner datos en forma canónica y para generar resultados
legibles por humanos.
MÉTODO DE
ORDENAMIENTO BURBUJA:
Este es uno de los métodos de
ordenamiento mas usados .aunque no de los mas eficaces.
Consiste en recorrer la lista de valores a
ordenar y compararlos dos a dos.Si los
elementos están bien ordenados, pasamos al siguiente , hasta
llegar al final de la lista.El proceso completo se repite hasta que la lista
este ordenada.
Algoritmo:
DESDE I=1 hasta N-1
hacer
DESDE J=1 hasta N-1 hacer
Si v[J]>V[J+1] entonces
Aux= V[J]
V[J]=V[J+1]
V[J+1]=Aux
FIN SI
FIN DESDE
FIN DESDE
Análisis de Complejidad:
El ciclo interno se ejecuta n veces para una lista de n elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).
Implementación
public int burbuja(int[] arreglo)
{
int aux,num_intercambios=0;
for(int i=1;i < arreglo.length;i++)
{
for (int j=0 ; j < arreglo.length- 1; j++)
{
if (arreglo[j] > arreglo[j+1])
{
aux = arreglo[j];
arreglo[j] = arreglo[j+1];
arreglo[j+1] = aux;
num_intercambios++;
}
}
}
//Nos retorna el numero de operaciones que hace referencia a la complejidad
//Si desea obtener la lista de valores ordenados , recuperar este valor a través de un método get
return num_intercambios;
}
MÉTODO DE ORDENACIÓN INSERCIÓN:
La idea de este algoritmo de ordenación
consiste en ir insertando un elemento de la lista o un arreglo en la parte
ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el
algoritmo ira comparando un elemento de la parte desordenada de la lista con
los elementos de la parte ordenada, insertando el elemento en la posición
correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la
lista ordenada. Para explicarlo mejor nos basaremos en el siguiente enunciado:
“Para cada elemento de la lista después
del primero, comparar los elementos con los anteriores desplazando una posición
a la derecha a todos los elementos anteriores que cumplan con la comparación y
luego colocar el elemento en la posición del último elemento anterior
desplazado.”
Algoritmo:
for (i=1; i<TAM; i++)
aux = array[i];
j = i - 1;
while ( (array[j] > aux) && (j >= 0) )
array[j+1] = array[j];
j--;
array[j+1] = aux;
aux = array[i];
j = i - 1;
while ( (array[j] > aux) && (j >= 0) )
array[j+1] = array[j];
j--;
array[j+1] = aux;
Análisis de la Complejidad:
Implementación:
//METODO DE ORDENACION : INSERCION
public int Insercion(int[] array){
int aux,num_intercambios=0;
for (int i = 1; i < array.length; i++) {
aux = array[i];
for (int j = i-1; j > =0 && array[j] > aux; j--) {
array[j+1]=array[j];
array[j]=aux;
num_intercambios++;
}
}
//Nos retorna el numero de operaciones que hace referencia a la complejidad
//Si desea obtener la lista de valores ordenados , recuperar este valor a través de un método get
return num_intercambios;
}
MÉTODO DE ORDENACIÓN QUICKSORT:
Sin duda, este algoritmo es uno de los más
eficientes. Este método es el más rápido gracias a sus llamadas recursivas, basándose
en la teoría de divide y vencerás.
Lo que hace este algoritmo es dividir recursivamente
el vector en partes iguales, indicando un elemento de inicio, fin y un pivote
(o comodín) 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 izquierda Al finalizar el algoritmo, nuestros elementos están ordenados.
Por ejemplo, si tenemos 3 5 4 8 básicamente
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 comodín o pivote el 5. Luego pregunta,
3 es mayor o menor que el comodín? Es menor, entonces lo deja al lado izquierda 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 izquierda. Luego pregunta por el 8,
al ser mayor lo deja donde está, quedando algo así: 3 4 5 8.
En esta figura se ilustra de mejor manera
un vector con más elementos, usando como pivote el primer elemento:
Algoritmo
// Inicialización de variables
elem_div = lista[sup];
i = inf - 1;
j = sup;
cont = 1;
// Verificamos que no se crucen los límites
if (inf >= sup)
retornar;
// Clasificamos la sublista
while (cont)
while (lista[++i] < elem_div);
while (lista[--j] > elem_div);
if (i < j)
temp = lista[i];
lista[i] = lista[j];
lista[j] = temp;
else
cont = 0;
// Copiamos el elemento de división
// en su posición final
temp = lista[i];
lista[i] = lista[sup];
lista[sup] = temp;
// Aplicamos el procedimiento
// recursivamente a cada sublista
OrdRap (lista, inf, i - 1);
OrdRap (lista, i + 1, sup);
Análisis de la Complejidad:
Caso promedio: La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como:
f(1) = 1
f(n) = n + 2 f(n/2)
La forma cerrada de esta expresión es:
f(n) = n log2n
Es decir, la complejidad es O(n log2n).
El peor caso ocurre cuando la lista ya está ordenada, porque cada llamada genera sólo una sublista (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n2).
Implementación
//METODO DE ORDENACION: QUICKSORT
public int ordenacionRapida(int[] v) {
final int N = v.length;
quicksort(v,0,N-1);
return num_intercambios_qs;
}
public void quicksort(int A[], int izq, int der) {
int pivote=A[izq]; // tomamos primer elemento como pivote
int i=izq; // i realiza la búsqueda de izquierda a derecha
int j=der; // j realiza la búsqueda de derecha a izquierda
int aux;
while(i< j){ // mientras no se crucen las búsquedas
while(A[i]< =pivote && i< j) i++; // busca elemento mayor que pivote
while(A[j] > pivote) j--; // busca elemento menor que pivote
if (i< j) { // si no se han cruzado
aux= A[i]; // los intercambia
A[i]=A[j];
A[j]=aux;
}
num_intercambios_qs++;
}
A[izq]=A[j]; // se coloca el pivote en su lugar de forma que tendremos
A[j]=pivote; // los menores a su izquierda y los mayores a su derecha
if(izq< j-1)
quicksort(A,izq,j-1); // ordenamos subarray izquierdo
if(j+1 < der)
quicksort(A,j+1,der); // ordenamos subarray derecho
}
MÉTODO DE ORDENACIÓN MERGESORT:
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.
En la siguiente
figura podemos ver cómo funciona:
Análisis de la Complejidad:
La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como:
f(1) = 1
f(n) = n + 2 f(n/2)
La forma cerrada de esta expresión es:
f(n) = n log2n
Es decir, la complejidad es O(n log2n).
Implementación:
//METODO DE ORDENACION: MERGESORT
public int MergeSort(int a[], int iMin, int iMax)
{
mergeSort (a,iMin,iMax) ;
return num_intercambios_ms;
}
public void mergeSort (int a[], int iMin, int iMax)
{
// Caso Base
if(iMin >= iMax)
{
return;
}
// Cortamos para aplicar mergeSort recursivamente
int k = (iMin+iMax) / 2;
mergeSort(a, iMin, k);
mergeSort(a, k+1, iMax);
// Utilizamos un arreglo temporal
int l = iMax-iMin+1;
int temp[] = new int[l];
for(int i = 0; i < l; i++)
{
temp[i] = a[iMin+i];
}
// Mezclamos
int i1 = 0;
int i2 = k-iMin+1;
for(int i = 0; i < l; i++)
{
if(i2 < = iMax-iMin)
{
if(i1 < = k-iMin)
{
if(temp[i1] > temp[i2])
{
a[i+iMin] = temp[i2++];
}
else
{
a[i+iMin] = temp[i1++];
}
}
else
{
a[i+iMin] = temp[i2++];
}
num_intercambios_ms++;
}
else
{
a[i+iMin] = temp[i1++];
num_intercambios_ms++;
}
}
}
MÉTODO DE ORDENACIÓN HEAPSORT
Este algoritmo consiste en almacenar
todos los elementos del vector a ordenar en un montículo (heap), y luego
extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteracciones
obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los
montículos, por la cual, la cima contiene siempre el menor elemento (o el
mayor, según se haya definido el montículo) de todos los almacenados en él. El
algoritmo, después de cada extracción, re coloca en el nodo raíz o cima, la
última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap
del árbol. Pero, a continuación realiza un proceso de "descenso" del
número insertado de forma que se elige a cada movimiento el mayor de sus dos
hijos, con el que se intercambia. Este intercambio, realizado sucesivamente
"hunde" el nodo en el árbol restaurando la propiedad montículo del árbol
y dejando paso a la siguiente extracción del nodo raíz.
Análisis de Complejidad:
Implementación:
// METODO DE ORDENACION: HEAP SORT
public int ordenacionMonticulos(int[] v)
{
final int N = v.length;
for(int nodo = N/2; nodo >=0; nodo--) hacerMonticulo(v, nodo, N-1);
for(int nodo = N-1; nodo >=0; nodo--) {
int tmp = v[0];
v[0] = v[nodo];
v[nodo] = tmp;
hacerMonticulo(v, 0, nodo-1);
}
return num_intercambios_hs;
}
public void hacerMonticulo(int[] v, int nodo, int fin)
{
int izq = 2*nodo+1;
int der = izq+1;
int may;
if(izq >fin) return;
if(der >fin)
{
may=izq;
num_intercambios_hs++;
}
else
{
if(v[izq] >v[der])
may= izq;
else
may=der;
num_intercambios_hs++;
}
if(v[nodo] < v[may])
{
int tmp = v[nodo];
v[nodo] = v[may];
v[may] = tmp;
num_intercambios_hs++;
hacerMonticulo(v, may, fin);
num_intercambios_hs++;
}
}
Fuente Teóricas:
Wikipedia, algunos documentos de Prezzi, apuntes de Clase.
