• Author / Uploaded
• marcoantonio1103

Citation preview

Carátula para entrega de prácticas

Facultad de Ingeniería

Laboratorios de docencia

Laboratorio de Computación Salas A y B Profesor: Asignatura:

Tista García Edgar M.I. Estructuras de datos y algoritmos II

Grupo:

5

No de Práctica(s):

3

Integrante(s): No. de Equipo de cómputo empleado: Semestre: Fecha de entrega:

Barrera Peña Víctor Miguel 21 2019-2 24/02/2019

Observaciones:

CALIFICACIÓN: ________________

Contenido Objetivo: ................................................................................................................. 3 Actividades: ............................................................................................................ 3 Introducción: ........................................................................................................... 3 Desarrollo: .............................................................................................................. 6 Ejercicios propuestos por el profesor: ..................................................................... 6 Ejercicio 1. Counting Sort.................................................................................... 6 Solución: ............................................................................................................. 7 Evidencia de implementación:............................................................................. 8 Ejercicio 2. Radix Sort ......................................................................................... 8 Solución: ............................................................................................................. 8 Evidencia de implementación:........................................................................... 10 Ejercicio 3. Merge Sort ...................................................................................... 10 Solución: ........................................................................................................... 10 Evidencia de implementación:........................................................................... 11 Ejercicio 4. Conclusiones .................................................................................. 12 Conclusión ........................................................................................................... 12

2

Objetivo: El estudiante conocerá e identificará la estructura de los algoritmos de ordenamiento Counting Sort y Radix Sort.

Actividades: •

Implementar el algoritmo Counting Sort en algún lenguaje de programación para ordenar una secuencia de datos.

•

Implementar el algoritmo Radix Sort en algún lenguaje de programación para ordenara una secuencia de datos.

Introducción: Esta práctica constituye la tercera parte de algoritmos de ordenamiento y como es de esperar, se analizarán e implementar 2 algoritmos nuevos. Siendo designados Counting Sort y Radix Sort. Radix Sort es un algoritmo fácil de entender, por la lógica que procesa, lo único en donde reside su dificultad, es como implementar esas características que para nosotros los humanos es tan sencillo. Su funcionamiento es básicamente el siguiente: 1. Introducir N elementos a ordenar. 2. Determinar el rango de los valores posicionales. Por ejemplo, si quisiéramos ordenar al 1500, lo dividiríamos 1,5,0,0, indicando cada una de estas divisiones a la cola, que será designada entre iteraciones. Para este único elemento su rango es de [1-5], pero el rango si agregáramos 2987 el rango del conjunto seria [0-9]. Es decir, el rango es todo aquel valor posible (posicional) que puede tomar el conjunto a ordenar. 3. Hacer colas M en base al rango obtenido, tomando el rango ejemplo: [0-9] , serían 10 colas. 4. Seleccionar un elemento de los N elementos a ordenar. 5. Incluir ese elemento en la cola designada para ese valor posicional, en base al 1° valor posicional de dicho elemento (2° valor posicional==

3

2° iteración, etc.). Por ejemplo Cola[1].añadir = 1501 ; Cola[3].añadir = 1603. 6. Desencolar los elementos de cada Cola[ P ], siendo 𝑃 ∈ {0,1,2,3, … } en ese orden para ordenar de manera Ascendente, por el contrario

𝑃∈

