CS50x 2024 - Lecture 3 - Algorithms

¿Cómo pensar algorítmicamente?

Introducción a los algoritmos

• David Malan introduce la semana 3 de CS50, enfocándose en algoritmos y su implementación, dejando de lado la nueva sintaxis por un momento.

• Se menciona la importancia de cuantificar problemas del mundo real para poder resolverlos mediante código.

Gráfica de Problemas

• Se recuerda una gráfica presentada en la semana cero que relaciona el tamaño del problema (eje x) con el tiempo necesario para resolverlo (eje y).

• El primer algoritmo discutido fue uno que revisaba una página a la vez, representado por una pendiente de 1:1.

• Un segundo algoritmo revisaba dos páginas a la vez, lo que aumentaba la velocidad pero también introducía riesgos de errores.

• El tercer algoritmo era fundamentalmente diferente, mostrando un crecimiento logarítmico donde aumentar el tamaño del problema no incrementaba significativamente el tiempo requerido.

Ejercicio Práctico

• Malan propone un ejercicio práctico para tomar asistencia utilizando diferentes métodos algorítmicos.

• Los participantes deben emparejarse y sumar sus números, lo que ilustra cómo se puede optimizar un proceso al dividir tareas.

Observaciones sobre el Algoritmo

• A medida que los participantes continúan emparejándose y sumando números, se observa cómo algunos quedan sentados mientras otros siguen participando.

• Malan ayuda a facilitar las parejas entre los participantes para asegurar que todos estén involucrados en el ejercicio.

Conclusiones sobre Eficiencia

• Al final del ejercicio, se destaca que este método debería ser más eficiente comparado con contar uno por uno o en pares debido a su naturaleza divisoria.

¿Cómo funciona el algoritmo de dividir y conquistar?

Introducción a un error en el mundo real

• Se presenta un error al contar personas en una sala, lo que ilustra la importancia de los algoritmos. Aunque se esperaba que funcionara, se perdieron algunos números.

• El concepto de "dividir y conquistar" es fundamental; implica reducir problemas dividiendo el conjunto en partes más pequeñas, lo que resulta en un proceso más eficiente.

Aplicaciones del algoritmo

• Este enfoque se utiliza en dispositivos móviles al buscar contactos mediante autocompletado, donde no se revisa cada entrada secuencialmente sino que se divide el espacio de búsqueda.

• La idea es similar a cómo las personas deberían haber contado desde 1 hasta llegar a un número final representando a todos.

Estructuras de datos simples

• Se introduce la noción de estructuras de datos simples como arreglos, describiendo su naturaleza como colecciones contiguas de bytes en la memoria.

• Un arreglo no solo es una colección, sino que tiene características clave: debe ser contiguo y puede contener diferentes tipos de datos (enteros, flotantes).

Importancia del almacenamiento contiguo

• En C, los arreglos son cruciales porque permiten almacenar valores consecutivos en la memoria, facilitando el acceso rápido a los datos.

• La disposición contigua permite resolver problemas eficientemente al acceder directamente a posiciones específicas dentro del arreglo.

Búsqueda dentro del arreglo

• Al buscar un número específico (como 50), se destaca que la computadora no tiene una vista general; debe revisar cada posición individualmente.

• Esta analogía con casilleros ilustra cómo los datos están ocultos detrás de puertas cerradas y deben ser accedidos uno por uno para encontrar información específica.

Terminología y notación

• Se presentan casilleros etiquetados para representar índices dentro del arreglo. La notación entre corchetes indica cómo acceder a elementos específicos.

Introducción a la Búsqueda de Datos

Conceptos Básicos de Algoritmos de Búsqueda

• Se introduce el concepto fundamental de un problema a resolver, utilizando un arreglo de números como ejemplo para ilustrar la búsqueda.

• El objetivo es determinar si un número específico (por ejemplo, 50) está presente en el arreglo y devolver un resultado verdadero o falso.

• La discusión se centra en cómo diseñar un algoritmo efectivo para encontrar el dato deseado, enfatizando que los ejemplos pueden extenderse más allá de números a otros tipos de información.

Participación del Público

• Se invita a dos voluntarios al escenario para participar en una demostración práctica relacionada con la búsqueda.

