Sigueme en Facebook Sigueme en Twitter Sigueme en Instagram Sigueme en Youtube
JC Mouse Bolivia
Index / Java / Ordenación de burbuja animado

Ordenación de burbuja animado

Autor jc mouse lunes, septiembre 7, 2015

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Este algoritmo es esencialmente un algoritmo de fuerza bruta lógica.

¿Como funciona?

Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.

Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas “burbujas“. También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Problema. Escriba el código que implemente el algoritmo de ordenación Bubble Sort para “n” números, el proceso de ordenamiento se debe visualizar en una interfaz animada

Solución

Se mostrara cada numero en su propia casilla con un color distinto, en lugar de hacer uso de algún componente gráfico (Jlabel,Button, TextField, etc), se prefiere usar java2d para pintar directamente las figuras en el lienzo. La clase destina a este objetivo es la clase BixNumber:

Clase BoxNumber

package com.bolivia.burbuja;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.Graphics2D;
import java.awt.Polygon;
import java.awt.font.FontRenderContext;
import java.awt.font.TextLayout;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.util.Random;

/**
 * @web https://www.jc-mouse.net/
 * @author Mouse
 */
public class BoxNumber {

    private Font font           =       new Font("Tahoma", Font.BOLD, 16); 
    private String number       =       "0";
    public int WIDTH            =       60;
    public int HEIGHT           =       32;    
    public int x;
    public int y;    
    private Color colorBg;
    private Dimension dimensionText;
    private Color[] color       = {     new Color(255,0,0),
                                        new Color(36,0,255),
                                        new Color(255,0,246),
                                        new Color(0,246,255),
                                        new Color(48,255,0),
                                        new Color(240,225,0),
                                        new Color(255,174,0),
                                        new Color(0,186,255)
                                };
    /**
 * Constructor de clase
 */
    public BoxNumber(){
        Random rn = new Random();        
        colorBg =  color[rn.nextInt(color.length)];
    }

    public void draw(Graphics2D g2){

        Polygon boxPolygon = new Polygon();
        boxPolygon.addPoint( x, y );  
        boxPolygon.addPoint( x+WIDTH, y );  
        boxPolygon.addPoint( x+WIDTH, y+ HEIGHT );  
        boxPolygon.addPoint( x, y + HEIGHT ); 

        g2.setColor( colorBg );
        g2.fillPolygon( boxPolygon );
        g2.setColor( new Color(0,0,0) );
        g2.drawPolygon( boxPolygon );

        if(getNumber().length()>0){            
            g2.setFont( font ); 
            g2.drawString( getNumber(), x+(WIDTH/2-dimensionText.width/2), y + HEIGHT/2 + dimensionText.height/2);        
        }

    }

    public String getNumber() {
        return number;
    }

    public void setNumber(String number) {
        this.number = number;
        dimensionText = calculateFontDimension(number);
    }

    public int getValue() {
        return Integer.valueOf(number);
    }

    /**
 * Obtiene las dimensiones de un texto
 * @param String texto
 * @return Dimension
 */
     private Dimension calculateFontDimension(String text){       
            BufferedImage image = new BufferedImage(1, 1, BufferedImage.TYPE_INT_ARGB);
            Graphics2D g2 = image.createGraphics();            
            g2.setStroke(new BasicStroke(0.0f));
            FontRenderContext frc = g2.getFontRenderContext();
            TextLayout layout = new TextLayout(text, font, frc);
            layout.draw(g2, 0, 0);
            Rectangle2D bounds = layout.getBounds();
            bounds.setRect(bounds.getX(),
                  bounds.getY(),
                  bounds.getWidth(),
                  bounds.getHeight());
            int w = (int) bounds.getWidth();
            int h = (int) bounds.getHeight();            
            g2.draw(bounds);
            g2.dispose();
            return new Dimension(w,h);
        }

}

Ya que se esta pintando las casillas directamente en un lienzo, en este caso un JPanel, se debe sobreescribir el método paintComponent. Asi también, como se pide animar el método de ordenación, se hará uso de un SwingWorker para trabajar en un hilo paralelo al de la aplicación, esto se hace así, para evitar congelar la interfaz hasta que se termine de ejecutar el método de ordenación. La clase se llama BurbujaPanel 

Clase BurbujaPanel

package com.bolivia.burbuja;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.geom.Rectangle2D;
import java.util.Random;
import javax.swing.JPanel;
import javax.swing.SwingWorker;

/**
 * @web https://www.jc-mouse.net/
 * @author Mouse
 */
public class BurbujaPanel extends JPanel{

    private int NUM_BOX                 =       5;
    private Dimension dimension         =       new Dimension(320,128);    
    private int max                     =       12;
    private int min                     =       1;
    private BoxNumber[] bNumber;

    /**
 * Constructor de clase
 */
    public BurbujaPanel(){
        setSize(dimension);
        setVisible(true);                
    }

