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:

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();
    }