• Los voluntarios se presentan: Sam, quien estudia matemáticas aplicadas, y Louis, que cursa economía con estadísticas.

Ejercicio Práctico: Encontrando el Número 50

• Sam recibe la tarea de buscar el número 50 entre siete casilleros sin ninguna pista adicional sobre su orden o contenido.

• Después de revisar los casilleros, Sam encuentra varios billetes falsos antes de finalmente localizar el número 50.

• Al explicar su proceso, menciona que no tenía un algoritmo definido y simplemente revisó cada casillero hasta encontrarlo.

Análisis del Algoritmo Utilizado

• Se discute si Sam podría haber optimizado su búsqueda; aunque encontró el número, lo hizo en cinco pasos.

• Se plantea la idea de ordenar los billetes primero como una posible estrategia más eficiente para búsquedas futuras.

Reflexiones sobre Eficiencia en Búsquedas

• Aunque ordenar puede parecer ineficiente inicialmente, podría ser útil si se planea realizar múltiples búsquedas en grandes conjuntos de datos.

• La presentación continúa mostrando diferentes arreglos numéricos mientras se explora cómo varía la eficiencia dependiendo del orden inicial y las decisiones tomadas durante la búsqueda.

Estrategias de Búsqueda en Algoritmos

Introducción a la Búsqueda

• Se presenta la idea de que los números están ordenados, lo que permite aplicar diferentes estrategias para encontrarlos.

• Louis menciona que conoce algunos números y decide comenzar su búsqueda desde el medio del conjunto.

Proceso de Búsqueda

• Al encontrar el número 20, Louis deduce que debe buscar hacia la derecha, dividiendo así el problema en dos partes.

• Louis identifica que el número 50 se encuentra entre 20 y 100, mostrando un enfoque lógico en su búsqueda.

Técnicas Utilizadas

• La estrategia inicial de Louis refleja una técnica intuitiva de deducción basada en la memoria, aunque no debería haberla utilizado.

• Se introduce el concepto de "hashing" como una técnica futura relacionada con cómo se puede acceder directamente a información específica.

Formalización de Algoritmos

• Se define la "búsqueda lineal", donde se revisan elementos uno por uno hasta encontrar el objetivo o concluir que no está presente.

• El pseudocódigo es presentado para ilustrar cómo se implementaría esta búsqueda lineal en términos más técnicos.

Comparación con Búsqueda Binaria

Búsqueda Binaria y Pseudocódigo

Introducción a la Búsqueda Binaria

• La búsqueda binaria se compara con buscar en una guía telefónica, dividiendo repetidamente el conjunto de datos por la mitad.

• Se identifican cuatro posibles escenarios al buscar información: encontrar el valor en la puerta del medio, buscar a la izquierda, buscar a la derecha o que no esté presente.

Manejo de Casos Especiales

• Es crucial manejar el caso donde no hay puertas disponibles para evitar que el programa se congele.

• El pseudocódigo propuesto refleja cómo se puede implementar esta lógica en un algoritmo de búsqueda binaria.

Detalles del Pseudocódigo

• En el pseudocódigo, "puertas" representa un arreglo y "puertas[middle]" indica acceder a la puerta del medio.

• Se optimiza el proceso evitando volver a investigar la puerta media si se busca hacia los lados.

Transición al Código Real

• Al escribir código real (por ejemplo, en C), es útil comenzar con pseudocódigo para facilitar la transición a sintaxis más precisa.

• Los problemas de redondeo son comunes al trabajar con enteros y deben ser considerados durante la implementación.

Eficiencia de Algoritmos

Medición del Tiempo de Ejecución

• Se plantea cómo medir la eficiencia de un algoritmo; no solo con cronómetros sino también considerando su comportamiento teórico.

• La eficiencia se describe matemáticamente como n (número total de elementos), donde log base 2 representa cuántas veces se puede dividir n hasta llegar a uno.

Conceptos Clave sobre Eficiencia

• Los científicos computacionales tienden a hablar sobre tiempos de ejecución en términos generales, ignorando detalles menores como factores constantes.

¿Cómo se mide la eficiencia de los algoritmos?

Conceptos básicos sobre la eficiencia de los algoritmos

• La eficiencia de un algoritmo puede ser generalizada como log(n), independientemente de los números específicos involucrados. A medida que n aumenta, las diferencias entre ciertos algoritmos se vuelven menos significativas.

