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

uml_ordenacion

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:

    ordenacion3.png

    ordenacion4.png

    ordenacion.png

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

     Saludos!!

    8 Responses to “Métodos de ordenación de forma concurrente”

    1. pe parece muy interesante .
      me puedes hacer el favor de dar el codigo fuente
      gracias

    2. Claro, se lo mando a su correo

    3. Me parecio muy interesante el desarrollo que llevo acabo, me puedes hacer el favor de darme el codigo fuente

      Muchas gracias

      Juan Sebastian

    4. Muy interesante el tema de los hilos, quisiera observar el codigo , te agradeceria muchisimo si me lo envias a mi correo.

      Mil gracias

      Alberto Benitez

    5. Me parece super bueno el ejemplo, serias tan amable de facilitarme el codigo fuente.

      Es que estoy haciendo un trabajo donde tengo que demostrar un ejemplo con threads y otro sin ellos.

      Gracias !!!

    6. muy interesante el ejemplo te agradeceria que me facilitaras el codigo fuente para checarlo

    7. hola mi estimado amigo porfavor mandame el codigo fuente en c++ grasias..

    8. hola me podrias enviar el codigo fuente a mi correo para poder pobrar y ejecutar mis pruebas

    Leave a Reply