[Powered by Google Translate] [Merge Sort] [Rob Bowden - Harvard University] [Esta es CS50. - CS50.TV] Hablemos de tipo de mezcla. Hasta ahora hemos visto especie de burbuja, ordenación por inserción, y una especie de selección. Aunque Voy tipo de onda mi mano en lo que quiero decir mejor, merge sort generalmente funciona mejor que cualquiera de estos tres tipos. Pero antes de hablar de tipo de mezcla, vamos a hablar de la fusión de dos listas ordenadas. Lo llamaremos el proceso de tomar 2 listas ordenadas, como estos, y hacer una única lista ordenada de ellos - la fusión de las listas. ¿Cómo podemos hacer esto? Bueno, una idea es seguir una sola lista en el extremo de la otra lista y luego ordenar la lista de resultados. Si bien esto funciona, es una gran cantidad de trabajo innecesario. Podemos hacerlo más rápido que un simple clasificación. Tenga en cuenta que una idea equivocada es simplemente tomar copas alternados de cada lista. Si bien esto puede parecer que funciona al principio, haciendo que nos encontramos con 4, 8, 15, 23, 16 - Anuncio de que el 16 y 23 están fuera de lugar. Esto se debe a dos elementos que deben aparecer consecutivo en la lista resultante de la fusión están en la lista inicial igual. Tanto el 15 y 16 están en la lista de la izquierda. El truco consiste en aprovechar el hecho de que las dos listas ya están ordenados. Esto significa que si nos fijamos en los primeros elementos de ambas listas - aquí, 4 y 8 - uno de ellos debe ser también el primer elemento de la lista combinada. Bueno, ¿por qué es eso? Ambas listas ya están ordenados, y por lo tanto ya sea de 4 u 8 debe ser el elemento más pequeño cuando combinamos las dos listas. En este caso, el más pequeño es 4, por lo que podemos sacar 4 y convertirlo en el primer elemento de la lista combinada. Ahora continuamos la fusión de los 3 restantes elementos de la primera lista y 4 elementos de la segunda lista. Una vez más, sólo tenemos que mirar el primer elemento de ambas listas. El menor de los 2 debe ser el segundo elemento de la lista combinada. Esta vez, entre el 8 y el 15 el más pequeño es de 8, por lo que insertar ese como el segundo elemento de la lista ordenada. Podemos seguir comparando los primeros elementos de ambas listas y la eliminación de la menor de las 2. Comparando los 15 y 23 15, es más pequeño y por lo tanto ese es nuestro tercer elemento. Ahora comparando 16 y 23, 16 es más pequeño. Así que ese es el cuarto elemento. Tenga en cuenta que dos elementos provenían de la misma lista en una fila. Por ello, la lista resultante de la fusión no puede simplemente elementos alternativos a partir de las 2 listas. Comparando los 50 y 23, 23 es más pequeño, así que elegimos eso. Entre 50 y 42, 42 es más pequeño. Entre 50 y 108, 50 es más pequeño. Y, por último, sólo tenemos 108, por lo que debe ir en el final de nuestra lista. Tenga en cuenta que tenemos una buena lista, ordenada. Cada vez que se compararon los primero 2 elementos de las listas 2 hemos sido capaces de determinar el siguiente elemento de la lista combinada. Esto significa que si la lista final contiene un número n, donde n es aquí 8, entonces tenemos que en la mayoría de las comparaciones n para obtener todos los números en el lugar correcto. Tal algoritmo se dice que se ejecutan en tiempo lineal, pero no te preocupes por eso aquí. Usando nuestro algoritmo para la fusión, podemos hacer un rápido algoritmo de combinación tipo. Por lo tanto, vamos a restablecer nuestras listas. Hay 2 grandes pasos en el proceso de la especie de mezcla. En primer lugar, continuamente dividir la lista de copas en dos mitades hasta que tengamos un montón de listas con sólo 1 taza en ellas. No te preocupes si una lista contiene un número impar y no se puede hacer un corte perfectamente limpio entre ellos. Sólo arbitrariamente escoger cuál desea incluir la taza extra cm Por lo tanto, vamos a dividir estas listas. Ahora tenemos 2 listas. Ahora tenemos 4 listas. Y ahora tenemos 8 listas con una sola taza en cada lista. Así que eso es todo por el paso 1. Para el paso 2, repetidamente mezcla pares de listas usando el algoritmo de fusión que hemos aprendido antes. La fusión de 108 y 15, nos encontramos con la lista de 15, 108. La fusión de 50 y 4, nos encontramos con 4, 50. La fusión de 8 y 42, terminamos con 8, 42. Y la fusión de 23 y 16, terminamos con 16, 23. Ahora todas nuestras listas son de tamaño 2. Observe que cada una de las 4 listas está ordenada. Así que podemos comenzar la fusión de pares de listas de nuevo. La fusión de 15 y 108 y 4 y 50 - primero tomar la 4, a continuación, la 15, la 50, entonces el 108. La fusión de 8, 42 y 16, 23, en primer lugar asumir el 8, el 16, luego el 23, luego el 42. Así que ahora tenemos sólo 2 listas de tamaño 4, cada uno de los cuales está ordenada. Así que ahora nos fusionamos estas dos listas. En primer lugar, tomar la 4. Luego tomamos el 8. Entonces se toma el 15 y el 16, y luego 23, luego 42, luego 50, luego 108. Y hemos terminado. Ahora tenemos una lista ordenada. Así lo rápido que era eso, exactamente? En términos técnicos, una especie de combinación es O (n log n), mientras que todos los de tipo burbuja, ordenación por inserción, y una especie de selección son O (n ²). De hecho, como usted aprenderá pronto, usted no será capaz de llegar a una especie que se comporta mejor que O (n log n) en el caso general. Una vez más, no se preocupe por esta notación grande O si usted no lo ha visto todavía. Solo que sepas que esto significa que si queríamos ordenar una lista muy grande especie tipo burbuja, ordenación por inserción, y la selección podría tomar significativamente más largo que merge sort. Esto no significa que ese tipo de mezcla será más rápido para todas las listas o incluso para cualquier lista única bajo un cierto tamaño. Por ejemplo, el tipo de inserción puede ser el más rápido de clasificación de todas las listas de menores de 5 elementos. En la práctica, una especie de combinación es generalmente más rápido para las listas de tan sólo 50 elementos. Sin embargo, esta velocidad extra no viene sin un precio. A diferencia de nuestros otros géneros, que tienen una lista y modificar la lista en su sitio hasta que tengamos una lista ordenada, una especie de mezcla necesita un poco de espacio adicional para fusionar 2 listas. No se puede usar inmediatamente las listas que se fusionaron para almacenar la lista resultante de la fusión ya que pueden anular los elementos que aún deben ser combinadas. Este espacio es un poco de un precio, pero por lo general no es irrazonable. Y eso es todo por tipo de mezcla. Mi nombre es Rob Bowden, y esto es CS50. [CS50.TV] - Selección y ordenación. [Risas] Oh, tengo que tomar eso también porque me cambié cómo lo estaba presentando. Lista de la izquierda. Eso fue un error. [Equivocó al hablar] Cometí un error - [Risas] No sé por qué -