• Cuando se evalúa la eficiencia, los términos constantes son desechados porque no afectan significativamente el rendimiento cuando n es grande. Esto permite una mejor comprensión del comportamiento del algoritmo en casos extremos.

Notación Big O

• La notación "Big O" (O mayúscula) es un término técnico utilizado para describir la complejidad algorítmica y es fundamental en ciencias de la computación. Se utiliza para clasificar algoritmos según su tiempo de ejecución o espacio requerido en función del tamaño de entrada.

• Un algoritmo con una complejidad O(n) implica que el tiempo requerido crece linealmente con respecto al número de elementos a procesar, lo que significa que en el peor caso tomará n pasos para completarse.

Ejemplos prácticos

• El algoritmo de búsqueda lineal tiene una complejidad O(n), ya que requiere revisar cada elemento hasta encontrar el objetivo, lo cual puede llevar hasta n pasos si el objetivo está al final.

• En contraste, un algoritmo con complejidad O(n²) implica que cada elemento debe interactuar con todos los demás elementos, como en el caso hipotético donde todos deben darse la mano; esto resulta en aproximadamente n² interacciones.

Complejidades constantes y otras notaciones

• Un algoritmo con complejidad O(1) indica que toma un número constante de pasos sin importar cuántos elementos haya; por ejemplo, si todos se levantan al mismo tiempo, eso sería considerado tiempo constante.

• Existen diferentes tipos de complejidades: lineales (O(n)), constantes (O(1)), cuadráticas (O(n²)), logarítmicas (O(log n)) y otras más avanzadas como O(n log n). Cada tipo describe cómo varía el tiempo o espacio requerido a medida que cambia el tamaño del input.

Comparación entre búsquedas

• La búsqueda binaria tiene una complejidad O(log n), ya que divide repetidamente el conjunto a buscar por la mitad, lo cual reduce drásticamente el número total de pasos necesarios incluso en peores escenarios.

• Es importante considerar tanto los mejores como los peores casos al evaluar algoritmos; por ejemplo, tanto la búsqueda lineal como la binaria pueden tener un mejor caso donde solo se necesita un paso si se encuentra rápidamente el objetivo deseado.

Notación Omega

• La notación omega (Ω) representa límites inferiores y complementa a Big O; mientras Big O describe cuántos pasos podría tomar un algoritmo en su peor caso, omega indica cuántos pasos podría tomar en su mejor caso posible.

¿Cómo se mide la complejidad algorítmica?

Introducción a la notación Big O y Theta

• Se establece que el tiempo de asistencia es O(n), ya que se debe señalar a cada persona en una sala con n personas.

• En el mejor y peor caso, algunos algoritmos requieren n pasos, lo que lleva a la introducción de la notación theta para describir este comportamiento.

• La notación theta se utiliza cuando las notaciones Big O y Omega son iguales, indicando que un algoritmo tiene un rendimiento consistente en ambos casos.

Implementación del Algoritmo de Búsqueda Lineal

• Se menciona la transición hacia la implementación del algoritmo de búsqueda lineal en C, utilizando enteros como ejemplo inicial.

• Se incluye el encabezado CS50.h para solicitar al usuario un número a buscar y se declara un arreglo con valores predefinidos usando llaves.

Ejecución del Algoritmo

• El código solicita al usuario un valor n y comienza a implementar la búsqueda lineal mediante un bucle for que itera sobre los elementos del arreglo.

• Si se encuentra el número buscado, se imprime "found"; si no, "not found". Sin embargo, hay una crítica sobre cómo manejar múltiples resultados negativos.

Correcciones Lógicas en el Código

• Se identifica un error lógico donde siempre imprime "not found" incluso si el número fue encontrado. Esto requiere ajustes en la estructura condicional del código.

• Para corregirlo, se sugiere eliminar una cláusula else y mover el mensaje "not found" fuera del bucle para evitar confusiones.

Manejo de Salidas en C

• Se recuerda que la función main puede devolver valores enteros; por convención, 0 indica éxito mientras que otros números indican fallas.

Comprendiendo el retorno de valores en C

Conceptos básicos sobre el retorno de valores

