Metodo Burbuja

METODO DE ORDENACION BURBUJA
Definición:
El método de Ordenación de burbuja (Bubble Sort) es el mas sencillo algoritmo de
ordenamiento a comparación de otros. Su funcionamiento consta en ir revisando cada
elemento del arrays que va a ser ordenado con el siguiente, si es que encuentra que
posición no es la correcta los intercambia. Este algoritmo posee ese nombre por su
forma en 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 de intercambio directo.
Puesto que solo usa comparaciones para operar elementos, se le considera un algoritmo
de comparación siendo el más sencillo de implementar.
Algoritmo de la burbuja:
Fuera el caso de un array con n elementos, entonces la ordenación requiere como hasta
n-1 iteraciones. Por cada iteración se comparan los elementos adyacentes y se
intercambian sus valores cuando se cumpla que el primer elemento es mayor que el
segundo elemento. Cuando la iteración 0 esa completa el array A[n-1] esta ordenada y
el frente de la lista permanece desordenada.
Las etapas del algoritmo son:
 En la primera iteración se comparan los elementos adyacentes:

(S[0], S[1]), (S[1], S[2]), (S[2], S[3]), ...(S[n-2], S[n-1])
Se realizan n-1 iteraciones, por cada pareja (S[i], S[i+1]) se intercambian
los valores dependiendo cual sea mayor S[i+1] < S[i] y al concluirse la pasada,
el mayor elemento del array está situado en S[n-1].
 En la siguiente iteración se realizan las mismas comparaciones e intercambios,
terminándose con el segundo mayor elemento en S[n-2].
 El proceso se concluye con la pasada n-1, en el cual el elemento más pequeño
termina almacenándose en S[0].
Análisis del algoritmo.

Este análisis hace referencia al modelo simple del método burbuja:
 Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por
lo tanto, es estable.
 Requerimientos de Memoria: Este algoritmo sólo requiere de una variable
adicional para realizar los intercambios.
 Tiempo de Ejecución: El ciclo interno se ejecuta n veces para una lista de n
elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad
es n * n = S(n2). El comportamiento del caso promedio depende del orden de
entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue
siendo S(n2).
Ventajas:
Fácil implementación.
No requiere memoria adicional.
Desventajas:
Muy lento.
Realiza numerosas comparaciones.
Realiza numerosos intercambios.
Este algoritmo es uno de los más pobres en rendimiento. Si miras la demostración te

darás cuenta de ello. No es recomendable usarlo. Tan sólo está aquí para que lo
conozcas, y porque su sencillez lo hace bueno para empezar. Ya veremos otros mucho
mejores.
Ahora un ejemplo manual:

Para poder entender el como se da el procedimiento del algoritmo burbuja:
Se tiene el siguiente arreglo 𝑆 = { 18, 13, 9, 10, 6, 2 }
Primera iteración:
18 13 9 10 6 2 18 es mayor a 13 SI (Hay intercambio)

13 9 10 6 2 18
Resultado de la primera Iteración.
Segunda iteración:
9 10 6 2 13 18 13 es mayor a 18 NO (No hay intercambio)

9 10 6 2 13 18 Resultado de la segunda iteración.
Tercera iteración:
9 6 2 10 13 18 Resultado de la tercera Iteración.
Cuarta iteración:

6 2 9 10 13 18 Resultado de la cuarta Iteración.
Quinta iteración:

2 6 9 10 13 18 Resultado de la quinta Iteración.
BURBUJA (SEGUNDO METODO)

Se observa que en el primer recorrido del vector (cuando i = 1) el mayor valor se mueve
al último elemento x[n]. Por consiguiente, en el siguiente paso no es necesario comparar
x [n – 1] y x[n]. En otras palabras, el límite superior del bucle desde puede ser el
elemento del vector de índice n – 2
BURBUJA (TERCER METODO):

Como se puede observar el algoritmo del método burbuja hace demasiadas iteraciones
que no son necesarias, sin embargo, existen variaciones en el método que logran
mejorarlo.
El proceso de ordenación puede terminar en la pasada n-1, o bien antes, si en una

iteración en el algoritmo ya no se produce cambio alguno quiere decir que el array ya se
encuentra ordenado, entonces seguir comparando valores viene a ser una perdida de
tiempo puesto no son necesarios.
En el siguiente ejemplo se puede mostrar como el introducir un variable interruptor
para detectar si se ha producido intercambio en la pasada.
Se tiene el siguiente arreglo 𝑆 = { 15, 12, 14, 18, 13 }
Primera iteración:
15 12 14 18 13 15 es mayor a 12 SI (Hay intercambio)
12 14 15 18 13 15 es mayor a 18 NO (Ordenados)
15 12 14 13 18 Elemento mayor es 18 / interruptor = TRUE
Segunda Iteración.

12 14 13 15 18 15 y 18 elementos mayores y ordenados

interruptor = TRUE
Tercera Iteración: Solo se hacen dos comparaciones

Interruptor = TRUE
Cuarta Iteración: Se hace una única comparación de 12 y 13, y no se produce

