>> [Música tocando]
>> Doug LLOYD: OK, entón unha combinación tipo é un algoritmo
que podemos utilizar para resolver os elementos dunha matriz.
Pero, como veremos, ten un diferenza moi fundamental
de selección tipo, burbulla tipo e ordenación por inserción
que o fan realmente moi intelixente.
>> A idea básica por tras de mesclagem tipo é clasificar matrices menores
e, a continuación, combinar esas matrices xuntos, ou mesturar eles--
de aí o nome-- na orde de clasificación.
O xeito que merge sort fai é dicir, aproveitando unha ferramenta
chamado recursão, que é o que nós imos estar falando en breve,
pero nós realmente non falamos sobre iso aínda.
>> Aquí é a idea básica por tras merge sort.
Ordenar a metade esquerda da matriz, asumindo que n é maior que 1.
E o que quero dicir cando digo asumindo que n é maior que 1 é,
Creo que podemos aceptar que se unha matriz consiste soamente dun único elemento,
é clasificado.
Nós realmente non precisa para facer calquera cousa para el.
Podemos só declaralo lo para ser clasificado.
É só un único elemento.
>> Así, o pseudocódigo, de novo, é ordenar a metade á esquerda da matriz,
a continuación, clasificar a metade dereita da matriz, a continuación, mesturar as dúas metades xuntas.
Agora, xa que pode ser pensar, el tipo de só
Parece que está adiando as-- non está realmente facendo algo.
Está dicindo clasificar á esquerda metade, ordenar a metade dereita,
pero non está dicindo me como está facendo iso.
>> Pero lembre que, mentres unha matriz é un único elemento,
podemos declaralo la clasificada.
Entón podemos só combina-los xuntos.
E iso é realmente o idea fundamental detrás merge sort,
é para rompe-lo para abaixo, para que súas matrices son de tamaño un.
E entón reconstruír a partir de aí.
>> Merge sort é sempre un algoritmo complicado.
E é tamén un pouco complicada para ver.
Polo tanto, esperamos que, a visualización que temos aquí vai axudar a seguir adiante.
E eu vou probar o meu mellor para narrar as cousas e continuar con este un pouco máis
lentamente do que os outros só coa esperanza de obter a súa cabeza
en torno ás ideas detrás merge sort.
>> Polo tanto, temos a mesma matriz como a outras algoritmo de clasificación vídeos
se xa viu eles-- unha matriz de seis elementos.
E o noso código pseudocode aquí é clasificar a metade esquerda, ordenar a metade dereita,
mesturar as dúas metades xuntas.
Entón, imos dar este ladrillo vermello moi escuro array e clasificar a metade esquerda do mesmo.
>> Entón, por agora, imos a ignorar as cousas á dereita.
É alí, pero estamos non naquel paso aínda.
Non somos a especie a metade dereita da matriz.
Estamos en especie á esquerda metade da matriz.
E só por unha cuestión de ser un pouco máis
claro, para que eu poida consultar ao paso que estamos no,
Vou cambiar o cor deste conxunto de laranxa.
Agora, aínda estamos a falar sobre o mesma metade esquerda da matriz orixinal.
Pero eu estou esperando que por poder refírense ás cores de varios elementos,
vai facelo un pouco máis claro o que está a suceder aquí.
>> OK, entón agora temos un tres matriz elemento.
Como podemos clasificar a metade esquerda deste matriz, o que é aínda neste paso?
Estamos tentando clasificar á esquerda metade do ladrillo vermello array--
a metade esquerda das cales Eu teño agora de cor laranxa.
>> Ben, nós poderíamos tentar cabo este proceso de novo.
Entón, nós aínda estamos no medio tentando clasificar
a metade esquerda da matriz completa.
A metade esquerda do array, eu só vou
para decidir arbitrariamente que a metade esquerda será menor que a metade dereita,
porque isto acontece a composto por tres elementos.
>> E así eu vou dicir que o metade esquerda da metade esquerda da matriz
é só o elemento cinco.
Cinco, sendo un único elemento array, sabemos como solucionar isto.
E así cinco está clasificada.
Nós só estamos indo a declarar isto.
É unha única matriz elemento.
>> Entón, nós temos agora clasificados a metade esquerda da esquerda half--
ou mellor, temos clasificados a metade esquerda da laranxa.
Entón, agora, a fin de aínda completa metade esquerda da matriz total,
necesitamos clasificar a metade dereita da laranxa, ou esas cousas.
Como facemos isto?
Ben, temos un array con dous elementos.
Así, podemos clasificar a metade esquerda da matriz, que é dous.
Dous é un único elemento.
Polo que é clasificado por defecto. Entón, podemos clasificar a metade dereita
de que a porción de matriz, a unha.
Isto é tipo de xeito predeterminado.
>> Isto é agora por primeira vez chegamos a un paso de mesclagem.
Nós completados, aínda agora estamos tipo de aniñados down--
e que é unha especie de complicado cousa con recursividade é,
precisa para manter o seu cabeza sobre onde estamos.
Entón, nós tipo de esquerda metade da porción de laranxa.
>> E agora, estamos no medio de selección a metade dereita da porción de laranxa.
E, nese proceso, estamos agora a piques de ser no chanzo,
mesturar as dúas metades xuntas.
Cando ollamos para as dúas metades da matriz, vemos dous e un.
Elemento que é menor?
Unha.
>> A continuación, o cal elemento é menor?
Ben, é dúas ou nada.
Polo tanto, é dous.
Entón, agora, só para enmarcar novo onde estamos no contexto,
nós ter resolto o metade esquerda da laranxa
ea metade dereita da orixe.
Sei que eu mudei as cores de novo, pero que é onde estabamos.
E a razón pola que eu fixen iso é porque este proceso é
seguirá, a iteración abaixo.
Temos clasificados esquerda a metade da laranxa ex
ea metade dereita do ex laranxa.
>> Agora necesitamos mesturar os dúas metades xuntos tamén.
Esa é a etapa na que estamos.
Polo tanto, considerar todas as elementos que son agora verde,
a metade esquerda da matriz orixinal.
E nós mesturar os utilizando o mesmo proceso de
fixemos para mesturar dous e un só un momento atrás.
>> A metade da esquerda, a menor elemento na metade esquerda é cinco.
O elemento máis pequeno a metade dereita é un deles.
Cal destas é menor?
Unha.
>> O elemento máis pequeno a metade esquerda é cinco.
O elemento máis pequeno a metade dereita é dous.
Cal é o menor?
Dous.
E para rematar, a continuación, cinco e nada, podemos dicir cinco.
>> OK, polo tanto, gran figura, imos facer unha pausa por un segundo
e descubrir onde estamos.
Se começássemos desde o principio, nós
agora completou para a matriz global só
un paso do código pseudocode aquí.
Nós ter resolto o metade esquerda da matriz.
>> Lembre que o orixinal orde era cinco, dous, un.
Ao pasar por este proceso e nidificación abaixo e repetir,
continuando a romper o problema en partes cada vez máis pequenos,
temos agora rematada un paso do pseudocode
para toda a matriz de saída.
Nós resolver súa media esquerda.
>> Entón agora imos conxelar alí.
E agora imos clasificar a dereita metade da matriz orixinal.
E imos facelo por pasando pola mesma iterativo
proceso de romper as cousas e, a continuación, mesclando los xuntos.
>> Así, a metade esquerda da vermello, ou a metade esquerda
da metade dereita do orixinal array, eu vou dicir é tres.
Unha vez máis, eu estou sendo consistente aquí.
Se tes un estraño número de elementos, ela
Non importa realmente se fai o esquerdo menor
ou o dereito dun menor.
>> O importante é que sempre que atopou con este problema na condución
unha mala, ten que ser consistente.
Quere sempre ten facer un á esquerda menor
ou sempre que facer o lado dereito menor.
Aquí, eu escollín para sempre facer á esquerda menor
cando a miña matriz, ou o meu sub-array, é dunha dimensión raro.
>> Tres é un único elemento, e por iso é ordenada.
Temos aproveitado esa suposición en todo o noso proceso ata agora.
Entón agora imos clasificar a dereita metade da metade dereita,
ou a metade dereita do vermello.
>> Unha vez máis, temos que dividir isto para abaixo.
Este non é un único elemento de matriz.
Non podemos declaralo la clasificada.
E así en primeiro lugar, imos para clasificar a metade esquerda.
>> A metade da esquerda é un único elemento, polo que é tipo de xeito predeterminado.
Entón imos clasificar a dereita metade, que é un único elemento.
É clasificado por defecto. E agora, que pode mesturar os dous xuntos.
Catro é menor, e a continuación, seis é menor.
>> Unha vez máis, o que fixemos neste momento?
Temos clasificados esquerda metade da metade dereita.
Ou volver ao orixinal cores que estaban alí,
temos ordenados esquerda metade do vermello máis suave.
El foi orixinalmente un ladrillo escuro vermello e agora é un vermello máis suave,
ou un vermello foi máis suave.
>> E entón temos o clasificado metade dereita do vermello máis suave.
Agora ben, son verde de novo, só porque estamos pasando por un proceso.
E nós temos que repetir iso máis e máis.
>> Entón agora podemos mesturar os dúas metades xuntas.
E iso é o que facemos aquí.
Así, a liña negra só dividido á metade esquerda
ea metade dereita da parte tipo.
>> Nós comparamos o menor valor na parte esquerda da array--
ou me desculpar, o menor valor da metade esquerda
ao valor menor da dereita metade e descubrir que tres é menor.
E agora un pouco de unha optimización, non?
Hai realmente nada esquerda, na parte esquerda.
>> Non hai nada que resta na parte esquerda,
para que poidamos eficientemente só move-- podemos declarar
o resto é, en realidade, clasificadas e só predica-la
sobre, porque non hai nada outra para comparación.
E sabemos que o lado dereito da dereita está clasificada.
>> OK, entón agora imos conxelar de novo e descubrir onde estamos na historia.
En xeral a matriz, o que fixemos?
Nós realmente realizar Agora os pasos un e dous etapa.
Separamos a metade esquerda, e nós ordenamos a metade dereita.
>> Entón, agora, todo o que queda é para nós para mesturar estas dúas metades xuntas.
Entón, nós comparamos o menor valorado elemento de cada metade da matriz
á súa vez, e continúe.
Un é inferior a tres, para que se pasa.
>> Dous é inferior a tres, así que dous vai.
Tres é inferior a 5, de xeito que tres intentos.
Catro é inferior a 5, de xeito que vai de catro.
A continuación, cinco é menos de seis, e seis é todo o que queda.
>> Agora, sei, iso foi unha serie de etapas.
E deixamos moi de memoria na nosa comentario.
E iso é o que eses son cadrados gris.
E probablemente me sentín como que tivo un moito máis que a ordenación por inserción, burbulla
sort, ou ordenación por selección.
>> Pero en realidade, porque un moitos destes procesos
están a ocorrer ao mesmo tempo-- que é algo que vai, unha vez máis,
falar cando falamos de recursão nun futuro video--
este algoritmo efectivamente claramente é fundamentalmente
diferente de todo vimos antes
pero tamén é significativamente máis eficiente.
>> Por que é iso?
Ben, no peor escenario, temos
para dividir n elementos up e logo recombinam a eles.
Pero cando recombinar los, o que estamos facendo
é basicamente dobrando o tamaño das matrices menores.
Temos unha morea de un elemento matrices que efectivamente
combinar en dúas matrices de elementos.
E, a continuación, tomamos os dúas matrices elemento
e combina-los catro matrices de elementos, e así por diante,
etc., e así por diante, ata que ten unha única matriz elemento n.
>> Pero cantas repetidos que fai falta para chegar ao n?
Pense de novo o exemplo do libro de teléfono.
Cantas veces hai que rasgar o libro de teléfono pola metade, cantos máis
veces hai que rasgar o libro de teléfono en metade, se o tamaño do libro de teléfono
duplicou?
Hai só un, non?
>> Polo tanto, hai algún tipo de elemento logarítmica aquí.
Pero nós tamén aínda temos que, polo menos, mirar para todo n elementos.
Así, no peor dos casos, merge sort é executado en log n n.
Temos que mirar para todo n elementos,
e temos que combina-los en conxunto en N rexistro N conxuntos de pasos.
No mellor dos casos, a matriz é perfectamente ordenadas.
Isto é óptimo.
Pero baseado no algoritmo que temos aquí, aínda temos que dividir e recombinar.
Aínda que, neste caso, o recombinación é unha especie de ineficaz.
Isto non é necesario.
Pero aínda pasar por todo o proceso de calquera maneira.
>> Así, no mellor dos casos e, no peor caso,
este algoritmo é executado en log n n tempo.
Merge sort é sempre un pouco máis complicado do que os outros principais algoritmos de ordenación
xa falamos sobre CS50, pero é substancialmente máis poderoso.
>> E por iso, se algunha vez atoparse ocasión para que del
ou usalo para clasificar unha gran conxunto de datos, obtendo
súa cabeza en torno á idea de recursão será realmente poderoso.
E que vai facer o seu programas realmente moito máis eficiente
usando merge sort contra calquera outra cousa.
Eu son Doug Lloyd.
Este é CS50.