Métodos de ordenamiento

UNIDAD III

• Algoritmos de ordenación y búsqueda.

OBJETIVOS ESPECÍFICOS

• Describir el funcionamiento de los algoritmos de ordenación: Burbuja, burbuja mejorada, inserción, selección, shell y Mezcla.

• Describir el funcionamiento de los algoritmos de búsqueda secuencial y búsqueda binaria.

• Comprender el concepto de complejidad algorítmica.

OBJETIVOS ESPECÍFICOS

• Determinar la complejidad de los algoritmos de ordenación: Burbuja, burbuja mejorada, inserción, selección, shell y mezcla.

• Determinar la complejidad de los algoritmos de búsqueda secuencial y binaria.

• Implementar programas de aplicación.

BIBLIOGRAFÍA RECOMENDADA

• Cairó Osvaldo & Guardati Silvia. Estructuras de Datos. 2001. Editorial Mc Graw Hill. Pp 319-384.

• Aguilar Joyanes. Programación en C++. 2000. Editorial Mc Graw Hill. Pp 247-262.

• Zimerman Heilleman. Estructuras de Datos. Editorial Mc Graw Hill. Pp 19-37.

BIBLIOGRAFÍA RECOMENDADA

• Centeno M. & Martínez J. Inteligencia Artificial. 2003. Tema 2.

• Dale & Nell. Estructuras de Datos. Mcgraw Hill. Pp 529-575.

CONTENIDO

• Introducción.• Ordenar. Concepto.• Clasificación de los métodos de ordenación.• Ordenación interna.• Métodos directos.

• Ordenación por burbuja.

CONTENIDO

• Ordenación burbuja mejorada.• Ordenación por selección.• Ordenación por inserción.• Métodos logarítmicos.• Búsqueda.• Búsqueda secuencial.

CONTENIDO

• Búsqueda Binaria.• Actividad 1.• Recomendaciones.• Errores más frecuentes.• Interrogantes.• Preguntas.

INTRODUCCIÓN

• Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia especifica. Los procesos de ordenación y búsqueda son muy frecuentes en nuestras vidas.

• La sociedad debe estar informada y por lo tanto buscar y recuperar información es ahora una necesidad.

INTRODUCCIÓN

• La operación de búsqueda para recuperar información normalmente se efectúa sobre elementos ordenados.

ORDENAR

• Significa permutar elementos de tal forma que los mismos queden de acuerdo con una distribución preestablecida (Ascendente o descendente).

CLASIFICACIÓN DE LOS MÉTODOS DE ORDENACIÓN

Ordenación interna (Arreglos)

Ordenación externa (Archivos)

ORDENACIÓN INTERNA

• Métodos directos (n2).• Métodos logarítmicos (n*logn).

MÉTODOS DIRECTOS

• Burbuja.• Burbuja mejorada.• Inserción.• Selección.

ORDENACIÓN POR BURBUJA

ORDENACIÓN POR BURBUJA

4 8 26

2 6 48

2 8 46

8 4 26

2 4 68

2 4 86

ORDENACIÓN BURBUJA MEJORADA

ORDENACIÓN BURBUJA MEJORADA

4 8 26

4 6 82

4 6 28

8 4 26

4 2 86

2 4 86

ORDENACIÓN POR INSERCIÓN

ORDENACIÓN POR INSERCIÓN

4 8 26

2 4 86

4 6 28

8 4 26

ORDENACIÓN POR SELECCIÓN

ORDENACIÓN POR SELECCIÓN

2 4 86

8 4 26

ORDENACIÓN POR SHELL

ORDENACIÓN POR SHELL

6 4 28

2 6 48

6 2 48

8 4 26

2 6 84

2 4 86

ORDENACIÓN POR MEZCLA

ORDENACIÓN POR MEZCLA

8 4 26

a b

4 8 62

c

4 8 62 2

4 8 62 2 4

4 8 62 2 4 6

4 8 62 2 4 86

i=0 j=0 k=0

i=0

i=1

j=1

j=1

k=1

k=2

i=1

i=2

j=2 k=3

j=2 k=4

BÚSQUEDA

• Es la operación que permite recuperar datos previamente almacenados. El resultado puede ser éxito, si se encuentra el elemento solicitado, o fracaso, en otro caso.

BÚSQUEDA

• Internas.• Externas.

BÚSQUEDAS INTERNAS

• Secuencial o lineal.• Binaria.

BÚSQUEDA SECUENCIAL

BÚSQUEDA BINARIA

ACTIVIDAD 1

• Realizar los ejercicios de la guía número dos (2).

RECOMENDACIONES

• Utilice como herramientas para determinar la eficiencia de un programa el análisis de algoritmo.

• Al trabajar en el diseño de un algoritmo es fundamental tener en cuenta dos factores críticos: Tiempo de procesamiento y Espacio de memoria ocupada.

ERRORES FRECUENTES DE PROGRAMACIÓN

• Utilizar el siguiente segmento de instrucciones para codificar el algoritmo de búsqueda secuencia:

for(int i=0; i<n; i++) if (A[i]==clave) return i; else return –1;

ERRORES FRECUENTES DE PROGRAMACIÓN

• Emplear el algoritmo de búsqueda binaria sin que el arreglo este ordenado.

• Emplear el método de ordenación por mezcla sin antes ordenar las dos mitades del arreglo.

• Deficiencias al trabajar con términos matemáticos como sumatoria

INTERROGANTES

• ¿Los métodos de ordenación analizados hasta ahora pueden ser empleando en otro tipo de estructuras como los arreglos de registro o arreglos de estructuras?

• ¿Cuál de los métodos de ordenación visto es el más eficiente y Cuál el más ineficiente?

• ¿Cuál de los métodos de búsqueda visto es el más eficiente y cuál el más ineficiente?

INTERROGANTES

• ¿Qué otros métodos de ordenación y búsqueda existen?