MÉTODO BURBUJA.
El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en posición hasta ponerlo en su lugar.
Procedimiento Bubble Sort
paso 1: [Inicializa i al final de arreglo] For i <- N down to 1 do
paso 2: [Inicia desde la segunda pos.] For j <- 2 to i do
paso 4: [Si a[j-1] es mayor que el que le sigue] If a[j-1] < a[j] then
paso 5: [Los intercambia] Swap(a, j-1, j).
paso 7: [Fin] End.
Tiempo de ejecución del algoritmo burbuja:
Para el mejor caso (un paso) O(n)
Peor caso n(n-1)/2
Promedio O(n2)
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. 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.
3 – METODO DE LA BURBUJA
El metodo de la burbuja es uno de los mas simples, es tan facil como comparar todos
los elementos de una lista contra todos, si se cumple que uno es mayor o menor a
otro, entonces los intercambia de posición.
Por ejemeplo, imaginemos que tenemos los siguientes valores:
5 6 1 0 3
Lo que haria una burbuja simple, seria comenzar recorriendo los valores de izq. a
derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3, si
es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se
intercambian de posicion. Luego continua con el siguiente, con el 6, y lo compara con
todos los elementos de la lista, esperando ver si se cumple o no la misma condicion
que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.3. 1 – BURBUJA SIMPLE
Como lo describimos en el item anterior, la burbuja mas simple de todas es la que
compara todos con todos, generando comparaciones extras, por ejemplo, no tiene
sentido que se compare con sigo mismo o que se compare con los valores anteriores a
el, ya que supuestamente, ya estan ordenados.
for (i=1; i<LIMITE; i++)
for j=0 ; j<LIMITE - 1; j++)
if (vector[j] > vector[j+1])
temp = vector[j];
vector[j] = vector[j+1];
vector[j+1] = temp;3. 2- BURBUJA MEJORADA
Una nueva version del metodo de la burbuja seria limitando el numero de
comparaciones, dijimos que era inutil que se compare consigo misma. Si tenemos una
El algoritmo de la burbuja (BubbleSort)
El algoritmo de ordenación por el método de la burbuja, también conocido como intercambio directo, es uno de los más simples que se conocen.
Se basa en una serie de intercambios entre elementos adyacentes. Esos intercambios dan la impresíón de que cada elemento va ascendiendo a través del array acercándose cada vez más a su posición final, recordando a cómo ascienden las burbujas de gas en un líquido.
A efectos prácticos, el algoritmo de la burbuja no es adecuado prácticamente para ninguna situación, ya que realiza muchas comparaciones y muchos intercambios. Los hay similares que se comportan bastante mejor. Su interés es más bien teórico, ya que sirve para establecer comparativas con otros métodos y extraer conclusiones teóricas.
No obstante, es un algoritmo sencillo y vistoso que se sigue viendo en casi cualquier curso o asignatura de programación. Muchos profesores prefieren no perder tiempo con este algoritmo en las clases de programación... bueno... quizá sea una decisión acertada. Sin embargo, es uno de los imprescindibles en algoritmia... así que vamos a echarle un vistazo.
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Es un algoritmo estable de ordenación interna, y su complejidad temporal en el peor caso es de O(n2), mientras que en el mejor caso -que el array ya esté totalmente ordenado- puede llegar a Ω(n) siendo n el tamaño del array a ordenar. En cuanto a la complejidad espacial, es muy ahorrativo: tan solo necesita una variable temporal para realizar los intercambios, así que su gasto de memoria es constante, sea cual sea el tamaño del array.
El algoritmo consiste en realizar varias pasadas sobre el array, logrando que en cada pasada el elemento de mayor valor se coloque al final del array. Para lograrlo, en cada pasada es necesario recorrer el array realizando comparaciones e intercambios. Por eso, se suele implementar con dos bucles, uno anidado dentro del otro. El bucle exterior realiza las pasadas y el interior recorre el array realizando comparaciones e intercambios.
Vamos a intentar ver informalemente el funcionamiento del algoritmo. Supondremos que el array tiene n elementos.
Realizaremos n-1 pasadas. En cada una de ellas lograremos que el elemento de mayor valor se sitúe al final. El motivo de realizar n-1 pasadas y no n es que si en cada pasada logramos ordenar un elemento, cuando tengamos en orden los n-1 del final del array el elemento que queda es necesariamente el más pequeño de todos.
En cada pasada recorreremos el array empezando por el principio hasta un cierto punto, comparando cada elemento con el siguiente, y si un elemento y el siguiente no están en orden, los intercambiamos de posición, logrando que el mayor de ellos vaya ascendiendo por el array.
En la primera pasada, compararemos cada uno de los n-1 primeros elementos con el siguiente, y lograremos que en la última posición se coloque el mayor de ellos.
En la segunda pasada, compararemos cada uno de los n-2 primeros elementos con el siguiente. No llegaremos a hacer ninguna comparación que implique al último elemento del array, porque sabemos que ese ya lo colocó en orden la primera pasada. Al término de la segunda pasada quedará también en orden el penúltimo elemento del array.
En la tercera pasada haremos lo mismo con los n-3 primeros elementos, logrando colocar el antepenúltimo elemento... y así sucesivamente, hasta que tengamos colocados los n-1 últimos elementos. Cuando estemos en esa situación, el primer elemento también estará en orden, ya que será el más pequeño de todos.
Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo de la burbuja: 45, 52, 21, 37, 49, así pues, n=5
1ª pasada: comparamos cada uno de los cuatro primeros (n-1) con los que le siguen. Si un elemento no está en orden con respecto al siguiente, los intercambiamos de sitio y seguimos. El elemento de mayor valor (52) irá "ascendiendo" hasta la última posición.
45, 52, 21, 37, 49 → Comparar 45 y 52. (1º y 2º) Están en orden. Seguimos.
45, 52, 21, 37, 49 → Comparar 52 y 21. (2º y 3º) No están en orden. Intercambio.
45, 21, 52, 37, 49 → seguimos
45, 21, 52, 37, 49 → Comparar 52 y 37 (3º y 4º). No están en orden. Intercambio.
45, 21, 37, 52, 49 → seguimos
45, 21, 37, 52, 49 → Comparar 52 y 49. (4º y 5º). No están en orden. Intercambio.
45, 21, 37, 49, 52 → Ya hemos terminado esta pasada.
45, 21, 37, 49, 52 → El 5º elemento ya está en su sitio.
2ª pasada: comparamos cada uno de los tres primeros (n-2) con los que le siguen. No llegamos a hacer comparaciones que involucren al 5º elemento, porque la primera pasada hizo que el mayor de todos los elementos ocupara la última posición, con lo cual, sabemos que ese ya está en su sitio. Trabajaremos sólo con los cuatro que quedan.
45, 21, 37, 49, 52 → Comparar 1º y 2º. No están en orden. Intercambio.
21, 45, 37, 49, 52 → seguimos
21, 45, 37, 49, 52 → Comparar 2º y 3º. No están en orden. Intercambio.
21, 37, 45, 49, 52 → seguimos
21, 37, 45, 49, 52 → Comparar 3º y 4º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → El 4º elemento ya está en su sitio. (Fíjate en que el array ya está en orden, pero algoritmicamente, eso no lo sabemos).
3ª pasada: Comparamos cada uno de los dos primeros (n-3) con los siguientes.
21, 37, 45, 49, 52 → 1º y 2º. Están en orden. Seguimos.
21, 37, 45, 49, 52 → 2º y 3º. Están en orden. Pasada terminada.
21, 37, 45, 49, 52 → Ya tenemos tres en orden.
4ª y última pasada: Comparamos el primero con el segundo.
Por supuesto, es necesario adaptarlo a las necesidades concretas. Por ejemplo, en C/C++/C#/Java, etc... los índices de los arrays empiezan en 0 y terminan en n-1. El array a ordenar no tiene por qué ser de enteros, puede ser de cualquier cosa ordenable, pero entonces, análogamente, la operación de comparación (">" debe ser sustituida por la operación que nos compare nuestros elementos por el criterio que nosotros queramos.
Lo importante de un algoritmo no es que lo memorices ni que lo intentes traducir literalmente a un lenguaje de programación concreto.
Lo importante es que lo entiendas y seas capaz de implementarlo adaptándolo a cualquier lenguaje sin traducirlo literalmente.
En el algoritmo de la página anterior hay un importante reto que a veces es dificil de superar: los índices. En el pseudocódigo se asume que el array de n elementos se indiza desde 1 hasta n. Es decir, el primer elemento es el número 1 y el último es el número n.
En algunos lenguajes de programación (como Pascal o Delphi, por ejemplo) es posible utilizar arrays que empiecen por un índice 1, como en el pseudocódigo. Sin embargo, en muchos otros (como C/C++/C# o Java) los arrays siempre empiezan por el índice 0. Es decir los elementos de un array de n elementos se indizan con índices que empiezan en 0 y terminan en n-1.
Esto no supone mayor problema que dedicar un rato a pensar cómo ajustar los índices para que el algoritmo siga haciendo lo que debe
el contenido de los bucles, cuando se accede a los elementos (restando 1 también). Personalmente, siempre me ha parecido más fácil la segunda opción.