• En C, retornar 0 desde la función main indica que el programa ha finalizado correctamente, mientras que cualquier otro valor (1, 2, etc.) puede indicar diferentes tipos de errores.

• Al retornar un valor desde main, se termina la ejecución del programa inmediatamente; no se ejecutará ningún código adicional después de la instrucción de retorno.

Importancia del manejo de errores

• Aunque retornar un valor diferente a cero no cambia funcionalmente el programa, es útil para los programadores y asistentes entender qué ocurrió durante la ejecución.

Introducción a arreglos de cadenas

• Se presenta un nuevo tipo de arreglo: un arreglo de cadenas. Esto permite almacenar múltiples cadenas en lugar de solo números.

• El uso de notación con corchetes permite al compilador determinar automáticamente cuántos elementos hay en el arreglo basado en las comas.

Búsqueda dentro del arreglo

• Se solicita al usuario una cadena para buscar dentro del arreglo. Si se encuentra la cadena, se imprime "found" y se retorna 0; si no, se imprime "not found" y se retorna 1.

Comparación correcta entre cadenas

• En C, para comparar cadenas no se utiliza == como con los enteros; es necesario usar la función strcmp definida en <string.h>.

• La función strcmp devuelve 0 si las dos cadenas son iguales. Por lo tanto, debemos verificar que su resultado sea cero para confirmar que las cadenas coinciden.

Errores comunes y soluciones

• Un error común es olvidar incluir el archivo encabezado correspondiente (<string.h>), lo cual puede causar fallos en tiempo de compilación.

¿Cómo se comparan las cadenas en programación?

Comparación de Cadenas

• La comparación de cadenas no se limita a determinar si son iguales o no; también puede implicar evaluar su similitud.

• En la programación, es común ordenar información, lo que hace útil saber si una cadena es igual a otra o cuál precede a la otra alfabéticamente.

• La función str compare permite comparar dos cadenas no solo por igualdad, sino también por un orden específico llamado "ASCII-betical".

• str compare devuelve cero si las dos cadenas son iguales y compara los valores enteros de los caracteres para determinar el orden.

• Es importante notar que el uso de equals, equals en otros lenguajes como Java o Python tiene un comportamiento diferente al de C.

Implementación Práctica: Agenda Telefónica

• Se propone implementar una agenda telefónica simple utilizando cs50.h, stdio.h, y string.h.

• Se crean arreglos para almacenar nombres y números telefónicos, destacando que los números deben ser tratados como cadenas para evitar problemas con el desbordamiento.

• Los números telefónicos se almacenan como cadenas para incluir caracteres especiales como "+" y "-", evitando así complicaciones con enteros.

• Se solicita al usuario un nombre para buscar en la agenda; se utiliza un bucle para iterar sobre los nombres almacenados.

Implementación de un Directorio Telefónico

Introducción a la Búsqueda en el Directorio

• Se realiza una búsqueda en un directorio telefónico, encontrando números para varios nombres como Carter, David y John. Sin embargo, Eli no se encuentra en el sistema.

Observaciones sobre el Almacenamiento de Datos

• Se plantea la pregunta sobre si hay algo que no parece correcto en cómo se están almacenando los datos del directorio (nombres y números).

• Un miembro de la audiencia señala que separar nombres y números puede ser problemático.

Problemas con el Diseño Actual

• El presentador menciona "code smell", un término técnico que indica que algo no está bien diseñado. La separación de nombres y números podría llevar a inconsistencias.

• Se sugiere que cualquier indicio de problemas en el código es una oportunidad para mejorarlo.

Introducción a las Estructuras de Datos

• Se introduce la idea de estructuras de datos más complejas, mencionando que los arrays son solo una forma básica.

• Propone crear un nuevo tipo de dato llamado "persona" para almacenar tanto el nombre como el número juntos.

Creación de una Nueva Estructura

• Se explica cómo usar struct para definir una nueva estructura que contenga múltiples variables (nombre y número).

• El uso del comando typedef permite definir nuevos tipos de datos personalizados, facilitando la creación del tipo "persona".

Implementación Práctica del Nuevo Tipo

• El presentador describe cómo mejorar el código utilizando la nueva estructura definida. Ahora se crea un array llamado "people" con espacio para tres personas.

Introducción a la Estructura de Datos y Búsqueda en un Libro de Teléfonos

