Eduardo Jimenez

13
UNIVERSIDAD METROPOLITANA, CIENCIA Y TECNOLOGÍA Licenciatura de sistemas y programación Magister: José Fung Integrantes: Edgardo Herrera Eduardo Jiménez

description

trabajo diapositivas grupo eduardo jimenz edgardo herrera

Transcript of Eduardo Jimenez

Universidad metropolitana, ciencia y tecnologa

Universidad metropolitana, ciencia y tecnologaLicenciatura de sistemas y programacin

Magister: Jos Fung

Integrantes: Edgardo HerreraEduardo JimnezORDENACION DE BURBUJAS Que es Ordenacin de burbujas?

Es un sencilloalgoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambindolos de posicin si estn en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten ms intercambios, lo cual significa que la lista est ordenada.ORDENACION DE BURBUJAS -DescripcinEl procedimiento de la burbuja es el siguiente: Ir comparando desde la casilla 0 nmero tras nmero hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevar hasta la ltima casilla, si no es as, ser reemplazado por uno mayor que l. Este procedimiento seguir as hasta que haya ordenado todas las casillas del vector. Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

ORDENACION DE BURBUJAS -Mtodo del Intercambio Directo Este algoritmoobtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeas "burbujas". Tambin es conocido como elmtodo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparacin, siendo el ms sencillo de implementar.ORDENACION DE BURBUJAS El procedimiento de la burbuja es el siguiente:Ir comparando desde la casilla 0 numero tras nmero hasta encontrar uno mayor, si este es realmente el mayor de todo el vector se llevar hasta la ltima casilla, si no es as, ser reemplazado por uno mayor que l.Este procedimiento seguir as hasta que halla ordenado todas las casillas del vector.Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

ORDENACION DE BURBUJAS -ComplejidadEl ordenamiento de burbuja tiene una complejidad igual que ordenamiento por seleccin. Cuando una lista ya est ordenada, a diferencia del ordenamiento por insercin, que pasar por la lista una vez y encontrar que no hay necesidad de intercambiar las posiciones de los elementos, el mtodo de ordenacin por burbuja est forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrtica en el mejor de los casos. Esto lo cataloga como elalgoritmo ms ineficienteque existe, aunque para muchos programadores sea el ms sencillo de implementar.ORDENACION DE BURBUJAS -AplicacinA pesar de que el ordenamiento de burbuja es uno de los algoritmos ms sencillos de implementar, su ordenlo hace muy ineficiente para usar en listas que tengan ms que un nmero reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden, otros procedimientos como el ordenamiento por insercin son considerados ms eficientes.

ORDENACION DE BURBUJAS -UtilizacionEl ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computacin. A pesar de esto, algunos investigadores como Owen Astrachan han criticado su popularidad en la enseanza de ciencias de la computacin, llegando a recomendar su eliminacin de los planes de estudio.ORDENACION DE BURBUJAS -Los algoritmos de ordenacin (ya sean de vectores o de otro tipo de estructura de datos) deben obtener una permutacin ordenada de los elementos presentes en la estructura.

-En La mayora de algoritmos de ordenacin de vectores se basan en realizar intercambios entre las componentes del mismo.

-Existen mltiples algoritmos de ordenacin de vectores diferencindose por su eficienciaORDENACION DE BURBUJAS -Mtodo Burbuja MejoradoEs un mtodo iterativo. Es utilizado para resolver problemas que pueden involucrar muchas variables Tambin se clasifica como un mtodo de ordenamiento interno ya que trabajan en memoria principal y sus implementaciones son muy variadas y en funcin de la memoria disponible. Integra una variable llamada "bandera", la cual detecta los intercambios que se realizaron. La ordenacin por burbuja o bubble sort se basa en comparar elementos contiguos del arreglo (vector) e intercambiar sus valores si no estn en orden. De este modo, los valores de mayor rango se hunden hacia la parte inferior del arreglo y los de menor rango burbujean hacia la parte superior del arreglo.ORDENACION DE BURBUJAS -Mtodo Burbuja Mejorado

Ventajas :Fcil de comprender y programar .Es eficaz.Consume menos recursos comparado con otros mtodos de ordenacin.

Desventajas:Requiere muchas comparacionesRequiere muchas lecturas/escrituras Es recursivo y su implementacin no recursiva es complicada.Es el menos eficiente de los mtodos de ordenamiento.

ORDENACION DE BURBUJAS Ordenacin de Burbujas-Ordenamiento por insercinMuchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, reemplazndolo por el ordenamiento por insercin. El ordenamiento de burbuja interacta vagamente con el hardware del los CPU modernos. Requiere al menos el doble de escrituras que el ordenamiento por insercin, el doble de prdidas de cache, y asintticamente ms prediccin de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que el ordenamiento de burbuja es 5 veces ms lento que el ordenamiento por insercin, y 40 % ms lento que el ordenamiento por seleccin.

Muchas Gracias