martes, 13 de octubre de 2009

Metodo de la Burbuja

Cuando estamos trabajando con mucha información, es imposible encontrar lo que ando buscando si no está ordenado. Imagínate tu directorio telefónico si no estuviera ordenado alfabéticamente probablemente jamás lo usarías. Esto sucede con los sistemas informáticos también: no basta guardar todos los datos, hace falta mantenerlos en orden o poder ordenarlos.

Ahorita voy a explicar una manera de ordenar datos. Es el algoritmo menos eficiente, pero el más fácil de entender. Este algoritmo es el de Burbuja (o bubble sort) y lo voy a ilustrar usando arreglos. Una vez que entiendas como funciona con arreglos, no tendrás problemas en implementarlo con diferentes tipos de estructuras, clases, registros, etc. Voy a hacer el código usando Visual Basic 6.0 (que va a ser igual que el 2005) y en C. Con esto creo que no tienen problema en transportar el código a cualquier lenguaje de programación.

El algoritmo funciona de la siguiente manera: primero compara el primer elemento contra los demás (obviamente se va comparando uno por uno, elemento por elemento). Si se encuentra un elemento menor, intercambia el contenido (es decir, asigna a este elemento el valor menor y el valor que tenía lo deja en el elemento donde estaba el valor más pequeño). Una vez terminado de comparar el primer elemento contra todos los demás (se supone que el elemento menor está en la primera posición), hago lo mismo con el siguiente elemento: lo comparo con todos los que siguen y dejo el menor valor (de los que quedan) , y así sucesivamente voy comparando todos los elementos contra todos. Al final del día, debería tener un arreglo ordenado.

Por si te hice bolas, sé que una imagen vale mil palabras y como no pienso escribir mil palabras, mejor hice unos dibujitos para aclarar la situación. Espero que se entienda. Después de la imagen, hacemos el algoritmo en C y Visual Basic. Ahí va la manera en que ordeno el primer elemento...


Ok. Allí está el primer elemento. Ahora voy con el segundo elemento...


Ahora voy con el tercero...


Así me voy ordenando todos, pero para completar el ejercicio, ahí va la manera en que se ordena el cuarto elemento:


Y el quinto...

Y el sexto...

El séptimo y octavo...

Ya no tiene comparar el octavo con el noveno porque se supone que si todos los número están ordenados hasta el octavo elemento, el último debe ser el mayor a todos. El arreglo final, ordenadito y toda la cosa, es así:



¡Listo! Queda un arreglo ordenadito y toda la cosa. Este algoritmo es muy sencillo de entender, sin embargo, es muy ineficiente. La eficiencia de un algoritmo tiene que ver directamente con el número de comparaciones que tiene que hacer y este algoritmo es muy ineficiente porque hace muchísimas.

Ahora, ya entendido el concepto y la manera en que funciona este algoritmo, vamos a mostrar cómo se vería ya en código. Como el lenguaje C es muy simple, primero lo voy a resolver en este lenguaje. Aquí pongo el código y abajo de esta imagen explico que onda.


Le puse comentarios al código con la esperanza que se entienda mejor. De este código, lo interesante, lo que hace el trabajo, son los dos ciclos anidados. El ciclo de "i" se encarga de dejarnos visitar todos los elementos del arreglo y el ciclo "j" nos permite comparar todos los elementos que son mayores de i (o sea, los que faltan por comparar). Si el elemento en la posición j es menor al que está en la posición i, los intercambio (para esto uso una variable k que auxilia en la cambiadera).

Simplemente como comentario cultural, el código en C lo hice usando el compilador Microsoft Visual C++ 6.0, pero como usé el C estándar (ANSI C) debería funcionar con cualquier compilador (bueno, algunos comentarios están en "formato" C++, los que comienzan con dos diagonales invertidas, pero no creo que tengas broncas).

Al ejecutarlo se ve así:


Transportar esta idea a Visual Basic 6.0 es sencillo (y es aún más fácil usar el código de Visual Basic 6 en el 2005). Hice una pequeña aplicación, sencillita, que tiene 10 cajas de texto y dos botones. Un botón ordena los valores de las cajas de texto y el otro finaliza la ejecución del programa. El interfaz se ve así:


El código del programa es ésta:


En éste código, txtNumero es un arreglo de los TextBoxes que están en la pantalla. ¿Algún problema? Recuerda que si te quedaste con dudas, me puedes dejar un comentario e intentaré responderte en cuanto pueda.

Ahora voy a hacer esta misma aplicación en Visual Basic 2005. Es casi igual que en la versión 6, pero de todos modos les muestro la interfaz y luego el código. El gran problema que me trauma de la versión 2005 es que no es posible tener arreglos de controles. Bueno, sí se puede pero es un gran relajo al que prefiero no entrarle. Para saltarme esta bronca, antes de ordenar, copio los valores de las cajas de texto (txtNumero1 a txtNumero10) a un arreglo.


Y aquí les dejo el código de la ventana es ésta:


Fuente: http://tony-valderrama.blogspot.com

3 comentarios:

  1. Estan muy bien explicados. Me sirvieron bastante. Gracias.

    ResponderEliminar
  2. muy chevere tu explicacion elpero si alguien desea tambien tengo el metodo de ordenamiento en el siguiente blog que encontre al buscar informacion el codigo esta en java

    http://www.ciberinformatico-elsabio.blogspot.com/

    ResponderEliminar
  3. pue si me sirvio muchas grasias apesar de que estaba batallando much0 pz k te digo y grasias por tu explicacion

    ResponderEliminar