Posts Tagged ‘java’

insertion sort <- sorting!

7 agosto 2009

Algo apasionante para algunos, divertido para otros, y completamente tonto para la mayoria es diseñar, inventar y estudiar algoritmos de ordenamiento. En mi caso, es algo que me interesa. No porque sea apasionante pasar tardes y tardes leyendo sobre esto, sino porque a la hora de probarlo es divertido ver como se ordena, y el hecho de buscar formas de superar el orden del tiempo de ejecución en cada algoritmo obtenido es un desafio bastante intersante.

A continuación presento una de las formas mas básicas, triviales e intuitivas de ordenamiento de una estructura. Es aplicable tambien a listas enlazadas, con ciertas modificaciones.

El algoritmo en cuestión se denomina Insertion-Sort, denominado así por la forma en que se toma cada elemento y se lo inserta en su nueva posición definitiva. Se ejecuta no-recursivamente sobre la estructura misma, y tiene un tiempo de ejecución del orden de N^2, siendo N el número de elementos en la estructura (ya hablaremos de esto al final).

Veamos:

procedimiento InsertionSort(Arreglo[] estructura){

N<- estructura.size() //retorna el número de elementos de la estructura

desde i=0 hasta N-1{

int index=i;

desde j=i hasta 0 {

if (estructura[index]<estructura[j]){

intercambiar(index,j,estructura)

index=j;

}

else break;//salimos porque encontramos la ubicacion final del elemento

}

}//fin procedimiento

Lo que hace, si no se entiende, es tomar cada uno de los elementos y compararlo con sus predecesores en la estructura. Si el elemento actual es menor, se intercambian. Así, una vez ubicado, no es necesario tocarlo nuevamente. Si se piensa a los elementos como burbujas, es como si los mas pesados fueran siendo desplazados hacia arriba por los mas livianos en cada iteración. El método intercambiar simplemente hace eso, intercambia los elementos ubicados en los indices pasados por parametro en la estructura señalada.

El método, implementado en Java luce así:

public static void insertionSort(int[]a){

int n=a.length;

for (int i=1;i<n;i++){

char cursor=a[i];

int j=i-1;

while((j>=0)&&(a[j]>cursor))

a[j+1]=a[j–];

a[j+1]=cursor;

}

}

A simple vista parece un algoritmo ideal: sencillo de pensar e implementar. Pero si nos ponemos a pensar, imaginemos que tenemos que ordenar algo asi como 5000 entradas (alumnos de una universidad), o peor aún, 36.000.000(votantes en un país). El algoritmo evalua cada elemento un0 a uno contra todos los otros (en realidad, contra sus predecesores). En el peor de los casos, el arreglo estará en orden decreciente y, como queremos ordenarlo de menor a mayor, cada elemento deberá moverse hacia su izquierda j-1 (j=posición del elemento en el arreglo) lugares (cabe aclarar, que el mejor escenario es un arreglo ya ordenado, donde se realizan solo N comparaciones). Esto da lugar a la siguiente ecuación:

T(N)=  N. (1 + 2 + 3 + 4 + … + (N-1))

Luego, T(N) es del orden de N^2. Algo que, si bien no es el peor de los escenarios, podría ser mucho mejor.

Para la proxima analizaremos otros métodos mas lindos e interesantes, y prometo hablar algo acerca del orden de ejecución de algoritmos, para los que no entiendan a que se refiere que insertionSort sea O(N^2).

UPaint 1.0 (java)

25 julio 2009

Siempre me sucede, como a tantos programadores, que al utilizar cierta función de cierto programa me viene a la cabeza la pregunta: ¿Cómo está hecho esto? Mas específicamente, cual es la idea detrás de todo esto. Lo que intento descubrir es como se pensaron cada una de las funciones innovadoras de cada programa mas allá del código; es decir, haciendo foco en la idea, o el algoritmo. Ejemplos que se me ocurren ya mismo: atrás y adelante en el navegador (ese es fácil), capas en los programas de diseño, buscador de coincidencias en el OpenOffice(o MS Word), etc.

El cuatrimestre anterior en la universidad nos plantearon como semi-proyecto desarrollar un programa similar al MSPaint de Windows (o el KolourPaint de KDE. Hay gente que realmente cree que el único programa de dibujo es el paint de windows! ). Fue un gran ejercicio porque, a pesar que solo nos exigieron las funciones mas básicas (dibujo de línea, cambios de colores, y poco más), decidí ir mas allá e investigué algo acerca del resto, no incluidas en el trabajo. Entre ellas, el “aerosol”, el dibujo de cuadrado/circulo, y opciones para determinar el trazo.

A pesar de todo, como todo gran proyecto universitario, se pinchó con la venida del verano y el UPaint 1.0 ( así lo llamé), quedó solo en eso: una pobretona versión 1.0 que incluye algunas funciones, algunas a medias, y otras propuestas pero no implementadas. El que desee puede terminarlo, publicarlo, mejorarlo, preguntarme cualquier cosa o incluso sugerir algo.

Así sin mas les dejo el código para que cada uno haga con él lo que desee y una imagen de como se ve el proyecto cargado en Bluej. (*)

(*) El código esta escrito en Java. Para visualizarlo correctamente, lo ideal sería que lo abran con el BlueJ (DESCARGAR); solo basta elegir la carpeta donde estan las fuentes y el programa carga todo de una. Ideal para novatos en el lenguaje. Ademas, muestra una interfaz gráfica con flechas y cuadros para orientarse entre las clases y entender mejor la jerarquía encuanto a las herencias. Si prefieren abrirlo con el Eclipse (u otro editor), es probable que tengan que importarlo a una carpeta y modificar el encabezado de cada archivo agregandole el paquete correspondiente (eclipse lo hace muy fácil, basta hacer un par de clicks..).