1 3 Ordenamiento y Búsqueda

Vista previa del material en texto

Nombre del alumno: Antony Arturo García Pérez
Matrícula: 2020690020
Carrera: Licenciatura en Ciencia de Datos
Nombre de la materia: Algoritmos y Estructura de Datos
Nombre del docente: Carlos Basulto González
1.3 Ordenamiento y Búsqueda
Sabinas, Coahuila							12/11/2020
1. Investiga sobre la lógica de funcionamiento de los algoritmos de Burbuja, de Inserción, y de Selección. 
La Ordenación de burbuja (Bubble Sort en inglés) 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. ... También es conocido como el método del intercambio directo.
El algoritmo de ordenamiento por inserción es un algoritmo de fácil aplicación que permite el ordenamiento de una lista. Su funcionamiento consiste en el recorrido por la lista seleccionando en cada iteración un valor como clave y compararlo con el resto insertándolo en el lugar correspondiente
Algoritmo de ordenamiento por Selección (Selection Sort en inglés): Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo.
Selecciona uno de los siguientes algoritmos: Cocktail Sort, Quick Sort, o Shell Sort, investiga sobre él y programa el algoritmo utilizando PSeInt; deberá ser capaz de ordenar una lista de 20 elementos. 
El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementación con un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar un sentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
1. El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
2. Investiga sobre los algoritmos de Búsqueda y programa en PSeInt el algoritmo que pueda realizar una búsqueda sobre una lista de 20 elementos. 
Algoritmos de Búsqueda
Un algoritmo de búsqueda es un conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.
La variante más simple del problema es la búsqueda de un número en un vector.
Búsqueda binaria
En ciencias de la computación y matemáticas, la búsqueda binaria, también conocida como búsqueda de intervalo medio1​ o búsqueda logarítmica,2​ es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado.3​4​ Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continua en la mitad restante hasta que el valor se encuentre.
La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando {\displaystyle O{\bigl (}\log n{\bigr )}} comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O (1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array.5​ Aunque estructuras de datos especializadas en la búsqueda rápidas como las tablas hash pueden ser más eficientes, la búsqueda binaria se aplica a un amplio rango de problemas de búsqueda.
Aunque la idea es simple, implementar la búsqueda binaria correctamente requiere atención a algunos detalles como su condición de parada y el cálculo del punto medio de un intervalo.
Existen numerosas variaciones de la búsqueda binaria. Una variación particular (cascada fraccional) acelera la búsqueda binaria para un mismo valor en múltiples arreglos.
Conclusión
Al concluir esta actividad pude entender a cerca de los diferentes tipos de algoritmos que existen y son muy útiles a la hora de ordenar ciertos datos, además de que pude practicar y crear distintos algoritmos para crear programas donde estos son útiles.
Referencias
· Mezzadri, Daniels. ¿Qué es un algoritmo? Consultado el 12 de noviembre de 2020. De: https://dmezzadri.com/que-es-un-algoritmo/
· Astrachan, Owen (2003). Ordenamiento de burbuja: Un análisis arqueológico de un algoritmo. SIGCSE. Consultado el 12 de noviembre de 2020. De: https://users.cs.duke.edu/~ola/papers/bubble.pdf
· Andrea Navarro. (2016). Ordenamiento por inserción – Algoritmos de ordenamiento. Consultado el 12 de noviembre de 2020. De: https://juncotic.com/ordenamiento-por-insercion-algoritmos-de-ordenamiento/#:~:text=El%20algoritmo%20de%20ordenamiento%20por%20inserci%C3%B3n%20es%20un%20algoritmo%20de,insert%C3%A1ndolo%20en%20el%20lugar%20correspondiente
· Weiss, Mark Allen (2002). Data Structures & Problem Solving using Java. Addison Wesley.
· Weisstein, Eric W Binary Search En Weisstein, Eric W, ed. MathWorld Wolfram Research