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?