Métodos de ordenación de forma concurrente

INTRODUCCIÓN

Un hilo de ejecución, en sistemas operativos, es una característica que permite a una aplicación realizar varias tareas concurrentemente. Los distintos hilos de ejecución comparten una serie de recursos tales como el espacio de memoria, los archivos abiertos, situación de autenticación, etc. Esta técnica permite simplificar el diseño de una aplicación que debe llevar a cabo distintas funciones simultáneamente.(wikipedia.org)

Los hilos de ejecución que comparten los mismos recursos, sumados a estos recursos, son en conjunto conocidos como un proceso. El hecho de que los hilos de ejecución de un mismo proceso compartan los recursos hace que cualquiera de estos hilos pueda modificar éstos. Cuando un hilo modifica un dato en la memoria, los otros hilos acceden e ese dato modificado inmediatamente.

PROBLEMA

Se trata de ordenar un array de datos de N dimensión mediante 3 métodos de ordenación. Estos métodos se ejecutarán de forma concurrente, es decir, “al mismo tiempo”. Debido a que ya hay bastante información en Internet sobre los hilos, no tiene caso explicar su funcionamiento, en vez de ello, quien no tenga muy claro el tema de hilos, les dejo algunos enlaces que deben leer antes de continuar:

http://rt00149b.eresmas.net/Otras/ConcurrenciaJAVA/

http://www.itapizaco.edu.mx/paginas/JavaTut/froufe/parte10/cap10-1.html

http://www.chuidiang.com/java/hilos/hilos_java.php

HERRAMIENTAS

• Sistema Operativo Linux (Mandriva 2007)
• JDK 1.6
• IDE NetBeans 6.0

DESARROLLO

Como se observa en el Diagrama de clases UML, el programa se compone de 3 clases:

1.- Burbuja
2.- Inserción
3.- QuickSort

Y una clase principal desde donde se genera el array con los elementos aleatorios a ordenar y se ejecutan los 3 hilos correspondientes a los 3 métodos por los cuales se ordenará el array.

Estas tres clases implementan a la interfaz Runnable para poder hacer uso de los hilos, también se pudo haber heredado de la clase Thread. En el método run de Runnable es donde se debe colocar el código que se desea ejecutar como un hilo, en nuestro caso es donde se codificarán los algoritmos de Burbuja, Inserción, y QuickSort. Además, como se observa, se cuenta con un método imprimir() el cuál imprimirá el array ya ordenado.

La clase principal es Test, desde donde se pide al usuario introduzca la dimensión del array, para este fin se utiliza la clase Scanner implementada a partir del JDK 1.5 que toma como parámetro la salida estandar System.in

Scanner in = new Scanner(System.in);

Y con sus métodos, nextInt, nextDouble, etc., se obtiene la salida del teclado.

Para generar los números aleatorios se utiliza la clase Random localizada en el paquete java.util

public void generaDatos()
{
System.out.println(”\n ************* DATOS GENERADOS ALEATORIAMENTE***************\n”);
for(int i = 0; i <= datos.length-1; i++)
{
dato = Double.parseDouble(formato.format(rnd.nextDouble()*100));
datos[i] = dato;
System.out.println(i + “.- “+ dato);
}
}

La diferencia de tiempos entre los 3 métodos implementados es muy notoria, QuickSort es un método bastante rápido para la ordenación de datos, mientras que el método burbuja tarda en ordenar 100,000 datos en más de 1 minuto, el QuickSort los ordena en menos de 2 segundos.

A continuación algunas pantallas del programa en ejecución:

Puedes solicitarme el código fuente enviandome un correo electrónico o dejando un comentario.

 Saludos!!