Modificación del Código para Buscar Nombres

• Se discute cómo modificar el código para buscar el nombre de una persona utilizando un índice i, accediendo al nombre a través de people[i].name.

• El enfoque actual permite verificar el nombre ingresado por el usuario, aunque se menciona que este método no es ideal para crear un libro de teléfonos a largo plazo.

Ejecución y Resultados del Libro de Teléfonos

• Se realiza una búsqueda en el libro de teléfonos, encontrando correctamente los números asociados a "Carter", "David" y "John".

• Se intenta buscar un nombre inexistente, "Eli", confirmando que no se encuentra en la base de datos.

Creación y Uso de Tipos de Datos Personalizados

• Se introduce el uso del tipo struct para agrupar datos relacionados (nombre y número), junto con typedef para asignar un nuevo nombre al tipo.

• Se aclara que es posible crear una persona sin asignar ambos valores, pero esto puede resultar en valores basura que podrían causar errores más adelante.

Consideraciones sobre Ordenamiento y Eficiencia

• La discusión se centra en la necesidad de ordenar datos antes de realizar búsquedas eficientes, planteando preguntas sobre los costos asociados con mantener datos ordenados.

• Se plantea la cuestión del costo temporal y financiero relacionado con algoritmos utilizados por grandes empresas como Google o Microsoft para mantener sus bases de datos ordenadas.

Demostración Práctica: Ordenamiento

• Se presenta un conjunto desordenado de números enteros como ejemplo práctico, destacando la importancia del ordenamiento.

Introducción a la programación y algoritmos de ordenamiento

Presentación de los estudiantes

• Un estudiante se presenta como primer año en Canadá, aún decidiendo qué estudiar.

• Otro estudiante planea concentrarse en economía y ciencias de la computación (CS).

• Un tercer estudiante menciona su interés en CS y lingüística.

Actividad de ordenamiento

• David Malan pide a los estudiantes que se organicen de menor a mayor, lo que inicia una actividad práctica.

• Los estudiantes describen sus métodos para ordenar, mencionando que buscaron números más bajos o altos para posicionarse correctamente.

Reflexiones sobre el proceso

• Malan observa que el método utilizado por los estudiantes fue orgánico pero difícil de traducir a código.

• Propone un enfoque más metódico para el ordenamiento, sugiriendo que esto facilitará la codificación.

Importancia del enfoque sistemático

• Se discute cómo un enfoque sistemático es crucial cuando hay grandes cantidades de datos (80 o 800 elementos).

• Malan explica que no puede ver todos los números al mismo tiempo, lo cual limita su capacidad para encontrar el número más pequeño rápidamente.

Ejemplo práctico del algoritmo

• Describe cómo debe revisar cada número secuencialmente para identificar el más pequeño.

• Menciona la importancia de recordar cuál es el número más pequeño encontrado hasta ese momento mientras revisa otros números.

Proceso iterativo y optimización

• Una vez identificado un número menor, se realiza un intercambio con otro elemento en la lista.

• Explica cómo este proceso permite reducir gradualmente el problema al seleccionar números uno por uno hasta completar el ordenamiento.

Conclusión sobre la implementación del algoritmo

Algoritmos de Ordenamiento: Selección y Enfoques Locales

Introducción a la Ordenación

• Se inicia una demostración de ordenamiento con el conjunto de números 72541603, donde se busca corregir el orden mediante intercambios locales.

• Se realizan múltiples intercambios entre números adyacentes para mejorar la situación del orden, aunque aún no está completamente ordenado.

Proceso Iterativo de Ordenamiento

• A medida que se realizan más intercambios, algunos números comienzan a ubicarse en su posición correcta, lo que permite avanzar en el proceso.

• La repetición del proceso muestra cómo los elementos se van colocando correctamente tras cada iteración, destacando la mejora continua.

Formalización del Algoritmo

• Se propone formalizar el algoritmo utilizado durante la demostración, contrastando dos enfoques diferentes: selección del elemento más pequeño y corrección de problemas locales.

• El primer enfoque es conocido como "selection sort", donde se selecciona repetidamente el elemento más pequeño hasta ordenar completamente la lista.

Detalles Técnicos del Selection Sort

