[Powered by Google Translate] [Merge sort] [Rob Bowden - Harvard University] [Esta é CS50. - CS50.TV] Imos falar sobre o tipo de mesclagem. Ata agora xa viu especie de burbulla, tipo de inserción e tipo de selección. Aínda que eu vou tipo de onda miña man que eu quero dicir con mellor, merge sort xeralmente ten un rendemento mellor que calquera destes tres tipos. 

Pero antes de falar merge sort, imos falar sobre a mesclagem de dúas listas ordenadas. Imos chamar o proceso de tomar dúas listas ordenadas, como estes, e facer unha única lista ordenada fóra delas - a fusión das listas. Como podemos facer iso? Ben, unha idea é se ater só unha lista para o final da lista de outro e despois ordenar a lista resultante. 

Mentres tanto funciona, é unha chea de traballo innecesario. Podemos facelo máis rápido que só a clasificación. Teña en conta que unha idea errónea é só para tomar vasos alternadas de cada lista. Aínda que isto poida parecer que funciona nun primeiro momento, facendo iso acabamos con 4, 8, 15, 23, 16 - aviso de que 16 e 23 están fóra de lugar. Isto porque dous elementos que deben aparecer consecutivo na lista mesclada están na mesma lista inicial. Ambos 15 e 16 están na lista do lado esquerdo. O truco é aproveitar o feito de que ambas as listas xa están clasificados. Isto significa que, se só ollar para os primeiros elementos de ambas as listas - aquí, 4 e 8 - un deles tamén debe ser o primeiro elemento da lista resultante da fusión. Ben, por que isto? Ambas as listas xa están clasificados, e entón ou 4 ou 8 debe ser o elemento máis pequeno cando se combinan as dúas listas. Neste caso, a máis pequena e 4, para que poidamos aproveitar 4 e facelo o primeiro elemento da lista mesclada. Agora imos continuar a fusión das restantes tres elementos da primeira lista e 4 elementos da segunda rolda. 

Unha vez máis, nós só necesitamos mirar para o primeiro elemento de ambas as listas. O menor dos dous debe ser o segundo elemento da lista resultante da fusión. Esta vez, entre 8 e 15 o máis pequeno é de 8, e entón introducir este como o segundo elemento da lista de clasificados. Podemos seguir comparando os primeiros elementos de ambas as listas e eliminar o menor dos dous. Comparando 15 e 23, 15 é menor e así é o noso terceiro elemento. Agora comparar 16 e 23, 16 é menor. Entón ese é o cuarto elemento. 

Teña en conta que dous elementos viñeron da mesma lista nunha fileira. É por iso que a lista resultante da fusión non pode só elementos alternados das dúas listas. Comparando 50 e 23, 23 é menor, polo tanto, escolla que. Entre 50 e 42, 42 é menor. Entre 50 e 108, 50 é menor. E, finalmente, temos só 108, polo que debe ir ao final da nosa lista. Teña en conta que temos unha lista, bo ordenado. Cada vez que se compararon os 2 primeiros elementos das dúas listas fomos capaces de determinar o elemento seguinte da lista resultante da fusión. Isto significa que a lista final contén n números, onde n aquí é 8, entón necesitamos na maioría das comparacións n para obter todos estes números para o lugar seguro. Tal algoritmo está dito para ser executado en tempo lineal, pero non se preocupe con iso aquí. 

Usando o noso algoritmo de fusión, podemos facer un algoritmo de ordenación rápido mesclagem. Entón, imos recuperar nosas listas. Existen dous grandes pasos no proceso de merge sort. En primeiro lugar, de forma continua dividir a lista de vasos en metades ata que teñamos unha morea de listas con só 1 cunca neles. Non te preocupes se a lista contén un número impar e non pode facer un corte perfectamente limpo entre eles. Só arbitrariamente escoller cal alista para incluír o vaso extra dentro Entón, imos dividir estas listas. Agora temos dúas listas. Agora temos catro listas. 

E agora temos oito listas con un só vaso de cada lista. Entón é iso para o paso 1. Para a etapa 2, nós repetidamente fundir pares de listas usando o algoritmo de unión que aprenden antes. Mesclando 108 e 15, imos acabar coa lista de 15, 108. Mesclando 50 e 4, imos acabar con 4, 50. Mesclando 8 e 42, imos acabar con 8, 42. E fusión de 23 e 16, imos acabar con 16, 23. Agora todas as nosas listas son de tamaño 2. Teña en conta que cada unha das catro listas son clasificados. 

Así, podemos comezar a fundirse pares de listas de novo. A fusión 15 e 108 e 4 e 50 - tira primeiro a 4, a continuación, a 15, a continuación a 50, a continuación a 108. Mesclando 8, 42 e 16, 23, que comezou a tomar o 8, a continuación, a 16, a continuación a 23, a continuación a 42. Polo tanto, agora temos só 2 listas de tamaño 4, cada un dos cales está clasificada. Entón agora nós mesturar estas dúas listas. Primeiro tomamos a 4. Entón tomamos a 8. A continuación, tomar a 15 e 16, e despois 23, despois 42, despois 50, despois 108. E estamos a facer. Temos, agora, unha lista ordenada. Entón, quão rápido foi iso, exactamente? En termos técnicos, merge sort é O (n log n), Considerando que todos especie de burbulla, tipo de inserción e tipo de selección son O (n ²). En realidade, como vai aprender logo, non será capaz de chegar a unha especie que ten un rendemento mellor que o (n log n) no caso xeral. Unha vez máis, non se preocupe con esta notación O gran se non viu aínda. 

Só sei que isto significa que, se quixésemos Ordenar unha lista moi grande tipo especie de burbulla, tipo de inserción e selección podería levar significativamente maior que merge sort. Iso non significa que a clasificación por intercalação será máis rápida para todas as listas ou mesmo para calquera lista única nun determinado tamaño. Por exemplo, tipo de inserción pode ser o máis rápido de clasificación para as listas de menores de 5 elementos. Na práctica, merge sort é normalmente máis rápido para listas de tan pequenas canto 50 elementos. 

Pero esa velocidade extra non vén sen un prezo. Ao contrario dos nosos outros tipos, que levan unha lista e modificar a lista en lugar ata chegar a unha lista ordenada, merge sort necesita un espazo adicional fundir dúas listas. Non podemos usar inmediatamente as listas que están sendo incorporadas para gardar a lista mesclada unha vez que poden substituír elementos que aínda precisan ser mescladas. Este espazo é un pouco de prezo, pero, xeralmente, non é razoable. E iso é todo para merge sort. 

O meu nome é Rob Bowden, e este é o CS50. [CS50.TV] - Selección e ordenación. [Risas] Ah, ten que ter iso tamén, porque eu mudei como eu estaba me presentando. Lista á esquerda. Iso foi un erro de dixitación. [Misspoke] eu estraguei todo - [Risas] Eu non sei o que -