{9,8,7,6, … } para ordenar de manera Descendiente. Obviamente al desencolar cada cola, sus elementos se almacenaran en la lista original. 7. Repetir desde el paso 2. Se repetirá por L veces, siendo L el número de dígitos de los números. Ya habiendo planteado el algoritmo, uno se pregunta ¿Dónde está lo caótico, si sobre el papel es fácil? Exacto, uno puede ver claramente el dígito de menor valor en cada número, pero para que la computadora lo identifique, es algo más difícil de implementar. Ahora, por parte de Counting Sort , es a mi parecer el algoritmo más fácil de hacer en papel y en computadora. Ya que este la lógica que procesa no es difícil de entender y de implementar tampoco como queda explicado su procedimiento: 1. Introducir N elementos a ordenar. 2. Obtener MIN y MAX que serán el mínimo y máximo número que está en los N elementos. 3. Calcular R=[MAX-MIN] que será el rango. 4. Con ayuda de la estructura auxiliar de tamaño R, donde en cada casilla de la misma se cuente el número de elementos I de en N que hay. Quedando la siguiente estructura Auxiliar={#i, #(i+1),…}. Por ejemplo teniendo R=[1,4] N={1,3,1,4,3} → Auxiliar={2,0,2,1}. 5. Sumar las casillas de auxiliar a cada casilla, el numero de suma de la propia casilla. Tomando del ejemplo anterior, Auxiliar {2,2+0,2+2,4+1} → Auxiliar={2,0,4,5} 6. Recorrer N de manera inversa, Auxiliar nos proporciona el índice donde debe ir el elemento, donde originalmente esta el conteo de ese 4

número. Tomando ese índice, y el elemento en cuestión, colocarlo en un nuevo arreglo, reducir la cantidad de Auxiliar de ese número, repetir este paso , hasta terminar el arreglo. 7. Copiar los elementos en el orden del arreglo ya ordenado al original. Viendo el anterior algoritmo, sólo es posible pensar varias maneras de implementarlo, las únicas decisiones que vemos entre ellas, son las variaciones de estructuras auxiliares para realizarlo, pero en cuanto a lógica sigue siendo lo mismo. Habiendo contemplado los anteriores algoritmos, es posible decir que estos algoritmos se basan en la empleamiento de estructuras auxiliares para realización, logrando que necesiten más espacio de memoria y que para el primer caso, su dificultad reside en el manejo de estructuras de datos , vistas en EDA 1.

5

Desarrollo: Ejercicios previos (análisis de diferencia entre la práctica suministrada por la división contra la teoría instruida por el profesor): Se explica:

Teórica (clase)

Práctica (La división)

Funcionamiento de Counting

Si

Si

Pseudo código de Counting Sort

Si

Si

Diagramas de funcionamiento

Si

Si

Funcionamiento de Radix Sort

Si

Si

Pseudo código de Radix Sort

Si

Si

Diagramas de funcionamiento

Si

Si

Documentos externos para

Diapositivas del

Enlaces externos para su

estudio

profesor

consulta

Ejercicios de Radix Sort y

Si

Si

Sort

Counting Sort

Radix Sort

Counting Sort

Ejercicios propuestos por el profesor: Ejercicio 1. Counting Sort Nota: En el lenguaje de tu preferencia (C o Java), realiza la implementación de Counting sort aplicado a un caso específico. Toma en cuenta los siguientes requerimientos: A. Utiliza un arreglo (lista) de 25 enteros, los cuales serán solicitados al usuario (asume que el usuario los va a ingresar correctamente) Para ello considera un rango de [55 a 63] B. Crea un segundo arreglo donde cada posición será asociada a uno de los posibles valores del rango indicado C. En una primera pasada al arreglo (lista) que llenó el usuario, realiza la cuenta de las apariciones de cada uno de los valores. (recuerda que eso se hace en un primer arreglo/lista auxiliar) D. Realiza la cuenta del arreglo; en cada índice se considera la cantidad de elementos actuales y los anteriores. Sugerencia, si tienes dificultades utiliza un arreglo adicional E. Crea un tercer arreglo para ingresar los elementos ordenados. F. Realiza una segunda pasada al primer arreglo, partiendo desde el final del mismo y para cada elemento, analiza la posición que le corresponde en el segundo arreglo y establece su posición final en el tercero. 6

Solución: El programa (llamado JavaApplication2) esta creado en NetBeans porque el IDE ayuda mucho a la creación de los programas en estos instantes donde el dominio sobre Java es muy pobre y este IDE marca automáticamente los errores e incluso mejorar el código al encontrar mejores maneras de implementar una misma idea. A) El programa contiene un arreglo de 25 elementos (desordenado) declarado para probar su funcionamiento y evitar la constante reintroducción de datos por parte del usuario, si se desea hacerlo manualmente, abajo del arreglo ya declarado existe un ciclo for, con el cual se llena el arreglo introduciendo 1 a 1 sus elementos, sólo es necesario quitarlo de comentario. B) El arreglo auxiliar fue creado dentro de la clase Counting Sort. Siendo llamado “contador_list” , que es donde se almacena las repeticiones de cada elemento. C) En el primer for del método sort() se realiza esta función e incluso aparece comentado debajo de este ciclo, otro ciclo , que de quitarse el comentado, muestra el “contador_list” con sus valores, sin incluir claro el primer elemento de esta lista. D) Se realiza la suma del arreglo como muestra el segundo ciclo, de igual manera hay un ciclo abajo para comprobar la suma visualmente. E) Se declara otro arreglo que fungirá para ordenar los elementos al recorrer la lista al revés. La lista en este caso se llama “lista_ordenada”. F) Se cumple a través del ultimo ciclo, a través de una notación un poco difícil de comprender, pero funcional. Observaciones: •