• El algoritmo "selection sort" implica buscar el número más pequeño en una lista desordenada y colocarlo al principio. Este proceso se repite para los siguientes elementos.

• Se menciona que este método requiere un uso limitado de memoria, ya que solo se necesita recordar un número a la vez durante las iteraciones.

Visualización y Comprensión del Algoritmo

• Se presenta un pseudocódigo para ilustrar cómo funciona "selection sort", utilizando índices para recorrer los elementos desde el inicio hasta el final.

Análisis del Algoritmo de Selección

Proceso de Ordenamiento

• El algoritmo busca el elemento más pequeño y lo coloca en la posición más a la izquierda, desplazando los elementos existentes. Este proceso se repite para ordenar la lista de izquierda a derecha.

• Se menciona que el algoritmo parece lento debido a su naturaleza cíclica, realizando muchas comparaciones repetitivas entre los elementos.

Eficiencia del Algoritmo

• La ineficiencia proviene de recordar solo un elemento a la vez, lo que obliga al algoritmo a realizar múltiples comparaciones en cada pasada.

• Para n números, las comparaciones iniciales son n - 1. En cada pasada subsiguiente, se reduce el número de comparaciones necesarias (n - 2, n - 3,...).

Cálculo Matemático

• La suma total de las comparaciones puede expresarse como: n - 1 + n - 2 + ... hasta llegar al último elemento. Esto se traduce matemáticamente en (n * (n - 1)) / 2.

• Al expandir esta fórmula, se obtiene una complejidad temporal aproximada de O(n²), donde el término dominante es n².

Comparación con Otros Algoritmos

• A medida que n aumenta (por ejemplo, 80 o más), el impacto del término cuadrático crece significativamente en comparación con otros términos menores.

• Se concluye que el algoritmo de selección tiene una complejidad temporal O(n²), lo que indica que es relativamente lento para listas grandes.

Escenarios Óptimos y Condiciones

• Aunque podría haber un caso óptimo si la lista ya está ordenada, el algoritmo no tiene condiciones especiales para detectar esto y sigue ejecutándose completamente.

• No hay ninguna lógica dentro del pseudocódigo del algoritmo que permita salir anticipadamente si los elementos están ordenados; por lo tanto, siempre opera bajo O(n²).

Conclusiones sobre Complejidad

• La estructura del bucle implica hacer algo n veces dentro de otro bucle también iterado n veces, resultando nuevamente en O(n²).

Análisis del Algoritmo Bubble Sort

Introducción al Bubble Sort

• Se menciona que el algoritmo bubble sort tiene una complejidad de O(n²), lo que implica que se requieren n² pasos o comparaciones para ordenar un conjunto de datos.

Funcionamiento del Bubble Sort

• El proceso de bubble sort se describe como un método donde los números "burbujearán" hacia la derecha, con los valores más grandes moviéndose al final de la lista a través de repetidas comparaciones.

Comparación y Swaps

• Durante el análisis, se explica cómo el algoritmo compara elementos adyacentes y realiza intercambios (swaps) si están desordenados. Este proceso se repite hasta que todos los elementos estén en orden.

Pseudocódigo del Bubble Sort

• El pseudocódigo sugiere repetir el proceso n veces, iterando desde 0 hasta n - 2 para evitar salir del límite del arreglo. Esto asegura que no se intente acceder a un índice fuera de rango.

Complejidad Temporal Detallada

• La complejidad temporal se analiza más a fondo, explicando que aunque inicialmente parece ser O(n²), puede optimizarse considerando que el último elemento ya está en su lugar después de cada pasada.

Optimización Potencial

• Se discute la posibilidad de abortar el algoritmo anticipadamente si no hay swaps durante una pasada completa, indicando que la lista ya está ordenada. Esto podría reducir significativamente el número total de pasadas necesarias.

Conclusiones sobre Eficiencia

¿Cómo se determina si una lista está ordenada?

Análisis de algoritmos y ordenación

• La pregunta sobre si una lista está ordenada no puede resolverse en un solo paso si hay n elementos, ya que sería simplemente adivinar. Es necesario revisar cada elemento para llegar a una conclusión lógica.

• Se establece que el tiempo mínimo requerido es Ω(n), ya que no se puede determinar la ordenación sin verificar todos los elementos. El tiempo constante no permite revisar toda la lista.

