Merge Sort Paso a Paso: Pseudocódigo y coste - Tema 1 DA

Aprende cómo funciona Merge Sort, el algoritmo de ordenación por mezcla, desde la idea de dividir y vencerás hasta su pseudocódigo y su coste O(n log n). Seguimos las llamadas recursivas y la fusión de dos vectores ordenados con trazas concretas. Después calculamos el trabajo con una recurrencia y con el árbol de recursión, prestando atención a las guardas que evitan leer fuera del vector. EN ESTA CLASE • Separar las tres fases de divide y vencerás: dividir, resolver y combinar. • Leer MergeSort y Merge línea a línea. • Seguir los índices de ambas mitades y reconocer cuándo una se agota. • Distinguir corrección del algoritmo y tiempo de ejecución. • Obtener el coste lineal de Merge y construir la recurrencia de MergeSort. • Sumar el trabajo por niveles y entender de dónde aparece el logaritmo. CAPÍTULOS 00:00 Ordenar ocho números o millones 00:37 Ruta del curso y problemas de diseño 03:55 Dividir, resolver y combinar 04:40 El problema de ordenar 05:13 Por qué mezclar dos mitades ordenadas 06:45 Cómo leer el pseudocódigo 08:38 Caso base y llamadas recursivas 09:48 Traza de MergeSort 11:26 Merge: los tres índices 13:16 Leer la fusión paso a paso 14:48 Traza y agotamiento de una mitad 16:22 Corrección y tiempo de ejecución 18:08 El error de leer fuera del vector 18:50 Por qué Merge tiene coste lineal 19:39 Logaritmos y coste de MergeSort 20:23 Construir y desplegar la recurrencia 22:53 Árbol de recursión y trabajo por nivel 27:07 Peor caso y términos dominantes 29:33 Ejercicios: traza de Merge y MergeSort 31:14 Comprobar fusiones y coste con un tamaño pequeño PARA SEGUIR LA CLASE Punto de partida de la serie. Ayuda reconocer variables, condiciones, bucles y vectores; la clase explica la notación de pseudocódigo que utiliza. Pausa los ejercicios y escribe tu solución antes de continuar. Continúa con el Tema 2, parte A: notación asintótica y comparación del crecimiento de funciones. Serie: Diseño de Algoritmos (Disseny d'Algorismes) · Tema 1. Narración en español. Material de estudio independiente. Guarda la clase para repasar. Si tienes una duda, deja el minuto y el paso que quieres aclarar. #Algoritmos #MergeSort #Programacion