Analisis de algoritmos

Vista previa del material en texto

Universidad de Guadalajara 
Centro Universitario de Ciencias Exactas e Ingenierías 
División de Tecnologías para la Integración Ciber Humana 
Departamento de Ciencias Computacionales 
Informática 
Algoritmia 
Act#2 Análisis de algoritmos. 
 
 
 
 
 
 
 
 
 
 
Alumno: Valenciano Tadeo Jeremy Esau 
Código: 218431076 
Bubble Sort 
¿Como funciona el Bubble Sort? 
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. 
Eficiencia: Bubble Sort es uno de los algoritmos más discutidos, simplemente por su 
falta de eficiencia para ordenar arrays. Si un array ya está ordenado, Bubble Sort sólo 
pasará por el array una vez (usando el concepto dos de abajo), sin embargo el peor 
escenario es un tiempo de ejecución de O(N²), que es extremadamente ineficiente 
Orden: Cuadrático 
Complejidad caso promedio: O(n^2) 
Complejidad mejor caso: O(n) 
Complejidad peor caso: O(n^2) 
 
Insertion Sort 
¿Como funciona el Insertion Sort? 
Funciona dividiendo el array en dos partes: un subarray ordenado y otro sin ordenar. La 
ordenamiento por selección encuentra el elemento más pequeño dentro del subarray sin 
ordenar y lo mueve al último índice del subarray ordenado 
Eficiencia: Para n muy pequeño, Insertion Sort es más rápido que otros algoritmos más 
eficientes como Quicksort o Merge Sort. 
Orden: Cuadratico 
Complejidad caso promedio: O(n^2) 
Complejidad mejor caso: O(n) 
Complejidad peor caso: O(n^2) 
 
Quick Sort 
¿Como funciona el Quick Sort? 
Basado en la técnica divide y vencerás, se deberá elegir un elemento del conjunto de 
elementos a ordenar, al que llamaremos pivote. Resituar los demás elementos de la lista 
a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al 
otro los mayores. 
Eficiencia: Quicksort es muy eficiente para ordenar conjuntos de datos pequeños. 
También es el algoritmo de ordenación preferido cuando la asignación de memoria 
adicional es costosa, este algoritmo es bastante eficiente para conjuntos de datos de 
gran tamaño, ya que su complejidad el peor de los casos son O(n^2), respectivamente. 
Orden: Logaritmico 
Complejidad caso promedio: O(n log n) 
Complejidad mejor caso: O(n log n) 
Complejidad peor caso: O(n^2) 
 
 
 
 
Shell Sort 
¿Como funciona el Shell Sort? 
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. 
Eficiencia: La ordenación Shell es un algoritmo de ordenación muy eficiente y se basa 
en el algoritmo de ordenación por inserción. Este algoritmo evita grandes 
desplazamientos como en el caso de la ordenación por inserción, si el valor más 
pequeño está en el extremo derecho y tiene que ser desplazado al extremo izquierdo. 
Orden: Logaritmico 
Complejidad caso promedio: O(n (log (n))^2) 
Complejidad mejor caso: O(n log n) 
Complejidad peor caso: O(n (log (n))^2) 
 
Merge Sort 
¿Como funciona el Merge Sort? 
Se basa en la estrategia de dividir y conquistar. La ordenación por combinación corta 
continuamente una lista en múltiples sublistas hasta que cada una de ellas tiene un solo 
elemento, y luego combina esas sublistas en una lista ordenada. 
Eficiencia: La ordenación por fusión es uno de los algoritmos de ordenación más 
eficaces. es un poco más complejo que la selección y la ordenación por burbujas, pero 
es más eficiente. podemos decir que el Merge Sort es eficiente en términos de tiempo y 
el Insertion Sort es eficiente en términos de espacio. 
Orden: Logarítmico 
Complejidad caso promedio: O(n log n) 
Complejidad mejor caso: O(n log n) 
Complejidad peor caso: O(n log n) 
 
 
 
Ciclos vs Recursividad 
El bucle es más eficiente para las factoriales. Cuando haces recursión, tienes hasta x 
llamadas a funciones en la pila. Casi nunca se utiliza la recursión por razones de 
rendimiento. Se utiliza la recursión para hacer el problema más simple. 
¿Son las funciones recursivas más eficientes? 
Los algoritmos y métodos iterativos suelen ser más eficientes que los algoritmos 
recursivos. La recursividad se basa en dos conceptos clave para la resolución de 
problemas: divide y vencerás y la autosimilitud. Una solución recursiva resuelve un 
problema resolviendo una instancia más pequeña del mismo problema. 
 Desde mi punto de vista podría resumir que el uso de ciclos se considera más eficiente 
en general para la implementación de algoritmos, debido a que el uso de la recursividad 
hace uso de una pila de funciones, por otra parte, al implementar un algoritmo mediante 
la recursividad lo que se esta buscando es la simplificación del problema. 
 
 
 
 
 
 
 
Reporte Capitulo: "1.5 Example: Analysis of Quicksort" 
A lo largo de este capítulo se habla básicamente sobre el análisis algorítmico del 
ordenamiento QuickSort el cual se basa en la filosofía divide y vencerás, se explica 
cómo se elige un pivote el cual ayudara a comparar los elementos del arreglo que sean 
mayores o menores al pivote, al mismo tiempo se necesitan de los extremos izquierdos 
y derechos del arreglo. Se explica que la implementación de este algoritmo es recursivo 
por lo que se detendrá hasta que los subarreglos sean de longitud 1. 
Después de explicar el algoritmo Quicksort se ejemplifica el como una instrucción de un 
bucle while se traduciría a lenguaje ensamblador, así como el costo en unidades de la 
ejecución de dicho bucle. Después se habla acerca de asignar nombres de variables a 
la frecuencia de ejecución de las instrucciones en el programa y el como el valor de 
dichos coeficientes puede variar dependiendo el lenguaje de programación, por otra 
parte, se hace una referencia al algoritmo MergeSort y el cómo el costo de comparación 
es menor en Quicksort lo cual nos lleva a un tiempo de ejecución menor en casos 
prácticos de aplicación. Finalmente se exponen diferentes fórmulas para el cálculo del 
número de comparaciones e intercambios que realiza el algoritmo Quicksort. 
 
 
Bibliografia: 
 
• Sedgewick, R. & Flajolet, P. (2013, 18 enero). Introduction to the Analysis of Algorithms, 
An (2.a ed.). Addison-Wesley Professional.