Estructura de datos Informe N°1

   [pic 1][pic 2]

Estructura de datos

Informe N°1

-Carrera: Ingeniería civil en Informática.

-Asignatura: Estructura de datos.

-Profesor: Hugo Araya Carrasco.

-Integrantes:  - Matías Marchant Quintero (20.706.322-3)

                        - Matías Morales Vergara (20.305.081-K)                  

-Fecha de entrega: 31-05-2021

Abstract

El presente informe científico tiene como propósito realizar un enfoque proveniente de la rama de estructura de datos, en donde se llevara a cabo un análisis y desarrollo mediante 2 computadores con distinto sistema operativo(Linux y Windows) sobre 3 métodos de ordenamiento, los cuales son: Bubble sort, Shell sort y  por ultimo Quick sort, a través de sus correspondientes algoritmos, logrando ordenar 1.000.000 de datos inversos, ordenados y aleatorios, añadiendo a su desarrollo ciertos códigos para medir su tiempo de ejecución  para posteriormente anotarlos en una tabla confeccionada y así lograr graficarlos con el objetivo de ser comparados y respaldados por su evidencia teórica.

Palabras claves: Ordenamiento, Bubble sort, Shell sort, Quick sort, algoritmos, resultados.

Índice

1. Introducción……………………………………………………………….pág.4
2. Marco metodológico……………………………………………………....pág.5-8

• Algoritmo Bubble sort…………………………………………….pág.5
• Algoritmo Shell sort………………………………………………pág.6
• Algoritmo Quick sort……………………………………………..pág.7

1. Presentación de los resultados…………....................................................pág.9-12

• Resultados Bubble sort……………………………………………pág.10
• Resultados Shell sort……………………………………………..pág.11
• Resultados Quick sort……………………………………………pág.12

1. Conclusiones y sugerencias………………………………………………pág.
2. ………
3. ………….
4. ………….
5. …………..
6. ………….
7. ………….

Introducción

Dentro de las ramas de la programación, nos encontramos la estructura de datos, la cual es una forma determinada de organizar datos para llegar a utilizarlos de la forma más eficaz, todo esto dentro de un equipo informático. Y es que hablar sobre la organización de datos, nos lleva a pensar en métodos de ordenamiento, los cuales son procesos de reagrupamiento de conjuntos de datos en orden creciente o decreciente y esto nos hace preguntarnos, ¿Existe algún método de ordenamiento dentro de todos que sea el más eficaz?, ¿Habría diferencias notorias entre sistemas operativos? Y de ser así ¿Cuál es el sistema operativo con mayor optimización?

En el presente informe expondremos 3 métodos de ordenamiento, los cuales llevan por nombre: Bubble sort, Shell sort y Quick sort, es por esta razón que el objetivo principal es conocer los distintos métodos de ordenamiento, para luego analizar y diferenciar sus resultados, específicamente, el tiempo de ejecución, en segundos, que se toman en ordenar 1.000.000 de datos ascendentes, descendentes y aleatorios, a través de sus correspondientes algoritmos y además conocer la eficacia de estos mismos, por lo tanto para lograr un análisis más a fondo, será necesario interpretar los resultados, comparándolos a través de gráficos para un mayor entendimiento.

Los algoritmos serán probados a través de 2 computadores con distinto sistema operativo, los cuales serán Linux y Windows, por lo que obtendremos sus comportamientos y notaremos cuanta eficiencia llegan a lograr utilizando en común el editor de código llamado: Visual Studio Code, en unión con Code::Blocks y el lenguaje de programación C para los algoritmos.

Métodos de Ordenamiento

Primero que nada, se necesita saber la definición de los 3 métodos de ordenamientos que serán ocupados durante el desarrollo de este informe científico, los cuales se definen como:

Algoritmo Bubble sort: Conocido también como ordenamiento de burbuja, es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.

[pic 3]

[pic 4]Algoritmo Shell sort: Es un algoritmo de ordenamiento el cual, de una lista o vector de datos los ordena; al estar leyendo la lista utiliza un solo tipo de comparación abstracta y de esta manera determina que elemento de la lista va primero, cual le sigue y quien va al final de la lista. 

Algoritmo Quick sort: Este algoritmo se basa en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

[pic 5]

Marco metodológico

Para los 3 métodos de ordenamiento, tenemos la misma cantidad de algoritmos correspondientes a Bubble sort, Shell sort y Quick sort, cada una con sus respectivas operaciones y funciones matemáticas, además de 3 códigos para generar archivos de textos con 1.000.000 de datos de manera ordenada o ascendente, inversa o descendente y finalmente, datos aleatorios, añadiendo a este conjunto de algoritmos un código para medir el tiempo de ejecución, todo esto dentro del editor de código, Visual Studio Code y en lenguaje C.

Para lograr una comparación mas detallada, fue necesario ocupar 2 máquinas con distinto sistema operativo:

• El primer computador contiene una instalación con el sistema operativo de Linux 2.6, gracias a la aplicación “Virtual Box”, el cual cuenta con un procesador Intel Core i7 y una RAM de 4gb
• El segundo computador contiene como sistema operativo Windows 10 Home Single, el cual cuenta con un procesador Intel Core i5 y una RAM de 8gb.

Diseño de la investigación

1. Lo primero que hicimos fue un estudio a los conceptos principales, ósea los 3 métodos de ordenamiento con el objetivo de entender su aplicación e identificar sus algoritmos.
2. Posteriormente procedimos a instalar el editor Visual Studio Code y Code::Blocks para poder dar comienzo a probar todos los códigos que se requerían utilizar en los programas.
3. Luego, mediante ensayo y error, fuimos probando los códigos de la fuente de programas, GitHub, en donde tuvimos que redireccionar los programas generadores de archivos de datos para que nos creara 3 archivos de texto con 1.000.000 de datos, el primero fue de datos inversos, ósea de manera descendente, el segundo, fue de datos ordenados, ósea, de manera ascendente y el ultimo de datos aleatorios, todos con números de hasta 6 dígitos.[pic 6]
4. Para poder lograr que el programa se ejecutara correctamente, fue necesario abrir el “CMD” desde la terminal y diferenciar la llamada al programa entre sistema operativo, ya que notamos que en Windows se podía llamar simplemente escribiendo el nombre del programa (como aparece en la imagen de a continuación, ej.: bubble_sort) pero en Linux era necesario colocar “./” antes del nombre del programa.
5. Cuando se ejecutaba correctamente tuvimos que siempre anotar desde, hasta y cuanto incremento queríamos que procesara, y así lograr que respecto al método de ordenamiento vaya reagrupando los datos y el programa nos entregara la diferencia entre el tiempo final e inicial, siendo ese el tiempo de ejecución, de cuanto se demora en ordenar todos los datos. [pic 7]

El proceso de ejecución nos tomo algunas horas debido a que tuvimos que encontrar nuestro limite de datos a procesar y así lograr que creara los archivos de salida y dentro de ella las matrices con los tiempos de los datos inversos, ordenados y aleatorios, en ese orden respectivamente.

Como técnicas de análisis, usamos los datos entregados por las máquinas, Linux y Windows; los datos que obtuvimos los derivamos a un documento Excel en donde fueron ordenados con el tipo de algoritmo y el método de ordenamiento de los datos en forma de tabla. Ya teniendo todos los datos obtenidos y ordenados como corresponde, procedimos a confeccionar los gráficos con los resultados de cada tabla para analizar y diferenciar los tiempos de cada algoritmo.

...