11
Unidad II Aplicaciones Unidad II Aplicaciones con Arreglos en Java y con Arreglos en Java y
C++C++M.C. Juan Carlos Olivares
Rojas
AgendaAgenda
• 2.2 Métodos Básicos de Ordenamiento en un Arreglo: Burbuja, Inserción y Selección
22
OrdenamientoOrdenamiento
• Una de las partes más interesantes en los arreglos después de las búsquedas son los ordenamientos.
• Si se tiene un arreglo ordenado las búsquedas se simplifican, el problema es ordenar el arreglo.
33
OrdenamientoOrdenamiento
• Existen varios métodos de ordenamiento, cada uno con sus respectivas ventajas y desventajas.
• Los métodos tratados son 3: Burbuja, Selección e Inserción, pero existen una gran variedad de algoritmos de ordenamiento: Shell, Heap, Tournament, Quicksort, Mergesort, Radixsort, …
44
Ordenamiento por BurbujaOrdenamiento por Burbuja• El Bubblesort es quizás el algoritmo más
simple de ordenamiento. Basa su filosofía en cada iteración colocar el elemento más grande o más pequeño (dependiendo del criterio de selección) en la primera posición de tiempo.
• La complejidad del algoritmo es O(n2) en el peor de los casos y de O(n) en el caso promedio.
55
Ordenamiento por BurbujaOrdenamiento por Burbuja
• La complejidad de un algoritmo determina que tan rápido es el algoritmo. Se expresa generalmente con una función matemática que permite comprender como trabaja un algoritmo.
• La complejidad está medida en tres situaciones: mejor de los casos, caso promedio y en el peor de los casos.
66
Ordenamiento por InserciónOrdenamiento por Inserción
• Este algoritmo tiene su fundamento en como trabajamos los humanos para ordenar las cosas: nos basamos en cosas ya ordenadas y simplemente las colocamos en su nuevo orden.
• Es parecido cuando ordenamos una carta en un juego de Pocker.
77
Ordenamiento por InserciónOrdenamiento por Inserción
• Su complejidad también es de O(n2) en el caso promedio.
• Asume a que el algoritmo ya está ordenado, por lo que es útil cuando se agrega un nuevo elemento. ¿Qué se hace cuando se está desordenado?
88
Ordenamiento por SelecciónOrdenamiento por Selección
• Tiene una complejidad de O(n2).
• Consiste en encontrar el valor máximo o mínimo del arreglo e intercambiarlo en la primera posición, después se realiza el mismo proceso para los n-1 elementos faltantes… se repite el procedimiento hasta terminar con los elementos del arreglo.
99
Comparativa de Algoritmos de Comparativa de Algoritmos de OrdenamientoOrdenamiento
1010
SelecciónInserción
Burbuja
Actividad 8Actividad 8
• Carrera de Métodos de Ordenamiento:
• En equipos de tres personas se programarán los tres métodos básicos de ordenamiento (burbuja, inserción y selección). Puntos extras a los algoritmos más rápidos y a los que utilicen otros algoritmos más avanzados. 1111
1212
¿Preguntas, dudas y ¿Preguntas, dudas y comentarios?comentarios?
Top Related