[Powered by Google Translate] [Merge Sort] [Rob Bowden - Harvard University] [Aquesta és CS50. - CS50.TV] Parlem de tipus de mescla. Fins ara hem vist espècie de bombolla, ordenació per inserció, i una mena de selecció. Encara Vaig tipus d'ona meva mà en el que vull dir millor, merge sort generalment funciona millor que qualsevol d'aquests tres tipus. 

Però abans de parlar de tipus de mescla, parlarem de la fusió de dues llistes ordenades. L'anomenarem el procés de prendre 2 llistes ordenades, com aquests, i fer una única llista ordenada d'ells - la fusió de les llistes. Com podem fer això? Bé, una idea és seguir una sola llista a l'extrem de l'altra llista i després ordenar la llista de resultats. 

Si bé això funciona, és una gran quantitat de treball innecessari. Podem fer-ho més ràpid que un simple classificació. Tingueu en compte que una idea equivocada consisteix en prendre copes alternats de cada llista. Si bé això pot semblar que funciona al principi, fent que ens trobem amb 4, 8, 15, 23, 16 - Anunci que el 16 i 23 estan fora de lloc. Això es deu a dos elements que han d'aparèixer consecutiu a la llista resultant de la fusió són a la llista inicial igual. Tant el 15 i 16 estan en la llista de l'esquerra. El truc consisteix en aprofitar el fet que les dues llistes ja estan ordenats. Això vol dir que si ens fixem en els primers elements de les dues llistes - aquí, 4 i 8 - un d'ells ha de ser també el primer element de la llista combinada. Bé, per què és això? Ambdues llistes ja estan ordenats, i per tant ja sigui de 4 o 8 ha de ser l'element més petit quan combinem les dues llistes. En aquest cas, el més petit és 4, pel que podem treure 4 i convertir-lo en el primer element de la llista combinada. Ara continuem la fusió dels 3 restants elements de la primera llista i 4 elements de la segona llista. 

Un cop més, només hem de mirar el primer element de les dues llistes. El menor dels 2 ha de ser el segon element de la llista combinada. Aquesta vegada, entre el 8 i el 15 el més petit és de 8, de manera que inserir aquest com el segon element de la llista ordenada. Podem seguir comparant els primers elements de les dues llistes i l'eliminació de la menor de les 2. Comparant els 15 i 23 15, és més petit i per tant aquest és el nostre tercer element. Ara comparant 16 i 23, 16 és més petit. Així que aquest és el quart element. 

Tingueu en compte que dos elements provenien de la mateixa llista en una fila. Per això, la llista resultant de la fusió no pot simplement elements alternatius a partir de les 2 llistes. Comparant els 50 i 23, 23 és més petit, així que triem això. Entre 50 i 42, 42 és més petit. Entre 50 i 108, 50 és més petit. I, finalment, només tenim 108, per la qual cosa ha d'anar al final de la nostra llista. Recordeu que tenim una bona llista, ordenada. Cada vegada que es van comparar els primer 2 elements de les llistes 2 hem estat capaços de determinar el següent element de la llista combinada. Això vol dir que si la llista final conté un nombre n, on n és aquí 8, llavors tenim que en la majoria de les comparacions n per obtenir tots els nombres en el lloc correcte. Tal algorisme es diu que s'executen en temps lineal, però no et preocupis per això aquí. 

Usant el nostre algorisme per a la fusió, podem fer un ràpid algorisme de combinació tipus. Per tant, anem a restablir les nostres llistes. Hi ha 2 grans passos en el procés de l'espècie de barreja. En primer lloc, contínuament dividir la llista de copes en dues meitats fins que tinguem un munt de llistes amb només 1 tassa-hi. No et preocupis si una llista conté un nombre imparell i no es pot fer un tall perfectament net entre ells. Només arbitràriament escollir quina voleu incloure la tassa extra cm Per tant, anem a dividir aquestes llistes. Ara tenim 2 llistes. Ara tenim 4 llistes. 

I ara tenim 8 llistes amb una sola tassa a cada llista. Així que això és tot pel pas 1. Per al pas 2, repetidament barreja parells de llistes usant l'algorisme de fusió que hem après abans. La fusió de 108 i 15, ens trobem amb la llista de 15, 108. La fusió de 50 i 4, ens trobem amb 4, 50. La fusió de 8 i 42, vam acabar amb 8, 42. I la fusió de 23 i 16, vam acabar amb 16, 23. Ara totes les nostres llistes són de mida 2. Observeu que cadascuna de les 4 llistes està ordenada. 

Així que podem començar la fusió de parells de llistes de nou. La fusió de 15 i 108 i 4 i 50 - primer prendre la 4, a continuació, la 15, la 50, llavors el 108. La fusió de 8, 42 i 16, 23, en primer lloc assumir el 8, el 16, després el 23, després el 42. Així que ara tenim només 2 llistes de mida 4, cada un dels quals està ordenada. Així que ara ens fusionem aquestes dues llistes. En primer lloc, prendre la 4. Després prenem el 8. Llavors es pren el 15 i el 16, i després 23, després 42, després 50, després 108. I hem acabat. Ara tenim una llista ordenada. Així ho ràpid que era això, exactament? En termes tècnics, una espècie de combinació és O (n log n), mentre que tots els de tipus bombolla, ordenació per inserció, i una mena de selecció són O (n ²). De fet, com vostè aprendrà aviat, vostè no serà capaç d'arribar a una espècie que es comporta millor que O (n log n) en el cas general. Un cop més, no es preocupi per aquesta notació gran O si vostè no ho ha vist encara. 

Només que sàpigues que això vol dir que si volíem ordenar una llista molt gran espècie tipus bombolla, ordenació per inserció, i la selecció podria prendre significativament més llarg que merge sort. Això no vol dir que aquest tipus de barreja serà més ràpid per a totes les llistes o fins i tot per a qualsevol llista única sota una certa grandària. Per exemple, el tipus d'inserció pot ser el més ràpid de classificació de totes les llistes de menors de 5 elements. A la pràctica, una mena de combinació és generalment més ràpid per les llistes de només 50 elements. 

No obstant això, aquesta velocitat extra no ve sense un preu. A diferència dels nostres altres gèneres, que tenen una llista i modificar la llista al seu lloc fins que tinguem una llista ordenada, una mena de barreja necessita una mica d'espai addicional per fusionar 2 llistes. No es pot utilitzar immediatament les llistes que es van fusionar per emmagatzemar la llista resultant de la fusió ja que poden anul · lar els elements que encara han de ser combinades. Aquest espai és una mica d'un preu, però en general no és irraonable. I això és tot per tipus de mescla. 

El meu nom és Rob Bowden, i això és CS50. [CS50.TV] - Selecció i ordenació. [Rialles] Oh, he de prendre això també perquè em vaig canviar com ho estava presentant. Llista de l'esquerra. Això va ser un error. [Equivocar al parlar] Vaig cometre un error - [Rialles] No sé per què -