Colabora
 

Ordenamiento de Vectores

Algoritmo de la Burbuja

 

Fecha: 05/Nov/2008 (30-10-08)
Autor: Wagner, Ariel Alejandro - ([email protected])

 


Introducción

En este artículo veremos una técnica de ordenamientos de datos que se encuentran almacenados dentro de un Vector o una Matriz unidimensional. La técnica que explayo en este artículo se basa en el tradicional algoritmo de la Burbuja.

La Burbuja

El algoritmo ha sido llamado de esta forma puesto que el proceso que se realiza durante las fases de ejecución del programa, simula un burbujeo de los datos en el vector. Análogamente y casi de una forma imaginativa, se trata de como si estuviéramos observando las burbujas ascender en el envase de una gaseosa. A igual que esta analogía algo fantasiosa, los datos contenidos dentro del vector, se van desplazando de un índice a otro hasta lograr que los mismos se encuentren ordenados.

Ahora bien, el orden podrá darse en forma ascendente o descendente. Este criterio de orden dependerá de algunos enfoques en la sección del algoritmo, más precisamente, en la sección de comparación y reubicación de los datos a lo largo del vector.

El Código:

Analizando el código, será importante separar por partes el algoritmo para facilitar mejor la comprensión del mismo. En consecuencia, pasaré a detallar las partes del mismo. Para ello, empezaremos observando la creación del vector mediante la orden Dim Bub(9) As Integer que nos permitirá crear un vector unidimensional de 10 elementos.

Nota:
Recuerde que la cantidad de los elementos en el vector es 10 y no 9. El vector se inicia con el valor 0 y su último elemento resulta ser el número 9. Si suma la cantidad de elementos resultan en 10 en totales. Por favor, no confunda cantidad de elementos dentro de un vector con el número de índice. Ambos son conceptos totalmente distintos. El índice le permite desplazarse por el vector de un extremo a otro o paso a paso y, por el otro lado, los elementos del vector, le permiten manipular los datos almacenados en el mismo.

En el algoritmo de nuestro código, existen dos funciones llamadas LBound y UBound. Estas se las utiliza para obtener los límites mínimos y máximos de los índices del vector. Es decir, mediante la función LBound obtendremos el valor del índice extremo mínimo que resulta ser el número 0. Por otro lado, la función UBound, que nos permitirá obtener el valor extremo máximo del índice del vector, que en este caso, se trata del número 9. Ambas funciones son utilizadas para determinar los límites extremos del vector.

Ahora bien, los valores extremos obtenidos a través de las funciones LBound y UBound, son asignados a dos variables. Dichas variables son utilizadas inicialmente para ser comparadas en el bucle While principal, luego dentro de este bucle, en el bucle For para ejercer el proceso de desplazamiento, comparación y enroque. Las variables MaxBub y MinBub irán actualizándose a medida que los bucles While y For se ejecuten permanentemente hasta que la variable MinBub alcance un valor mayor o igual a MaxBub, lo cual, detendrá el proceso de ejecución del bucle While. En consecuencia, si se llega a esta instancia, se supone que los valores en los elementos del vector deberán encontrase ordenados.

La sección más importante de este algoritmo se centra dentro del bucle For. A medida que el bucle For avance de uno en uno, la variable i, podrá desplazarse por sobre los índices del vector. Notará que un índice se ha escrito como i + 1. Cuando el valor i es igual a uno, en el caso de i + 1 será igual a dos. De esta forma, con i se accede al elemento 1 y con i + 1 se accede al elemento dos. A medida que i vaya avanzando, los índices se actualizarán y así sucesivamente hasta llegar al índice extremo superior MaxBub - 1, es decir, cuando se llegue en este caso al tope cuyo valor es el número 8.

Dentro de la estructura de comparación If del bucle For, existe un proceso de enroque de valores en el vector durante la recorrida de datos. La estructura de decisión If nos permitirá ejercer el enroque, siempre y cuando, el valor hallado en un elemento de la matriz sea mayor que el elemento de índice siguiente. De ser mayor entonces, se procede hacer el enroque entre los valores, caso contrario, se ignora por completo este proceso y se continua con el ciclo del bucle.

Habrá notado que existe una variable que se llama sutilmente Acum. Esta variable se la utiliza para retener la información temporalmente durante el proceso de enroque de datos en el vector. De no contar con esta variable Acum, resultaría imposible garantizar el enroque de los valores dentro de los elementos del vector. Es decir, se correría el riesgo de sobreescribir los valores en el vector, lo cual esto termina lisa y llanamente en un desastre. La variable Pos, actualiza el índice de posición actual, lo cual optimiza al algoritmo y reduce el número de ciclos en el bucle. Con el número de posición, se actualiza la variable MaxBub. De esta forma, los bucles While y For renuevan sus variables de control para optimizar el ciclo del control de los bucles de los mismos.

' *********************************
'   Método de La Burbuja
'   Algoritmo de análisis...
' *********************************
Dim Bub(9) As Integer
MinBub = LBound(Bub)
MaxBub = UBound(Bub)
' Determinar el estado del vetor...
While MaxBub > MinBub
Pos = MinBub
For i = MinBub To MaxBub - 1 ' Comparación de los valores en el vector... ' Si usa > ordena Ascendentemente ' Si usa < ordena Descendentemente
If Bub(i) > Bub(i + 1) Then
' Proceso de enroque de datos de variables...
Acum = Bub(i + 1)
Bub(i + 1) = Bub(i)
Bub(i) = Acum
Pos = i
End If
Next i
MaxBub = Pos
Wend

Tipo de Orden - Ascendente o Descendente

Resulta importante señalar que, según el signo mayor o menor que utilicemos entre las variables Bub(i) y Bub(i + 1), podremos producir un orden o, bien, ascendente o, bien, descendente. Lo que se produce en síntesis dentro de estos cambios es el sentido inverso de organización. Pese a esta diferencia, la metodología mecánica funcional del algoritmo no cambia en absoluto, aunque claro está, simplemente en el factor de ordenado final es el que cambia realmente. Debajo de este comentario, dejo el algoritmo de estudio para que lo analicen. Además, dejaré aquí un archivo conteniendo un proyecto de prueba para que puedas ver cómo funciona.


 



Compromiso del autor del artículo con el sitio del Guille:

Lo comentado en este artículo está probado (y funciona) con la siguiente configuración:

El autor se compromete personalmente de que lo expuesto en este artículo es cierto y lo ha comprobado usando la configuración indicada anteriormente.

En cualquier caso, el Guille no se responsabiliza del contenido de este artículo.

Si encuentras alguna errata o fallo en algún link (enlace), por favor comunícalo usando este link:

Gracias.


Código de ejemplo (comprimido):

 

No hay código extra al mostrado en el artículo.

 


Ir al índice principal de el Guille