[Powered by Google Translate] [Merge sort] [Rob Bowden - Harvard University] [Esta é CS50. - CS50.TV] Vamos falar sobre o tipo de mesclagem. Até agora você já viu espécie de bolha, tipo de inserção e tipo de seleção. Embora eu vou tipo de onda minha mão do que eu quero dizer com melhor, merge sort geralmente tem um desempenho melhor do que qualquer um desses três tipos. 

Mas antes de falar sobre merge sort, vamos falar sobre a mesclagem de duas listas ordenadas. Vamos chamar o processo de tomar duas listas ordenadas, como estes, e fazer uma única lista ordenada fora delas - a fusão das listas. Como podemos fazer isso? Bem, uma idéia é se ater apenas uma lista para o final da lista de outro e depois ordenar a lista resultante. 

Enquanto isso funciona, é um monte de trabalho desnecessário. Nós podemos fazê-lo mais rápido do que apenas a classificação. Observe que uma idéia errada é apenas para tomar copos alternadas de cada lista. Embora isso possa parecer que funciona num primeiro momento, fazendo isso acabamos com 4, 8, 15, 23, 16 - aviso de que 16 e 23 estão fora de lugar. Isto porque dois elementos que devem aparecer consecutivo na lista mesclada estão na mesma lista inicial. Ambos 15 e 16 estão na lista do lado esquerdo. O truque é aproveitar o fato de que ambas as listas já estão classificados. Isto significa que, se apenas olhar para os primeiros elementos de ambas as listas - aqui, 4 e 8 - um deles também deve ser o primeiro elemento da lista resultante da fusão. Bem, por que isso? Ambas as listas já estão classificados, e então ou 4 ou 8 deve ser o elemento mais pequeno quando se combinam as duas listas. Neste caso, a mais pequena é 4, para que possamos tirar 4 e torná-lo o primeiro elemento da nossa lista mesclada. Agora vamos continuar a fusão das restantes três elementos da primeira lista e 4 elementos da segunda lista. 

Mais uma vez, nós só precisamos olhar para o primeiro elemento de ambas as listas. O menor dos dois deve ser o segundo elemento da nossa lista resultante da fusão. Desta vez, entre 8 e 15 o mais pequeno é de 8, e então inserir esse como o segundo elemento da nossa lista de classificados. Podemos continuar comparando os primeiros elementos de ambas as listas e removendo o menor dos dois. Comparando 15 e 23, 15 é menor e assim é o nosso terceiro elemento. Agora comparar 16 e 23, 16 for menor. Então esse é o quarto elemento. 

Observe que dois elementos vieram da mesma lista em uma fileira. É por isso que a lista resultante da fusão não pode apenas elementos alternados das duas listas. Comparando 50 e 23, 23 é menor, portanto, escolha que. Entre 50 e 42, 42 for menor. Entre 50 e 108, 50 for menor. E, finalmente, temos apenas 108, por isso deve ir no final de nossa lista. Observe que temos uma lista, bom ordenado. Cada vez que se compararam os 2 primeiros elementos das duas listas fomos capazes de determinar o elemento seguinte da lista resultante da fusão. Isto significa que se a lista final contém n números, onde n aqui é 8, então precisamos na maioria das comparações n para obter todos esses números para o lugar certo. Tal algoritmo é dito para ser executado em tempo linear, mas não se preocupe com isso aqui. 

Usando o nosso algoritmo de fusão, podemos fazer um algoritmo de ordenação rápido mesclagem. Então, vamos repor nossas listas. Existem dois grandes passos no processo de merge sort. Em primeiro lugar, de forma contínua dividir a lista de copos em metades até que tenhamos um monte de listas com apenas 1 xícara neles. Não se preocupe se uma lista contém um número ímpar e você não pode fazer um corte perfeitamente limpo entre eles. Apenas arbitrariamente escolher qual lista para incluir o copo extra dentro Então, vamos dividir essas listas. Agora temos duas listas. Agora temos quatro listas. 

E agora temos oito listas com um único copo em cada lista. Então é isso para o passo 1. Para a etapa 2, nós repetidamente fundir pares de listas usando o algoritmo de junção que aprendemos antes. Mesclando 108 e 15, vamos acabar com a lista de 15, 108. Mesclando 50 e 4, vamos acabar com 4, 50. Mesclando 8 e 42, vamos acabar com 8, 42. E fusão de 23 e 16, vamos acabar com 16, 23. Agora todas as nossas listas são de tamanho 2. Observe que cada uma das quatro listas são classificados. 

Assim, podemos começar a fundir pares de listas novamente. A fusão 15 e 108 e 4 e 50 - tira primeiro a 4, em seguida, a 15, em seguida a 50, em seguida a 108. Mesclando 8, 42 e 16, 23, que começou a tomar o 8, em seguida, a 16, em seguida a 23, em seguida a 42. Portanto, agora temos apenas 2 listas de tamanho 4, cada um dos quais está classificada. Então agora nós mesclar essas duas listas. Primeiro tomamos a 4. Então tomamos a 8. Em seguida, tomar a 15 e 16, e depois 23, depois 42, depois 50, depois 108. E estamos a fazer. Temos, agora, uma lista ordenada. Então, quão rápido foi isso, exatamente? Em termos técnicos, merge sort é O (n log n), Considerando que todos espécie de bolha, tipo de inserção e tipo de seleção são O (n ²). Na verdade, como você vai aprender logo, você não será capaz de chegar a uma espécie que tem um desempenho melhor do que O (n log n) no caso geral. Mais uma vez, não se preocupe com esta notação O grande se você não viu ainda. 

Só sei que isso significa que, se quiséssemos classificar uma lista muito grande tipo espécie de bolha, tipo de inserção e seleção poderia levar significativamente maior do que merge sort. Isso não significa que a classificação por intercalação será mais rápida para todas as listas ou mesmo para qualquer lista única em um determinado tamanho. Por exemplo, tipo de inserção pode ser o mais rápido de classificação para todas as listas de menores de 5 elementos. Na prática, merge sort é normalmente mais rápido para listas de tão pequenas quanto 50 elementos. 

Mas essa velocidade extra não vem sem um preço. Ao contrário dos nossos outros tipos, que levam uma lista e modificar a lista em lugar até chegarmos a uma lista ordenada, merge sort precisa de algum espaço adicional fundir duas listas. Nós não podemos usar imediatamente as listas que estão sendo incorporadas para armazenar a lista mesclada uma vez que podem substituir elementos que ainda precisam ser mescladas. Este espaço é um pouco de preço, mas, geralmente, não é razoável. E isso é tudo para merge sort. 

Meu nome é Rob Bowden, e este é o CS50. [CS50.TV] - Selecção e ordenação. [Risos] Ah, tem que ter isso também, porque eu mudei como eu estava me apresentando. Lista à esquerda. Isso foi um erro de digitação. [Misspoke] eu estraguei tudo - [Risos] Eu não sei o que -