Separata Unidad 3 AED - MÉTODOS DE ORDENAMIENTO Y BÚSQUEDA, ARREGLOS MULTIDIMENSIONALES, CON CASOS Y PDF

Preview

Summary

MÉTODOS DE ORDENAMIENTO Y BÚSQUEDA, ARREGLOS MULTIDIMENSIONALES, CON CASOS Y EJERCICIOS PROPUESTOS, CON SOLUCIONES, ETC....

Description

Universidad Nacional del Callao

Separata preparada para el desarrollo del curso de:

Algoritmos y Estr Estructur uctur uctura a de Da Datos tos

Tercera Unidad Temática: Métodos de Ordenamiento y Búsqueda

Semestre: 2015-II

Pág. 1

Universidad Nacional del Callao

Pág. 2

INDICE TERCERA UNIDAD TEMATICA MÉTODOS DE ORDENAMIENTO

NOVENA SEMANA MARCO TEORICO MÉTODOS DE ORDENAMIENTO II Método de ordenamiento por selección………………………………………….. 2 Método de ordenamiento Shell………………………………………..………….. 2 Método de ordenamiento Ordenación Rápida (Quick Sort).………..…………… 2 MARCO PRÁCTICO Actividades…………………………………………………….……………………….

DÉCIMA SEMANA MARCO TEORICO MÉTODOS DE BÚSQUEDA Método Secuencial……...…....………………………………..….……………….…17 Método Binario…………………...……………………………..….……………….…17 MARCO PRÁCTICO Actividades……………………………………………………………………………

DÉCIMA PRIMERA SEMANA Semana de Exámenes Parciales (con suspensión de clases)

DÉCIMA SEGUNDA SEMANA MARCO TEORICO OPERACIONES CON ARREGLOS MULTIDIMENSIONALES Cargar una matriz bidimensional…..………………………..….………………….…17 Sumar dos matrices cuadradas……………………………..….……………….… 17 Sumar diagonales……………………………………………..….……………….… 17 MARCO PRÁCTICO Actividades……………………………………………………………………………

Universidad Nacional del Callao

Pág. 3

NOVENA SEMANA – Marco Teórico Logro Que el alumno comprenda y aplique los diferentes metodos de ordenamiento que existen. Resumen Durante esta semana aprenderemos en qué consisten los métodos de ordenamiento por selección, método Shell y el método de ordenamiento por QuickSort.

Métodos de Ordenamiento II MÉTODO DE ORDENAMIENTO POR SELECCIÓN El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere n2 operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente:  Buscar el mínimo elemento de la lísta  Intercambiarlo con el primero  Luego, buscar el mínimo en el resto de la lista  Intercambiarlo con el segundo y así sucesivamente. Y en general:  Buscar el mínimo elemento entre una posición i y el final de la lista  Intercambiar el mínimo con el elemento de la posición i Ventajas: Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros, esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menos operaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo.

Universidad Nacional del Callao

Pág. 4

Desventajas:  Lento.  Realiza numerosas comparaciones. Este es un algoritmo lento. No obstante, ya que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas.

Caso Práctico: Realizar una aplicación Java que utilice POO, Estructura de Datos Estáticas (Arreglos) que aplique el método de ordenamiento por selección. Lógica de Presentación Para desarrollar este caso utilizaremos el formulario frmOrdenamiento, cuyo diseño se presenta en el siguiente gráfico.

Método Seleccion (Agregarlo en la clase Arreglos) Tipo de dato que retorna como respuesta: String Argumentos que recibe: longitud del arreglo.

Universidad Nacional del Callao

Pág. 5

public String Seleccion(int n) { int k, i, j; double aux; for (i = 0; i v) { ventas[j + k] = ventas[j]; j -= k; } ventas[j + k] = v; } } k = k / 2; } return mostrarTodoslosDatos(n); }

Invocar la acción Shell (Agregarlo en el evento actionperformanced del botón Shell) Para mostrar el resultado, se deberá invocar el método de la siguiente manera: txtlista.setText(obj.SHELL(n));

Universidad Nacional del Callao

Pág. 8

NOVENA SEMANA – Marco Práctico TRABAJO PRÁCTICO 1 Objetivo del Trabajo: Incentivar la investigación del alumno. Investigue en qué consiste el método de Ordenamiento Quick Sort (Ordenación Rápida), explíquelo, indique ventajas y desventajas, ilústrelo con diagrama de flujo, muestre paso a paso como se va dando la ejecución del algoritmo y realice la codificación Java para comprobar la eficacia de este método. 

Esfuérzate por hacer tu mismo este trabajo, es importante que lo compruebes en Java. No olvidar que se entrega el informe de este trabajo en un folder y también el disquete o CD. (Leer forma de presentación según aparece en la Diapositiva de la Semana 1).



Si alguno de sus compañeros no tiene esta guía de práctica, reenvíenlo a su correo.

