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(); }
Ejecutando el programa tenemos
Descargar proyecto: Bubble Sort
Common Object Request Broker Architecture (CORBA) es un estándar que permite que diversos componentes de software escrit[...]
En este post veremos como crear una aplicación de ayuda al usuario similar al extinto javahelp. Pero en esta oportunidad[...]
¿Qué es una transición? Una transición es un efecto de movimiento que se da entre una imagen y la siguiente en una prese[...]
Melody.ml es un aplicación online que usa la I.A (Inteligencia Artificial) para procesar archivos MP3 y separar en pist[...]
La clase de java DatabaseMetaData nos permite obtener información exhaustiva sobre una base de datos, para ser más exact[...]
En esta oportunidad dejo a considerancion un codigo realizado en Java/Netbeans para recortar una imagen visualmente Vide[...]
