>> [REPRODUCCIÓN DE MÚSICA]
>> DOUG LLOYD: OK, por lo que una fusión especie es otro algoritmo
que podemos utilizar para solucionar los elementos de una matriz.
Pero como veremos, tiene un diferencia muy fundamental
desde la selección del tipo, burbuja ordenar y ordenación por inserción
que hacen que sea realmente muy inteligente.
>> La idea básica detrás de la fusión clase es para ordenar arrays más pequeños
y luego combinar los arrays juntos, o fusionar ellos--
de ahí el nombre-- en forma ordenada.
La forma en que se funden especie hace esto es mediante el aprovechamiento de una herramienta
llama recursividad, que es lo que vamos a estar hablando de pronto,
pero en realidad no hemos hablado todavía.
>> Esta es la idea básica detrás de mezcla tipo.
Ordene la mitad izquierda de la matriz, suponiendo que n es mayor que 1.
Y lo que quiero decir cuando digo suponiendo que n es mayor que 1, es decir,
Creo que podemos estar de acuerdo que si una matriz sólo se compone de un único elemento,
se arregló.
En realidad no necesitamos que hacer nada para él.
Sólo podemos declararlo a clasificar.
No es más que un solo elemento.
>> Así que el pseudocódigo, de nuevo, es ordenar la mitad izquierda de la matriz,
a continuación, ordenar la mitad derecha de la matriz, luego fusionar las dos mitades.
Ahora, ya que podría ser pensar, es como que acaba de
suena como usted está poniendo fuera el-- usted no está realmente haciendo nada.
¿Estás diciendo que ordenar la izquierda medio, más o menos la mitad derecha,
pero no se está diciendo mí cómo lo estás haciendo.
>> Pero recuerde que mientras una matriz es un solo elemento,
podemos declarar lo arregló.
Entonces sólo podemos combinarlos.
Y eso es en realidad el idea fundamental detrás de combinación de clase,
es romper hacia abajo para que las matrices son de talla única.
Y luego vuelve a generar a partir de ahí.
>> Merge Sort es definitivamente un algoritmo complicado.
Y también es un poco complicado de visualizar.
Así que es de esperar, la visualización que tiene aquí le ayudará a lo sigue.
Y voy a intentar mi mejor esfuerzo para narrar las cosas y proceder a través de esto un poco más
lentamente que los demás sólo para obtener espero tu cabeza
alrededor de las ideas detrás de mezcla tipo.
>> Así que tenemos la misma matriz como la otros vídeos del algoritmo de clasificación
ellos-- si has visto una matriz de seis elementos.
Y nuestro código pseudocódigo aquí es una especie la mitad izquierda, ordenar la mitad derecha,
fusionar las dos mitades juntas.
Así que tomemos este ladrillo rojo muy oscuro matriz y ordenar el medio que queda de ella.
>> Así que por el momento, vamos hacer caso omiso de las cosas a la derecha.
Está ahí, pero estamos no en ese paso todavía.
No estamos en la clase media derecha de la matriz.
Estamos en una especie de la izquierda medio de la matriz.
Y sólo por el bien de ser un poco más
claro, así que me puedo referir a lo que el paso que estamos en,
Voy a cambiar la color de este conjunto de naranja.
Ahora, todavía estamos hablando de la misma mitad izquierda de la matriz original.
Pero espero que al ser capaces de referirse a los colores de diversos artículos,
que va a hacer un poco más aclarar lo que está pasando aquí.
>> OK, así que ahora tenemos una de tres conjunto de elementos.
¿Cómo ordenar la media izquierda de esta array, que sigue siendo este paso?
Estamos tratando de ordenar la izquierda medio del array-- ladrillo rojo
la mitad izquierda de los cuales Ahora he de color naranja.
>> Bueno, podríamos tratar de repetir este proceso otra vez.
Así que todavía estamos en el medio de tratar de clasificar
la mitad izquierda de la matriz completa.
La mitad izquierda de la matriz, sólo voy
para decidir arbitrariamente que la mitad izquierda será menor que la mitad derecha,
porque esto le sucede a constará de tres elementos.
>> Y por lo que voy a decir que la media izquierda de la mitad izquierda de la matriz
es sólo el elemento de cinco.
Five, siendo un solo elemento matriz, sabemos cómo arreglarlo.
Y así, de cinco se ordena.
Sólo vamos a declarar eso.
Es un solo elemento de la matriz.
>> Así que ahora hemos solucionaron el mitad izquierda de la izquierda half--
o más bien, hemos solucionaron el mitad izquierda de la naranja.
Así que ahora, con el fin de todavía completa mitad izquierda de la matriz global,
tenemos que ordenar la mitad derecha de la naranja, o estas cosas.
¿Cómo lo hacemos?
Bueno, tenemos una matriz de dos elementos.
Así que podemos ordenar la media izquierda de la matriz, que es de dos.
Dos es un solo elemento.
Así que ha ordenado de forma predeterminada. Entonces podemos ordenar la mitad derecha
de esa porción de la matriz, el uno.
Eso es una especie de forma predeterminada.
>> Esta es ahora la primera vez hemos llegado a una etapa de mezcla.
Hemos completado, aunque ahora estamos tipo de anidado down--
y eso es una especie de la difícil cosa con la recursividad es,
usted necesita para mantener su cabeza acerca de dónde estamos.
Para ello hemos especie de la izquierda medio de la porción de naranja.
>> Y ahora, estamos en el medio de la clasificación la mitad derecha de la parte naranja.
Y en ese proceso, estamos ahora a punto de estar en el paso,
fusionar las dos mitades juntas.
Cuando nos fijamos en las dos mitades de la matriz, vemos dos y uno.
¿Qué elemento es menor?
Uno.
>> Entonces qué elemento es más pequeño?
Bueno, es dos o nada.
Así que es dos.
Así que ahora, sólo para enmarcar de nuevo donde estamos en contexto,
hemos ordenado la mitad izquierda de la naranja
y la mitad derecha del origen.
Sé que he cambiado los colores de nuevo, pero eso es donde estábamos.
Y la razón por la que hizo esto es porque este proceso es
va a seguir adelante, iterando hacia abajo.
Hemos solucionaron la izquierda la mitad de la antigua naranja
y la mitad derecha de la antigua naranja.
>> Ahora, tenemos que combinar los dos mitades también.
Ese es el paso que estamos en.
Así tenemos en cuenta la totalidad de la elementos que ahora son de color verde,
la mitad izquierda de la matriz original.
Y nos fusionamos los utilizando el mismo proceso
lo hicimos para la fusión de dos y hace un un momento.
>> La mitad izquierda, la más pequeña elemento en la mitad izquierda es de cinco.
El componente más pequeño de la mitad derecha es uno.
¿Cuál de ellos es más pequeño?
Uno.
>> El componente más pequeño de la mitad izquierda es de cinco.
El componente más pequeño de la mitad derecha es de dos.
¿Cuál es el más pequeño?
Dos.
Y luego, por último, cinco y nada, podemos decir cinco.
>> OK, la imagen tan grande, vamos a tomar un descanso por un segundo
y averiguar dónde estamos.
Si partimos de el principio, nos
ahora se han completado para la matriz global justo
un paso del código pseudocódigo aquí.
Hemos ordenado la media izquierda de la matriz.
>> Recordemos que el original orden era de cinco, dos, uno.
Al pasar por este proceso y anidando abajo y repetir,
continua para romper el problema en partes cada vez más pequeñas,
ahora hemos completado paso uno del pseudocódigo
para toda la matriz de partida.
Hemos ordenado su mitad izquierda.
>> Así que ahora vamos a congelar allí.
Y ahora vamos a ordenar la derecha la mitad de la matriz original.
Y vamos a hacer eso por pasando por el mismo iterativo
proceso de romper las cosas y luego fusionarlos juntos.
>> Así que la mitad izquierda de la rojo, o la mitad izquierda
de la mitad derecha del original matriz, que voy a decir es tres.
Una vez más, estoy siendo coherente aquí.
Si usted tiene un extraño número de elementos,
en realidad no importa si a tomar el de la izquierda más pequeña
o el derecho de un menor.
>> Lo que importa es que cada vez que encontrar este problema en la realización de
una fusión, tiene que ser coherente.
Usted bien siempre hay que hacer un lado izquierdo más pequeño
o siempre que tenga que hacer el lado derecho más pequeño.
Aquí, he optado por siempre hacer que el lado izquierdo más pequeño
cuando mi matriz, o de mi sub-matriz, es de un tamaño impar.
>> Tres es un solo elemento, y por lo que se ordena.
Hemos aprovechado esa suposición lo largo de todo nuestro proceso hasta el momento.
Así que ahora vamos a ordenar la derecha la mitad de la mitad derecha,
o la mitad derecha de la roja.
>> Una vez más, tenemos que dividir esto.
Esto no es un único elemento de la matriz.
No podemos declarar lo arregló.
Y así, en primer lugar, vamos para ordenar la mitad izquierda.
>> La mitad izquierda es un solo elemento, por lo que es una especie de forma predeterminada.
Entonces vamos a ordenar la derecha medio, que es un solo elemento.
Está ordenada por defecto. Y ahora, podemos combinar los dos juntos.
Cuatro es más pequeño, y a continuación, seis es más pequeño.
>> Una vez más, ¿qué hemos hecho en este punto?
Hemos solucionaron la izquierda la mitad de la mitad derecha.
O volver a la original colores que estaban allí,
hemos solucionaron la izquierda medio del rojo más suave.
Originalmente fue un ladrillo oscuro rojo y ahora es un rojo más suave,
o que era un rojo más suave.
>> Y luego hemos solucionaron el mitad derecha del rojo más suave.
Ahora, bien, son verdes de nuevo, sólo porque vamos a través de un proceso.
Y tenemos que repetir esto una y otra.
>> Así que ahora podemos combinar los dos mitades.
Y eso es lo que hacemos aquí.
Así que la línea de negro solo dividido a la mitad izquierda
y la mitad derecha de esta parte de clasificación.
>> Comparamos el valor más pequeño en el lado izquierdo de la array--
o perdón, la más pequeña valor de la mitad izquierda
al valor más pequeño de la derecha medio y encontrar que tres es más pequeño.
Y ahora un poco de una optimización, ¿verdad?
En realidad hay nada a la izquierda en el lado izquierdo.
>> No hay nada restante En el lado izquierdo,
para que podamos de manera eficiente simplemente move-- podemos declarar
el resto de él es en realidad ordenado y justo virar
en adelante, porque no hay nada otra cosa que comparar.
Y sabemos que el lado derecho del lado derecho está ordenada.
>> OK, así que ahora vamos a congelar de nuevo y averiguar dónde estamos en la historia.
En la matriz general, ¿qué hemos logrado?
De hecho, hemos logramos ahora los pasos uno y el paso dos.
Clasificamos la mitad izquierda, y nos lo solucionaron la mitad derecha.
>> Así que ahora, todo lo que queda es para nosotros fusionar esas dos mitades.
Así comparamos el más bajo valorado elemento de cada medio de la matriz
a su vez, y proceder.
Una de ellas es inferior a tres, por lo que uno va.
>> Dos es inferior a tres, así que dos va.
Tres es inferior a 5, así que tres va.
Cuatro es inferior a 5, por lo que va de cuatro.
Luego de cinco es menos de seis, y seis es todo lo que queda.
>> Ahora, lo sé, que era un montón de pasos.
Y hemos dejado un montón de la memoria en nuestra estela.
Y eso es lo que los cuadrados grises son.
Y probablemente se sentía como que tuvo un mucho más tiempo que la ordenación por inserción, burbuja
especie, o la selección de clasificación.
>> Pero, en realidad, ya que un Muchos de estos procesos
están sucediendo al mismo tiempo-- que es algo que voy a hacer, de nuevo,
hablar cuando hablamos de recursividad en un futuro video--
este algoritmo en realidad claramente es fundamentalmente
diferente a cualquier cosa hemos visto antes
pero también es significativamente mas eficiente.
>> ¿Porque es eso?
Bueno, en el peor de los casos de los casos, tenemos
dividir n elementos arriba y luego recombinar ellos.
Pero cuando recombinarlo ellos, lo que estamos haciendo
es, básicamente, la duplicación de la tamaño de las matrices más pequeñas.
Tenemos un montón de un elemento arrays que efectivamente
combinar en dos conjuntos de elementos.
Y luego tomamos los dos conjuntos de elementos
y combinarlos en cuatro conjuntos de elementos, y así sucesivamente,
y así sucesivamente, y así sucesivamente, hasta que tener una sola n elemento de la matriz.
>> Pero, ¿cuántos duplicaciones Qué se necesita para llegar al n?
Piense de nuevo al ejemplo de la guía telefónica.
¿Cuántas veces tenemos que romper la guía telefónica en medio, ¿cuántos más
veces tenemos que romper la guía telefónica a la mitad, si el tamaño de la guía telefónica
duplicado?
Sólo hay una, ¿no?
>> Así que hay algún tipo de elemento logarítmica aquí.
Pero también queda por lo menos mirar a todos los n elementos.
Así que en el peor de los casos, ordenamiento por mezcla corre n log n.
Tenemos que mirar todos los elementos N,
y tenemos que combinarlos juntos en log n conjuntos de pasos.
En el mejor de los casos, la matriz está perfectamente ordenadas.
Eso es genial.
Pero basado en el algoritmo que tenemos aquí, todavía tenemos que dividir y recombinar.
Aunque en este caso, la recombinación es una especie de ineficaz.
No es necesario.
Pero todavía atravesamos todo el proceso de todos modos.
>> Así, en el mejor de los casos y en el peor de los casos,
este algoritmo se ejecuta en n log n tiempo.
Combinar tipo es sin duda un poco más complicado que los otros algoritmos de clasificación principales
hemos hablado de CS50 pero es sustancialmente más potente.
>> Y por lo que si alguna vez se encuentra ocasión para la necesitan
o utilizarlo para ordenar una gran conjunto de datos, consiguiendo
su cabeza alrededor de la idea de recursividad va a ser muy poderosa.
Y que va a hacer su programas realmente mucho más eficiente
utilizando fusionar especie frente nada más.
Soy Doug Lloyd.
Esto es CS50.