intercambio
12 13 14 15 18 Arreglo ordenado / interruptor = TRUE
En consecuencia:
El algoritmo de ordenación de burbuja mejorado contempla dos bucles anidados: el
bucle externo controla la cantidad de pasadas (al principio de la primera pasada todavía
no se ha producido ningún intercambio, por tanto, la variable interruptora se pone a
valor falso (0); el bucle interno controla cada pasada individualmente y cuando se
produce un intercambio, cambia el valor de interruptor a verdadero (1). El algoritmo
terminará, bien cuando se termine la última pasada (n − 1) o bien cuando el valor del
interruptor sea falso (0), es decir, no se haya hecho ningún intercambio. La condición
para realizar una nueva pasada se define en la expresión lógica.
(𝒑𝒂𝒔𝒂𝒅𝒂 < 𝒏 − 𝟏) && 𝒊𝒏𝒕𝒆𝒓𝒓𝒖𝒑𝒕𝒐𝒓
Ejemplo en C++, generar por BURBUJA S={ 18,13,9,10,6,2} (podemos observar

que se puede ordenar de forma ascendente y forma descendente)
JOYANES AGUILAR, L. (2008). FUNDAMENTOS DE PROGRAMACIÓN: ALGORITMOS, ESTRUCTURA DE DATOS Y
OBJETOS (4A. ED. --.). MADRID: MCGRAW-HILL.
JOYANES AGUILAR, L., & ZAHONERO MARTÍNEZ, I. (2010). PROGRAMACIÓN EN C, C++, JAVA Y UML (1A. ED. --
.). MÉXICO D.F.: MCGRAW-HILL.

Metodo Burbuja

Cargado por

Copyright:

Formatos disponibles

Metodo Burbuja

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Metodo Burbuja

Cargado por

Copyright:

Formatos disponibles

METODO DE ORDENACION BURBUJA

Las etapas del algoritmo son:

 En la primera iteración se comparan los elementos adyacentes:

Análisis del algoritmo.

No requiere memoria adicional.

Realiza numerosas comparaciones.

Realiza numerosos intercambios.

Este algoritmo es uno de los más pobres en rendimiento. Si miras la demostración te

Ahora un ejemplo manual:

18 13 9 10 6 2 18 es mayor a 13 SI (Hay intercambio)

13 18 9 10 6 2 18 es mayor a 9 SI (Hay intercambio)

13 9 10 18 6 2 18 es mayor a 6 SI (Hay intercambio)

13 9 10 6 18 2 18 es mayor a 2 SI (Hay intercambio)

13 9 10 6 2 18 13 es mayor a 9 SI (Hay intercambio)

9 13 10 6 2 18 13 es mayor a 10 SI (Hay intercambio)

9 10 13 6 2 18 13 es mayor a 6 SI (Hay intercambio)

9 10 6 13 2 18 13 es mayor a 2 SI (Hay intercambio)

9 10 6 2 13 18 13 es mayor a 18 NO (No hay intercambio)

9 10 6 2 13 18 9 es mayor a 10 NO (No hay intercambio)

9 10 6 2 13 18 10 es mayor a 6 SI (Hay intercambio)

9 6 10 2 13 18 10 es mayor a 2 SI (Hay intercambio)

9 6 2 10 13 18 10 es mayor a 13 NO (No hay intercambio)

9 6 2 10 13 18 13 es mayor a 18 NO (No hay intercambio)

9 6 2 10 13 18 Resultado de la tercera Iteración.

9 6 2 10 13 18 9 es mayor a 6 SI (Hay intercambio)

6 2 9 10 13 18 9 es mayor a 13 NO (No hay intercambio)

6 2 9 10 13 18 10 es mayor a 13 NO (No hay intercambio)

6 2 9 10 13 18 13 es mayor a 18 NO (No hay intercambio)

6 2 9 10 13 18 Resultado de la cuarta Iteración.

6 2 9 10 13 18 6 es mayor a 2 SI (Hay intercambio)

2 6 9 10 13 18 6 es mayor a 9 NO (No hay intercambio)

2 6 9 10 13 18 9 es mayor a 10 NO (No hay intercambio)

2 6 9 10 13 18 10 es mayor a 13 NO (No hay intercambio)

2 6 9 10 13 18 Resultado de la quinta Iteración.

BURBUJA (SEGUNDO METODO)

BURBUJA (TERCER METODO):

El proceso de ordenación puede terminar en la pasada n-1, o bien antes, si en una

Se tiene el siguiente arreglo 𝑆 = { 15, 12, 14, 18, 13 }

15 12 14 18 13 15 es mayor a 12 SI (Hay intercambio)

12 15 14 18 13 15 es mayor a 14 SI (Hay intercambio)

12 14 15 18 13 18 es mayor a 13 SI (Hay intercambio)

15 12 14 13 18 Elemento mayor es 18 / interruptor = TRUE

12 14 15 13 18 12 es mayor a 14 SI (Hay intercambio)

12 14 15 13 18 14 es mayor a 15 SI (Hay intercambio)

12 14 13 15 18 15 y 18 elementos mayores y ordenados

12 13 14 15 18 14 es mayor a 13 SI (Hay intercambio)

Cuarta Iteración: Se hace una única comparación de 12 y 13, y no se produce

12 13 14 15 18 Arreglo ordenado / interruptor = TRUE

(𝒑𝒂𝒔𝒂𝒅𝒂 < 𝒏 − 𝟏) && 𝒊𝒏𝒕𝒆𝒓𝒓𝒖𝒑𝒕𝒐𝒓

Ejemplo en C++, generar por BURBUJA S={ 18,13,9,10,6,2} (podemos observar

También podría gustarte