• Aunque tanto el bubble sort como el selection sort son ineficientes en el peor de los casos, el bubble sort podría ser más rápido en el mejor de los casos debido a su condición de intercambio.

Visualización del Bubble Sort

• En la demostración visual del bubble sort, las comparaciones se realizan entre elementos adyacentes, lo que ilustra cómo los elementos más grandes "suben" al final de la lista.

• A pesar de las mejoras visibles durante el proceso, se observa que este método sigue siendo lento debido a la cantidad repetida de comparaciones necesarias.

Eficiencia y escalabilidad

• Ambos métodos (bubble sort y selection sort) son considerados ineficientes para listas grandes; con n² operaciones, su rendimiento disminuye drásticamente con un aumento en la cantidad de datos.

• Se plantea la necesidad de introducir técnicas más eficientes para resolver problemas, sugiriendo que se explore el concepto de recursión como solución alternativa.

¿Qué es la recursión?

Definición y aplicación

• La recursión implica que una función se llama a sí misma. Este enfoque ha sido utilizado previamente en ejemplos como la búsqueda binaria, donde cada llamada reduce el tamaño del problema a la mitad.

• Aunque llamar a una función recursivamente podría llevar a un bucle infinito, existe un caso base que evita esto al finalizar cuando no quedan más elementos por procesar.

Ejemplo práctico: Búsqueda en directorios

• En ejemplos previos como buscar en una agenda telefónica, se utilizó un enfoque iterativo. Sin embargo, ahora se presenta cómo simplificarlo mediante recursión dividiendo continuamente el problema hasta encontrar lo deseado.

¿Cómo se define recursivamente una pirámide?

Introducción a la Recursividad en Estructuras

• Se presenta el concepto de estructuras físicas y su relación con el pseudocódigo, utilizando bloques que evocan elementos de Mario y Super Mario Brothers. La pirámide es un ejemplo de estructura recursiva.

• Se plantea la pregunta sobre qué constituye una pirámide de altura 4, sugiriendo que puede definirse como una pirámide de altura 3 más una fila adicional.

• El proceso continúa desglosando la definición: cada nivel inferior (altura 3, 2, etc.) se construye sumando filas hasta llegar a la base, que es simplemente un ladrillo.

Implementación del Código Iterativo

• Se introduce el concepto de iteración en programación. Se menciona cómo implementar un ejemplo clásico en C para dibujar una pirámide mediante bucles.

• En el código, se solicita al usuario la altura de la pirámide y se define una función draw que no devuelve valores pero imprime los ladrillos en pantalla.

• La lógica del bucle externo itera sobre cada fila desde arriba hacia abajo, mientras que el bucle interno controla cuántos hashes imprimir por fila.

Ejecución y Resultados

• Al compilar y ejecutar el código con diferentes alturas (ejemplo: 4), se observa cómo se forma visualmente la pirámide en pantalla.

• Se prueba con alturas mayores (10 y 50), demostrando que el enfoque iterativo funciona correctamente aunque las dimensiones pueden no ser proporcionales.

Transición a Recursión

• A continuación, se propone reescribir el programa utilizando recursión para simplificar aún más la solución.

Introducción a la Recursión en C

Errores de Recursión

• El código presentado genera un error en Clang, indicando que todas las rutas de la función llamarán a sí mismas. Esto resalta el problema de una recursión infinita si no se maneja adecuadamente.

• Se menciona que los enteros son firmados por defecto, lo que significa que pueden ser positivos, cero o negativos. La resta continua sin control puede llevar a un desbordamiento.

Caso Base en Recursión

• Para evitar la recursión infinita, se establece un caso base: si n es menor o igual a 0, la función debe retornar sin hacer nada. Este es un paso crucial para prevenir llamadas negativas.

• Se compara este caso base con situaciones cotidianas como "si John Harvard no está en la guía telefónica", enfatizando su importancia para detener la recursión.

Ejecución y Resultados

• Al compilar y ejecutar el código corregido, se obtienen resultados esperados al imprimir estructuras repetitivas basadas en el valor de n, mostrando que funciona correctamente hasta valores altos como 5,000.

• Sin embargo, se advierte sobre posibles problemas al intentar valores extremadamente altos (como 500,000), sugiriendo que aunque funcione bien ahora, podría volverse lento o problemático.