Uso la función System.arraycopy para devolver el valor de “lista_ordenada” a la lista ordenada.

•

Uso constructor para tener la lista incluida en la clase, solicitando únicamente como parámetros el mínimo y el máximo.

•

Creo el método add_array() para mandar el arreglo completo a el arreglo que esta en la clase CountingSort , por la razón de darle mas utilidades , además darle un posible ajustamiento para que trabaje con archivos en un futuro.

•

El algoritmo funciona perfectamente como se muestra en la ilustración 1, con datos ingresados por el usuario, arreglos ,etc. Debajo de cada ciclo contiene otro ciclo comentado para poder visualizar los movimientos del algoritmo en cuestión.

7

Evidencia de implementación:

Ilustración 1 Ejecución 1 del programa 1 Counting Sort

Ejercicio 2. Radix Sort Nota: En el lenguaje de tu preferencia (C o Java). Realiza la implementación de radix para el ejemplo visto en clase. Considera los requerimientos siguientes. Para la implementación de colas: 1. Si lo realizas en lenguaje c, podrás utilizar las colas vistas en eda1 2. Si lo realizas en lenguaje java, podrás utilizar la biblioteca que proporciona el lenguaje para dicho fin A. Los datos de entrada serán números de 4 dígitos, de entre los cuales solo aparecerán dígitos del 0 al 3 B. Deberás implementar una cola para cada uno de estos dígitos (0,1, 2, 3) C. Se deberán solicitar al usuario los valores a ordenar (mínimo 10), los cuales podrás almacenar en un arreglo o una lista D. Es necesario realizar varias pasadas sobre esta lista o arreglo, y en cada una de ellas utilizar las colas para almacenar los elementos de acuerdo con su posición (unidades, decenas, etc.). El programa deberá mostrar la lista resultante en cada iteración E. Al finalizar, el programa deberá mostrar la lista ordenada.

Solución: El programa (llamado JavaApplication3) esta creado en NetBeans porque el IDE ayuda mucho a la creación de los programas en estos instantes donde el dominio sobre Java es muy pobre y este IDE marca automáticamente los errores e incluso mejorar el código al encontrar mejores maneras de implementar una misma idea. A) Funciona con la entrada de números de 4 dígitos , de ser menor esta entrada aparecerá un error asociado a un índice que no existe, ya que la implementación que yo hice se basa en obtener el arreglo de números y tomar un elemento para asignarlo a su cola correspondiente , transformo el número a un String (Integer.toString) y selecciono el dígito que deseo (charAt()), es decir el chartAt()

8

dándole el índice de 4 a la transformación de un número de 3 cifras transformado, no hallaría la posición indicada. B) Se implementan 4 colas de tipo entero usando (Linkedlist) es la opción más conveniente que encontré porque había Arraylist,Dqueue, etc. Pero no lograba cumplir en alguna función con lo que yo necesitaba, y por eso es la implementación de esta estructura, obviamente limitando sus funciones , porque si no , su comportamiento no sería de una cola. C) Como mencione en el inciso B, implemente las colas. D) Varias pasadas son realizas en el programa, ya que para digito se necesita encolar en una cola de acuerdo al digito y desencolar todas para volverla al arreglo original. Para este inciso se utilizaron demasiados ciclos , ya que cada cola al no poseer un método que regresa todos los elementos , se tenía que retirar de 1 en 1. E) Se muestra ordenada la lista en la cuarta iteración, como agregado se puede decir que muestra la lista con todos los elementos después de cada iteración , es decir después de desencolar las 4 colas. Observaciones: •

