Burbuja

Método de la Burbuja

Integrantes: •Karla Isabel Magallanes Gonzalez •Martin Flores Valencia

Menu 1. 2. 3. 4. 5.

Introducción Origen Descripción Algoritmo Tiempos de ejecución 6. Implementación en C 7. Ventajas y Desventajas 8. Bibliografia

Introducción Método de los más conocidos y

más fáciles, pero a la vez es uno de los menos eficaces que se basa en la ordenación por intercambio de elementos.

Origen Se le denomina

ordenación por burbuja debido a que los valores mas grandes burbujean a la parte superior de modo similar como suben las burbujas en el agua.

Descripción Para una lista de n

elementos, requiere hasta n-1 pasadas. Donde una pasada representa el recorrido total de la lista.

Primera pasada

Descripción Por cada pasada

se comparan elementos adyacentes de la lista y se intercambian sus valores solo cuando el primer elemento es mayor que el

Se hace intercambio

Se hace intercambio

No se hace intercambio Se hace intercambio

Ejemplo

L={

, ,

, }

Pasada 1

L={ i

, ,

ij

, }j

Compara i > j

>

?

Pasada 2

L={ i

, ,

ij

, }j

Compara i > j

>

?

Comprobación

L={ i

, ,

ij

, }j

Compara i > j

>

?

Resultado

L={

, ,

, }

Algoritmo

Tiempos de ejecución Peor de los casos (O) En el i-ésimo paso de la ordenación burbuja se necesitan n-1 intercambios por cada n-1 comparaciones. Por tanto:

Mejor de los casos (Ω) En caso de que la lista ya este ordenada solo realiza n-1 comparaciones. Por tanto

Implementacion

Ventajas y Desventajas Ventajas Bastante sencillo y

Desventajas Es el método mas

mas utilizado por su ineficiente fácil comprensión y Consume bastante programación tiempo de Código reducido computadora Eficaz. Requiere de muchas lecturas/escrituras en memoria

Bibliografia:  Código  Algoritmos en C++

Sedgewick, Robert Ed. Pearson Education.  Definición  Algoritmos y estructura de datos. Una perspectiva en C

Luis Joyanes, Ignacio Zahonero Ed. Mc Graw Hill.

 Tiempos de ejecución  Analysis of Algorithms, An active learning approach

Jeffrey J. McConnell Jones and Bartlett Publishers