Concepto de Recursión

• Se introduce el concepto de recursión como una técnica poderosa para resolver problemas y optimizar el código. Permite escribir menos líneas mientras se utiliza la memoria del ordenador de manera eficiente.

Algoritmo Merge Sort

• Se presenta el algoritmo Merge Sort como una alternativa más eficiente a otros métodos de ordenación (como Selection Sort y Bubble Sort), buscando mejorar la complejidad temporal del algoritmo.

• El pseudocódigo para Merge Sort implica dividir un conjunto de números en mitades izquierda y derecha, ordenarlas por separado y luego fusionar las mitades ordenadas.

Proceso de Fusión

Introducción a la Fusión de Listas Ordenadas

Concepto de Fusión

• Se explica cómo fusionar dos listas ordenadas, eligiendo el siguiente número de una u otra lista.

• Se menciona que se utilizará un enfoque digital para representar las listas en lugar de números físicos.

Limitaciones de Algoritmos Anteriores

• Se discute cómo los algoritmos como selección y burbuja limitan el uso de memoria, utilizando solo una variable para rastrear elementos.

• Se introduce la idea de intercambiar recursos: más espacio puede reducir el tiempo necesario para resolver problemas.

Evaluación del Algoritmo Merge Sort

Comparación con Otros Algoritmos

• Se plantea la necesidad de evaluar si merge sort es mejor que selección y burbuja, ambos con complejidad O(n²).

• La estrategia se basa en dividir y conquistar, comenzando por ordenar la mitad izquierda del arreglo.

Pasos Clave del Algoritmo

• Los pasos fundamentales son: ordenar la mitad izquierda, ordenar la mitad derecha y fusionar ambas mitades ordenadas.

Proceso Detallado de Ordenamiento

Ordenando Mitades

• Al trabajar con un arreglo original, se comienza a ordenar la mitad izquierda usando un enfoque recursivo.

• Para un arreglo pequeño (de tamaño 4), se aplican los mismos tres pasos: ordenar mitades y fusionar.

Casos Base en Recursión

• Un caso base es cuando se encuentra una lista de tamaño 1; ya está ordenada por defecto.

Fusión Final

Combinación de Resultados Parciales

• Después de ordenar las mitades individuales (3 y 6), se realiza la fusión para obtener una lista ordenada (1, 3, 4, 6).

Continuación del Proceso

Proceso de Ordenamiento con Merge Sort

Introducción al Merge Sort

• Se ha completado la ordenación de la mitad izquierda y derecha, y ahora se están fusionando los resultados. El proceso implica combinar listas ordenadas para obtener una lista final ordenada.

• La fusión parece mágica, ya que el algoritmo no realiza muchas operaciones en las hojas individuales; es en la fusión donde ocurre la verdadera magia del ordenamiento.

Recursión y Eficiencia

• El algoritmo no repite acciones innecesariamente; cada número se corrige una vez antes de pasar al siguiente. Esto es fundamental para entender cómo funciona el merge sort.

• Aunque el algoritmo utiliza más espacio (hasta tres estantes), se puede optimizar utilizando solo dos estantes, lo que reduce el uso de memoria sin perder eficiencia.

Comparación de Velocidades

• A medida que las mitades se fusionan, el proceso es notablemente más rápido. Esto contrasta con otros métodos como bubble sort, que son menos eficientes.

• Se realizó un análisis del trabajo realizado durante el proceso: 24 movimientos fueron necesarios para completar la tarea de ordenamiento.

Análisis Matemático del Algoritmo

• Al dividir repetidamente una lista (log base 2), se determina cuántas veces se puede dividir un problema. Para una lista de tamaño 8, esto resulta en log base 2 de 8 = 3.

• Cada división requiere pasos adicionales para fusionar los números nuevamente. Por lo tanto, hay n pasos por cada nivel de división.

Complejidad Temporal

• La complejidad total del tiempo de ejecución es n log n. Esto significa que merge sort es más eficiente que algoritmos cuadráticos como bubble sort o selection sort.

• Aunque merge sort tiene un rendimiento superior en general, puede ser superado por bubble sort en casos específicos donde los datos ya están parcialmente ordenados.

Conclusiones sobre Merge Sort