    @Override
    public void paintComponent(Graphics g){    
        Graphics2D g2 =(Graphics2D) g;
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,RenderingHints.VALUE_ANTIALIAS_ON);    
        g2.setColor( new Color(255,255,255) );
        g2.fill(new Rectangle2D.Double(0,0,getWidth(),getHeight()));                 
        //pinta numeros y casillas
        if(bNumber!=null)
        for(BoxNumber b:bNumber){
            b.draw(g2);
        }

    }

    /**
 * Genera 5 numeros al azar y asigna a casillas
 * posicion las casillas en el panel
 */
    public void generar(){       
        bNumber = new BoxNumber[NUM_BOX];
        Random rn = new Random();
        for(int i=0;i<NUM_BOX;i++){
            bNumber[i] = new BoxNumber();    
            bNumber[i].x= 10 + bNumber[i].WIDTH * i;
            bNumber[i].y = getHeight()/2 - bNumber[i].HEIGHT/2 ;
            int num = rn.nextInt(max - min + 1) + min;
            bNumber[i].setNumber(String.valueOf(num));
        }
        repaint();
    }

    /**
 * Comando para ordenar el array de numeros con el metodo de la burbuja
 */
    public void ordenar(){
        if(bNumber!=null)        
            new BurbujaWorker().execute();//inicia worker
    }

    /**
 * Clase 
 */ 
    public class BurbujaWorker extends SwingWorker<Void, Void> {

        private int SPEED = 11; //velocidad de animacion (milisegundos) 

        @Override
        protected Void doInBackground() throws Exception {

         int i, j;
         BoxNumber aux;
         for(i=0;i<bNumber.length-1;i++)
            for(j=0;j<bNumber.length-i-1;j++)
                if(bNumber[j+1].getValue()<bNumber[j].getValue()){
                      aux=bNumber[j+1];
                      //animar movimiento
                      girar(j,j+1);                      
                      bNumber[j+1]=bNumber[j];
                      bNumber[j]=aux;
                   }         
            return null;
        }

        /**
 * 
 */
        private void girar(int a , int b){
            //movmiento vertical
            for(int i=0; i< bNumber[0].HEIGHT;i++){
                bNumber[a].y -= 1;
                bNumber[b].y += 1;                   
                try {
                    Thread.sleep(SPEED);
                 } catch (InterruptedException e) {}
                repaint();
            }

            //vomiento horizontal
            for(int i=0; i< bNumber[0].WIDTH;i++){
                 bNumber[a].x += 1;
                 bNumber[b].x -= 1;
                 try {
                    Thread.sleep(SPEED);
                 } catch (InterruptedException e) {}
                repaint();
            }

            //movimiento vertical
            for(int i=0; i< bNumber[0].HEIGHT;i++){
                bNumber[a].y += 1;
                bNumber[b].y -= 1;                   
                try {
                    Thread.sleep(SPEED);
                 } catch (InterruptedException e) {}
                repaint();
            }
        }

    }

}//BurbujaPanel:end

Finalmente la interfaz de usuario solo comprenderá el lienzo “BurbujaPanel” y dos botones colocados en un JFrame como se muestra en la siguiente figura:

bubble java

La clase BurbujaPanel que definimos más arriba la cuenta los metodos para generar numeros y ordenar la lista de numeros, se implementa en la interfaz de la siguiente manera:

  private void jButton1ActionPerformed(java.awt.event.ActionEvent evt) {                                         
        burbujaPanel1.ordenar();
    }                                        

    private void jButton2ActionPerformed(java.awt.event.ActionEvent evt) {                                         
         burbujaPanel1.generar();
    }

Ejecutando el programa tenemos

burbuja java

Descargar proyecto: Bubble Sort

Tags

Si te ha gustado podrías compartirlo o dejar un comentario. ¡Muchas gracias!
Autor: JC Mouse

Yo soy yo :) JC Mouse, Soy orgullosamente boliviano soy fundador y CEO de la web jc-Mouse.net uno de las pocas web en emprendimiento y tecnología en Bolivia.

Toda la información que encuentres en este sitio es y sera completamente gratis siempre, puedes copiar, descargar y re-publicar si así lo deseas en otros blogs o sitios web, solo te pido a cambio que dejes una referencia a esta web. Esto nos ayuda a crecer y seguir aportando. Bye

Enjoy! :)

También Te Podría Interesar

Bandera en Alto

Bandera en Alto

EL 6 de agosto de cada año se recuerda una de las fechas más importantes de la historia boliviana, porque el 6 de Agosto...

Fragmentos dinamicos y eventos de usuario

Fragmentos dinamicos y eventos de usuario

Continuando con los tutoriales sobre fragmentos en android, en esta oportunidad veremos como añadir Fragments dinámicame...

Laberinto del Terror (Código Fuente + juego)

Laberinto del Terror (Código Fuente + juego)

El laberinto del terror es un juego en el que haciendo uso del ratón y de tu pulso de borracho debes cruzar distintos la...

Pruebas instrumentadas con Espresso

Pruebas instrumentadas con Espresso

Espresso es un framework de testing propiedad de Google que está dirigido a desarrolladores que creen que las pruebas au...

Filtros con JMF y una webcam [Proyecto]

Filtros con JMF y una webcam [Proyecto]

En esta oportunidad dejo a consideracion un proyecto para la captura de video desde una webcam, utilizando filtros como...

Gestión de Stock – La Vista (Parte 3)

Gestión de Stock – La Vista (Parte 3)

En esta tercera parte del tutorial crearemos la interfaz de usuario GUI (VISTA) para el sistema de gestión de stock. Tom...

Comparte lo que sabes

Categorias

Últimas entradas

“MyBatis es una herramienta de persistencia Java que se encarga de mapear sentencias SQL y procedimientos almacena...

MyBatis es un framework de persistencia Java que se encarga de mapear sentencias SQL y procedimientos almacenados a part...

Webcam Capture es un API  que permite usar una cámara web incorporada o externa directamente desde código Java utilizand...

im4java es una interfaz pura de Java para la línea de comandos de ImageMagick. La interfaz de la línea de comandos de IM...

Herramientas

Generador de Enlaces a Whatsapp