Ordenación de datos.

	Introducción.
	Método de la burbuja.
	Método de la burbuja mejorado.

 

Introducción.

Una de las tareas con las que nos podemos encontrar, muy habitualmente, en el momento de utilizar matrices o bases de datos es la ordenación o búsqueda de los datos que están almacenados en el interior. Para la ordenación o la búsqueda de datos existen diferentes métodos que nos pueden facilitar el trabajo. Estos métodos son más o menos complejos según lo rápido o lo eficaz que sean. Podemos encontrar métodos fáciles para la ordenación de pocos elementos y otros más complejos y su vez más eficaces para la ordenación de matrices con muchos elementos.

Antes de empezar a explicar métodos de ordenación vamos a decir que podemos ordenar los datos de dos formas diferentes: ascendente o descendentemente. Ascendente es la ordenación de menor a mayor y Descendente es la ordenación de mayor a menor.  

Método de la burbuja.

Es uno de los métodos más extendidos y más fáciles, pero a la vez es uno de los menos eficaces. Este método se basa en la ordenación por cambio de elementos, ya que se van comparando de dos en dos los elementos de la tabla. Si nosotros deseamos ordenar dicha tabla de menor a mayor (ascendente) al realizar la comparación entre dos elementos se produce el intercambio en el momento en el que el primer elemento es mayor que el segundo. De esta forma el elemento más grande pasa a estar en el último lugar de la tabla. El elemento sube por la tabla, al igual que una burbuja en un recipiente, de ahí proviene su nombre.

Los pasos a seguir utilizando este método son los siguientes, imaginando que deseamos realizar una ordenación creciente:

1.- Se compara el primer elemento con el segundo. Si están desordenados se intercambian. Luego se mira el segundo con el tercero, intercambiando también si es necesario. Así hasta que llegamos al último elemento. De esta forma tenemos en la última posición de nuestra tabla el elemento más grande.

2.- Repetimos lo mismo que antes pero ahora con todos los elemento, menos el último, que ya está ordenado.

3.- Repetimos el primer paso pero esta vez con otro elemento menos, ya que este también está ordenado. Este método finaliza en el momento en el que se han realizado tantas pasadas como objetos - 1 hay en la lista. Su hace menos 1 pasadas porque el primero de los objetos, como es lógico si pensamos que los demás ya están ordenados, ya está ordenado.

Vamos a ver el código que escribiríamos para utilizar este método:

1-	Indice = 1
2-	Repetir
3-	Mientras Indice2 <> TotalElem - 1 hacer
4-	Si Tabla(Indice2) > Tabla(Indice + 1) Entonces
5-	Intercambiar Tabla(Indice2), Tabla(Indice2 + 1)
6-	Fin Si
7-	Indice2 = Indice2 + 1
8-	Fin Mientras
9-	Hasta que Indice > TotalElem - 1

Vamos a comentar como funcionaría este código:

En la línea 1 iniciamos una variable llamada Indice a 1, ya que vamos a suponer que nuestra tabla empieza a contar en el 1, esta variable es la que nos controlará cuando se acaba nuestra ordenación. La ordenación finalizará cuando el valor de Indice sea mayor que el número total de elementos (aquí representado por TotalElem) menos 1, (Mirar línea 9). Ya que como hemos dicho antes suponemos que en la última pasada, solo existirá un elemento a mirar y por lo tanto ya estará ordenado.

En la línea 2 iniciamos un bucle Repetir... Hasta que que termina en la línea 9. Este bucle terminará en el momento en el que el Indice tenga como valor el total de elementos TotalElem menos 1. Ya que entonces terminará la ordenación.

En la línea 3 iniciamos otro bucle que está situado dentro del primero. Este se repetirá para ir comparando de dos en dos los diferentes elementos de la tabla. Se repetirá mientras Indice2 sea diferente del total de elementos menos 1 (TotalElem - 1). Hacemos que sea TotalElem - 1 porque así nos aseguramos que en ningún momento nos salgamos del índice de la tabla. Este bucle termina en la línea 8.

En la línea 4 miramos si el elemento que ocupa la posición Indice2 de la tabla, es más grande que el siguiente elemento (Indice + 1). Este Si termina en la línea 6, en un principio no sería necesario ya que solo tenemos una instrucción el Si, pero así facilitamos un poco el entendimiento de la estructura.

En la línea 5, utilizamos una nueva instrucción llamada Intercambiar. Esta instrucción lo que nos hace es cambiar los elementos que ocupan dos posiciones determinadas de la tabla. Estos elementos los separaremos entre sí mediante una coma (,). Esta línea se llevará a cabo en el momento que el primer elemento mirado sea más grande que el segundo.

En la línea 7 incrementamos el valor de Indice2, para continuar comparando elementos dentro de la tabla.

Esta sería la estructura básica de la ordenación de elementos de una tabla utilizando el método burbuja. Podemos ver que es un método un poco rudimentario y un poco largo en según que casos.

Imagina que tenemos una tabla de un total de 50 elementos y que desde un principio está ordenada, pero eso nosotros no lo sabemos, por lo que sometemos la tabla a una ordenación. Como te puedes imaginar el programa está empleando un tiempo que nos puede ser útil, para realizar cualquier otro cálculo dentro de la aplicación. Piensa que con una tabla de 50 elementos el programa pasará por el bucle principal 49 veces.

¿Como podemos arreglar esto?

Método de la burbuja mejorado.

Este método dentro de lo sencillo que es nos permite una mejora. Esta mejora consiste en terminar el bucle principal en el momento en el que detectemos que en una pasada, por todo lo largo de la tabla no ha habido ningún cambio. Al no haber ningún cambio, esto quiere decir que la tabla está completamente ordenada.

Vamos a ver esto haciendo las variaciones pertinentes en el código anterior.

Para comprobar que no se ha realizado ningún tipo de cambio necesitaremos insertar una variable de tipo booleana que solo permitirá dos valores, Verdadero o Falso.

1-	Indice = 1
2-	Repetir
3-	Ordenado = Verdadero
4-	Mientras Indice2 <> TotalElem - 1 hacer
5-	Si Tabla(Indice2) > Tabla(Indice + 1) Entonces
6-	Intercambiar Tabla(Indice2), Tabla(Indice2 + 1)
7-	Ordenado = Falso
8-	Fin Si
9-	Indice2 = Indice2 + 1
10-	Fin Mientras
11-	Hasta que Indice > TotalElem - 1 o Ordenado = Verdadero

Observa que en la línea 3 y 7 hemos introducido dos líneas nuevas. Hemos creado una nueva variable llamada Ordenado que solamente podrá tener dos valores: Verdadero o Falso. En el momento de entrar en el bucle principal, ponemos el valor de dicha variable a Verdadero, esto quiere decir que si en todas las comparaciones entre dos elementos no se realiza ningún tipo de cambio, ya hemos conseguido la ordenación de la tabla. Si existe algún cambio de elementos, cosa que quiere decir que la tabla no está ordenada cambiamos el valor de la variable a Falso.

¿Como detenemos la ejecución de nuestro bucle? Muy sencillo, utilizaremos la variable que hemos explicado anteriormente, para controlar si volvemos a entrar o no dentro del bucle. Observa la línea 11 y las modificaciones que hemos hecho. Nosotros repetiremos el bucle hasta que el índice sea más grande que el total de elementos menos uno o que la variable ordenado sea verdadera.

 

---