>> [Música tocando]
>> DOUG LLOYD: OK, então uma mesclagem tipo é mais um algoritmo
que podemos usar para resolver os elementos de uma matriz.
Mas, como veremos, tem um diferença muito fundamental
de seleção tipo, bolha tipo e ordenação por inserção
que o tornam realmente muito inteligente.
>> A idéia básica por trás de mesclagem tipo é classificar matrizes menores
e, em seguida, combinar essas matrizes juntos, ou mesclar eles--
daí o nome-- na ordem de classificação.
A maneira que merge sort faz isto é, aproveitando uma ferramenta
chamado recursão, que é o que nós vamos estar falando em breve,
mas nós realmente não conversamos sobre isso ainda.
>> Aqui é a idéia básica por trás merge sort.
Classificar a metade esquerda da matriz, assumindo que n é maior do que 1.
E o que eu quero dizer quando digo assumindo que n é maior do que 1 é,
Eu acho que nós podemos concordar que se uma matriz consiste somente de um único elemento,
ele é classificado.
Nós realmente não precisa para fazer qualquer coisa para ele.
Podemos apenas declará-lo para ser classificado.
É apenas um único elemento.
>> Assim, o pseudocódigo, novamente, é ordenar a metade do lado esquerdo da matriz,
em seguida, classificar a metade direita da matriz, em seguida, mesclar as duas metades juntas.
Agora, já que você pode ser pensando, ele tipo de apenas
Parece que você está adiando as-- você não está realmente fazendo alguma coisa.
Você está dizendo classificar à esquerda metade, ordenar a metade direita,
mas você não está dizendo me como você está fazendo isso.
>> Mas lembre-se que, enquanto uma matriz é um único elemento,
podemos declará-la classificada.
Então nós podemos apenas combiná-los juntos.
E isso é realmente o ideia fundamental por trás merge sort,
é para quebrá-lo para baixo, de modo que suas matrizes são de tamanho um.
E então você reconstruir a partir daí.
>> Merge sort é definitivamente um algoritmo complicado.
E é também um pouco complicada para visualizar.
Portanto, esperamos que, a visualização que eu temos aqui vai ajudá-lo a seguir adiante.
E eu vou tentar o meu melhor para narrar as coisas e prosseguir com este um pouco mais
lentamente do que os outros apenas com a esperança de obter a sua cabeça
em torno das idéias por trás merge sort.
>> Portanto, temos a mesma matriz como a outras algoritmo de classificação vídeos
se você já viu eles-- uma matriz de seis elementos.
E o nosso código pseudocode aqui é classificar a metade esquerda, ordenar a metade direita,
mesclar as duas metades juntas.
Então, vamos dar este tijolo vermelho muito escuro array e classificar a metade esquerda do mesmo.
>> Então, por enquanto, vamos a ignorar as coisas à direita.
É lá, mas estamos não naquele passo ainda.
Nós não somos a espécie a metade direita da matriz.
Estamos em espécie à esquerda metade da matriz.
E apenas por uma questão de ser um pouco mais
claro, para que eu possa consultar para o passo que estamos no,
Eu vou mudar o cor deste conjunto de laranja.
Agora, nós ainda estamos falando sobre o mesma metade esquerda da matriz original.
Mas eu estou esperando que por ser capaz de referem-se às cores de vários itens,
ele vai torná-lo um pouco mais claro o que está acontecendo aqui.
>> OK, então agora temos um três matriz elemento.
Como podemos classificar a metade esquerda deste matriz, o que é ainda neste passo?
Nós estamos tentando classificar a esquerda metade do tijolo vermelho array--
a metade esquerda das quais Eu tenho agora de cor laranja.
>> Bem, nós poderíamos tentar repetir esse processo novamente.
Então, nós ainda estamos no meio tentando classificar
a metade esquerda da matriz completa.
A metade esquerda do array, eu só vou
para decidir arbitrariamente que a metade esquerda será menor do que a metade direita,
porque isto acontece a composto por três elementos.
>> E assim eu vou dizer que o metade esquerda da metade esquerda da matriz
é apenas o elemento cinco.
Cinco, sendo um único elemento array, nós sabemos como resolver isso.
E assim cinco está classificada.
Nós apenas estamos indo para declarar isso.
É uma única matriz elemento.
>> Então, nós temos agora classificados o metade esquerda da esquerda half--
ou melhor, temos classificados o metade esquerda da laranja.
Então, agora, a fim de ainda completa metade esquerda da matriz total,
precisamos classificar a metade direita da laranja, ou essas coisas.
Como fazemos isso?
Bem, nós temos um array com dois elementos.
Assim, podemos classificar a metade esquerda da matriz, que é dois.
Dois é um único elemento.
Por isso é classificado por padrão. Então, podemos classificar a metade direita
de que a porção de matriz, a uma.
Isso é tipo de por padrão.
>> Isto é agora pela primeira vez chegamos a um passo de mesclagem.
Nós completamos, embora agora estamos tipo de aninhados down--
e que é uma espécie de complicado coisa com recursividade é,
você precisa para manter seu cabeça sobre onde nós estamos.
Então, nós tipo de esquerda metade da porção de laranja.
>> E agora, nós estamos no meio de triagem a metade direita da porção de laranja.
E, nesse processo, estamos agora prestes a ser no degrau,
mesclar as duas metades juntas.
Quando olhamos para as duas metades da matriz, vemos dois e um.
Elemento que é menor?
Uma.
>> Em seguida, o qual elemento é menor?
Bem, é duas ou nada.
Portanto, é dois.
Então, agora, só para enquadrar novamente onde estamos no contexto,
nós ter resolvido o metade esquerda da laranja
e a metade direita da origem.
Eu sei que eu mudei as cores de novo, mas que é onde estávamos.
E a razão pela qual eu fiz isso é porque este processo é
vai continuar, a iteração para baixo.
Temos classificados esquerda a metade da laranja ex
e a metade direita do ex-laranja.
>> Agora, precisamos mesclar aqueles duas metades juntos também.
Essa é a etapa em que estamos.
Portanto, considerar todas as elementos que são agora verde,
a metade esquerda da matriz original.
E nós mesclar aqueles utilizando o mesmo processo de
fizemos para mesclar dois e um apenas um momento atrás.
>> A metade da esquerda, a menor elemento na metade esquerda é cinco.
O elemento mais pequeno a metade direita é um deles.
Qual dessas é menor?
Uma.
>> O elemento mais pequeno a metade esquerda é cinco.
O elemento mais pequeno a metade direita é dois.
Qual é o menor?
Dois.
E por último, em seguida, cinco e nada, podemos dizer cinco.
>> OK, portanto, grande figura, vamos fazer uma pausa por um segundo
e descobrir onde estamos.
Se começássemos a partir de o início, nós
agora completou para a matriz global apenas
um passo do código pseudocode aqui.
Nós ter resolvido o metade esquerda da matriz.
>> Lembre-se que o original ordem era cinco, dois, um.
Ao passar por este processo e nidificação para baixo e repetir,
continuando a quebrar o problema em partes cada vez menores,
temos agora concluída um passo do pseudocode
para toda a matriz de partida.
Nós ter resolvido sua meia esquerda.
>> Então agora vamos congelar lá.
E agora vamos classificar a direita metade da matriz original.
E vamos fazer isso por passando pela mesma iterativo
processo de quebrar as coisas e, em seguida, mesclando-los juntos.
>> Assim, a metade esquerda da vermelho, ou a metade esquerda
da metade direita do original array, eu vou dizer é três.
Mais uma vez, eu estou sendo consistente aqui.
Se você tem um estranho número de elementos, ela
Não importa realmente se você faz o esquerdo menor
ou o direito de um menor.
>> O que importa é que sempre que você deparar com este problema na condução
uma mala, você precisa ser consistente.
Você quer sempre precisa fazer um lado esquerdo menor
ou sempre precisa fazer o lado direito menor.
Aqui, eu escolhi para sempre fazer o lado esquerdo menor
quando minha matriz, ou o meu sub-array, é de uma dimensão ímpar.
>> Três é um único elemento, e por isso é ordenada.
Temos aproveitado essa suposição em todo o nosso processo até agora.
Então agora vamos classificar a direita metade da metade direita,
ou a metade direita do vermelho.
>> Mais uma vez, temos de dividir isso para baixo.
Este não é um único elemento de matriz.
Não podemos declará-la classificada.
E assim em primeiro lugar, vamos para classificar a metade esquerda.
>> A metade da esquerda é um único elemento, por isso é tipo de por padrão.
Então vamos classificar a direita metade, que é um único elemento.
É classificado por padrão. E agora, que pode mesclar os dois juntos.
Quatro é menor, e em seguida, seis é menor.
>> Mais uma vez, o que temos feito neste momento?
Temos classificados esquerda metade da metade direita.
Ou voltar para o original cores que estavam lá,
temos ordenados esquerda metade do vermelho mais suave.
Ele foi originalmente um tijolo escuro vermelho e agora é um vermelho mais suave,
ou um vermelho foi mais suave.
>> E então temos o classificado metade direita do vermelho mais suave.
Agora, bem, eles são verde novamente, apenas porque estamos passando por um processo.
E nós temos que repetir isso mais e mais.
>> Então agora podemos mesclar aqueles duas metades juntas.
E isso é o que fazemos aqui.
Assim, a linha preta apenas dividido a metade esquerda
ea metade direita da parte tipo.
>> Nós comparamos o menor valor no lado esquerdo da array--
ou me desculpar, o menor valor da metade esquerda
para o valor menor da direita metade e descobrir que três é menor.
E agora um pouco de uma otimização, certo?
Há realmente nada esquerda, no lado esquerdo.
>> Não há nada restante do lado esquerdo,
para que possamos eficientemente apenas move-- podemos declarar
o resto é, na verdade, classificadas e apenas pregá-la
sobre, porque não há nada outra para comparação.
E nós sabemos que o lado direito do lado direito está classificada.
>> OK, então agora vamos congelar novamente e descobrir onde estamos na história.
Em geral a matriz, o que temos feito?
Nós realmente realizar Agora as etapas um e dois etapa.
Separamos a metade esquerda, e nós ordenamos a metade direita.
>> Então, agora, tudo o que resta é para nós para mesclar essas duas metades juntas.
Então, nós comparamos o menor valorizado elemento de cada metade da matriz
por sua vez, e prossiga.
Um é inferior a três, para que se passa.
>> Dois é inferior a três, assim que dois vai.
Três é inferior a 5, de modo que três tentativas.
Quatro é inferior a 5, de modo que vai de quatro.
Em seguida, cinco é menos de seis, e seis é tudo o que resta.
>> Agora, eu sei, isso foi uma série de etapas.
E nós deixamos muito de memória em nossa esteira.
E é isso que esses são quadrados cinza.
E provavelmente me senti como que teve um muito mais do que a ordenação por inserção, bolha
sort, ou ordenação por seleção.
>> Mas, na realidade, porque um muitos destes processos
estão acontecendo ao mesmo tempo-- que é algo que vai, mais uma vez,
falar quando falamos de recursão em um futuro video--
este algoritmo efectivamente claramente é fundamentalmente
diferente de tudo temos visto antes
mas também é significativamente mais eficiente.
>> Por que é que?
Bem, na pior cenário, temos
para dividir n elementos up e em seguida recombinam-los.
Mas quando nós recombinar los, o que estamos fazendo
é basicamente dobrando o tamanho das matrizes menores.
Temos um monte de um elemento matrizes que efectivamente
combinar em duas matrizes de elementos.
E, em seguida, tomamos aqueles duas matrizes elemento
e combiná-los em quatro matrizes de elementos, e assim por diante,
e assim por diante, e assim por diante, até que tem uma única matriz elemento n.
>> Mas quantas duplicações que é preciso para chegar ao n?
Pense de volta para o exemplo do livro de telefone.
Quantas vezes temos de rasgar o livro de telefone pela metade, quantos mais
vezes temos de rasgar o livro de telefone em metade, se o tamanho do livro de telefone
duplicou?
Há apenas um, certo?
>> Portanto, há algum tipo de elemento logarítmica aqui.
Mas nós também ainda temos que, pelo menos, olhar para todos os n elementos.
Assim, no pior dos casos, merge sort é executado em log n n.
Temos de olhar para todos os n elementos,
e nós temos que combiná-los em conjunto em N log N conjuntos de passos.
Na melhor das hipóteses, a matriz é perfeitamente ordenadas.
Isso é ótimo.
Mas baseado no algoritmo que temos aqui, ainda temos de dividir e recombinar.
Embora, neste caso, o recombinação é uma espécie de ineficaz.
Isto não é necessário.
Mas nós ainda passar por todo o processo de qualquer maneira.
>> Assim, na melhor das hipóteses e, no pior caso,
este algoritmo é executado em log n n tempo.
Merge sort é definitivamente um pouco mais complicado do que os outros principais algoritmos de ordenação
nós já conversamos sobre CS50, mas é substancialmente mais poderoso.
>> E por isso, se você alguma vez encontrar- ocasião para precisar dele
ou usá-lo para classificar uma grande conjunto de dados, obtendo
sua cabeça em torno da idéia de recursão vai ser realmente poderoso.
E ele vai fazer o seu programas realmente muito mais eficiente
usando merge sort contra qualquer outra coisa.
Eu sou Doug Lloyd.
Este é CS50.