Fecha de Entrega: Segunda clase de la semana 10

Universidad Nacional del Callao

Pág. 9

DÉCIMA SEMANA – Marco Teórico Logro Que el alumno comprenda y aplique los diferentes metodos de búsqueda que existen. Resumen Durante esta semana aprenderemos en qué consisten los métodos de búsqueda secuencial y binaria.

Métodos de Búsqueda MÉTODO DE BÚSQUEDA SECUENCIAL La búsqueda secuencial, también se le conoce como búsqueda lineal. Este método consiste en recorrer el arreglo o vector elemento a elemento e ir comparando con el valor buscado (clave). Se empieza con la primera casilla del vector y se observa una casilla tras otra hasta que se encuentre el elemento buscado o se han visto todas las casillas. El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero. Dado que el vector o arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el ultimo. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del vector. El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. Ventajas:  Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños (Hasta aproximadamente 500 elementos)  Es fácil adaptar la búsqueda secuencial para que utilice una lista enlazada ordenada, lo que hace la búsqueda más eficaz.  Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas búsquedas. Desventajas:  Este método tiende hacer muy lento.

Universidad Nacional del Callao 

Pág. 10

Si los valores de la clave no son únicos, para encontrar todos los elementos con una clave particular, se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

Caso Práctico: Realizar una aplicación Java que utilice POO, Estructura de Datos Estáticas (Arreglos) que aplique el método de búsqueda Secuencial. Lógica de Presentación Para desarrollar este caso utilizaremos el formulario frmOrdenamiento, cuyo diseño se presenta en el siguiente gráfico.

Universidad Nacional del Callao

Pág. 11

Método búsqueda Secuencial (Agregarlo en la clase Arreglos) Tipo de dato que retorna como respuesta: String Argumentos que recibe: longitud del arreglo. public String buscar(int n,int dato){ int i,a; a=0; String acu=""; String b=""; for(i=0;i0){ return acu; } else { return "Lo sentimos, el dato no ha sido encontrado..."; } }

Invocar la acción BusquedaSecuencial (Agregarlo en el evento actionperformanced del botón Búsqueda Secuencial) Para mostrar el resultado, se deberá invocar el método de la siguiente manera: double dato=Double.parseDouble(JOptionPane.showInputDialog("Ingrese el dato que desea buscar")); txtlista2.setText(String.valueOf(obj.buscar(n,dato)));

Universidad Nacional del Callao

Pág. 12

DÉCIMA SEMANA – Marco Práctico TRABAJO PRÁCTICO 2 Objetivo del Trabajo: Que el alumno se ejercite en la construcción de métodos que permitan realizar operaciones básicas con arreglos unidimensionales. Utilizando la metodología aprendida en clase, construya los métodos para resolver los siguientes requerimientos e invóquelos desde la Lógica de Presentación: Elabore los diagramas de flujo de cada uno de los métodos tratados durante esta semana y detalle paso a paso como se va desarrollando la ejecución del algoritmo. Esfuérzate por hacer tu mismo este trabajo, es importante que lo compruebes en Java. No olvidar que se entrega el informe de este trabajo en un folder y también el disquete o CD. (Leer forma de presentación según aparece en la Diapositiva de la Semana 1). Si alguno de sus compañeros no tiene esta guía de práctica, reenvíenlo a su correo. Fecha de Entrega: Segunda clase de la semana 11

Universidad Nacional del Callao

Pág. 13

DÉCIMA PRIMERA SEMANA – Marco Teórico Durante esta semana se llevarán a cabo los exámenes parciales, motivo por el cual las clases quedan suspendidas.

Universidad Nacional del Callao

Pág. 14

DÉCIMA SEGUNDA SEMANA – Marco Teórico Logro Que el alumno comprenda y aplique los diferentes algoritmos aplicados a arreglos bidimensionales. Resumen Durante esta semana detallaremos las siguientes operaciones: Cargar una matriz, Sumar dos matrices, Sumar Diagonales.

Operaciones con Arreglos Multidimensionales CARGAR UNA MATRIZ BIDIMENSIONALES Caso Práctico: Realizar una aplicación Java que utilice POO, Estructura de Datos Estáticas (Arreglos) que realice las siguientes operaciones básicas con los arreglos, tales como: Cargar una matriz bidimensional, Sumar dos matrices bidimensional y Sumar Diagonales. Lógica de Negocios Para desarrollar este caso utilizaremos la clase Matrices, dentro de la cual implementaremos los métodos que se detallan en esta unidad. Hasta el momento nuestra clase Matrices contiene lo siguiente: package Semana6; public class Matrices { public int stock[][]; public Matrices(){ stock=new int[100][100]; } public void cargarDatos(int f,int c,int dato){ stock[f][c]=dato; } public String mostrarTodoslosDatos(int nf,int nc){ String acu="";

Universidad Nacional del Callao

Pág. 15

for(int f=0;f...