En este caso existían muchas estructuras adyacentes, ya listas para la implementación en Java, quedaría la duda de cual es mejor para este caso, tal vez exista una cola de una sola dirección.

•

La implementación realizada para este programa es un poco deficiente por la transformación de datos Int a Char, en especial para su selección, la duda quedaría en que si hay una manera más eficientemente de realizar esa selección digito por digito si hacer una transformación.

•

Puedo decir que este programa funciona perfectamente para N elementos, mientras estén contemplados para las 4 colas que se plantean aquí. La ventaja de este código es que es muy fácil reescribirlo para que acepte más colas con diferentes dígitos, con demasiada facilidad, de hecho solo tienen que copiar y pegar pequeñas partes del código y cambiarle unos parámetros que hacen la selección y listo.

9

Evidencia de implementación:

Ilustración 2 Ejecución 1 del programa 2 Radix Sort

Ejercicio 3. Merge Sort Nota: Con ayuda de NetBeans, abre el proyecto proporcionado, el cual es una implementación de Merge Sort en Java. A. Agrega las instrucciones en la clase Principal, en el método main, para poder crear un arreglo de enteros, crear una instancia de la clase Merge Sort Y a través de esa instancia realizar el ordenamiento por Merge Sort. B. Realiza un análisis del programa indicando cómo es que se realiza la división de esta y posteriormente la combinación ya ordenada de las sub-listas. C. Modifica la clase Merge Sort, de tal manera que se puedan imprimir en pantalla las iteraciones del algoritmo (las divisiones de la lista en 2).

Solución: A. Use para este caso la declaración de un arreglo ya definido, ya que con ele no es necesario tener que estando introduciendo los elementos que constituyen el arreglo, y en este caso decidí que fuera de 10 elementos desordenados, por la simple razón de que no se crean tantas sub-listas que serían un desastre como captura de

10

pantalla, sino que son más difíciles de observar su comportamiento y de como se reacomodan. B. El programa esta constituido de 3 métodos. printArray() que recibe un arreglo y lo imprime en pantalla, en este caso para mostrar las nuevas sub-listas derivadas de la original. Merge() se encarga de dividir la lista en 2 , crear ambas listas, asignar los valores a cada lista, y a partir de donde empiezan los ciclos while() es donde suceden las intercalaciones entre las sub-listas ya divididas. Por otro lado Sort() se encarga de calcular la mitad de los elementos que se le darán al método Merge() y más que nada limitar este en sus particiones, además este es un método recursivo. Los demás elementos de mi análisis se encuentran en comentarios en el programa. C. Esta opción fue muy fácil de implementar, siguiente de que el método Merge() llenaba la lista izquierda y derecha , lo incluí aprovechando de que el método printArray() imprimé un arreglo , ambas listas se las pase como parámetro.

Evidencia de implementación:

Ilustración 3 Ejecución del programa 3 parte 1 (la consola era demasiado grande para una sola toma)

Ilustración 4 Ejecución 1 del programa 3 parte 2

11

Ejercicio 4. Conclusiones Escribe las conclusiones de tu práctica en la cual incluyas comentarios generales de todos los algoritmos de ordenamiento vistos en las primeras 3 prácticas del curso

Conclusión Esta práctica fue sencilla comparada con las 2 anteriores prácticas sobre algoritmos de ordenamiento, principalmente porque los algoritmos son fáciles de comprender en su funcionamiento, lo difícil es manipular los datos con las estructuras en un nuevo lenguaje de programación (Java). El objetivo de esta práctica era comprender el funcionamiento de Radix Sort, Counting Sort e implementarlo. En esta práctica se logró la implementación de ambos algoritmos y su compresión, ya que, al transcurso de la realización de los programas, se tuvo que encontrar maneras alternativas de implementación, por errores lógicos imprevistos, además del poco dominio de Java. Por anterior dicho, puedo justificar el decir que esta práctica se ha cumplido exitosamente, además de añadir de con esta se ha explorado muchas más opciones del lenguaje Java que en todas las prácticas de POO y EDA 2 juntas hasta ahora. Creo que esta práctica te impulsa en gran medida hacia el explora miento de nuevas características en Java de las que C no estaba dota, ya que en este lenguaje la mayoría de las acciones eran por cuenta propia.

12