[Powered by Google Translate] [Merge Sorteer] [Rob Bowden - Harvard Universiteit] [Hierdie is CS50. - CS50.TV] Kom ons praat oor merge soort. Tot dusver het jy gesien borrel soort, invoeging soort, en seleksie soort. Alhoewel ek sal soort van golf my hand op wat ek bedoel deur 'n beter, saamsmelt soort voer oor die algemeen beter as enige van hierdie 3 vorme. 

Maar voordat praat oor merge soort, laat ons praat oor die samesmelting van 2 gesorteer lyste. Ons sal die proses van die neem van 2 gesorteer lyste roep, soos hierdie, en die maak van 'n gesorteerde lys van hulle - die samesmelting van die lyste. Hoe kan ons dit doen? Wel, 'n idee is om net te hou 'n lys op die einde van die ander lys en dan sorteer die lys. 

Terwyl hierdie werk, dit is 'n baie onnodige werk. Ons kan dit doen vinniger as net sorteer. Let daarop dat een verkeerde idee is om net wisselstroom koppies uit elke lys. Terwyl dit kan lyk soos dié werke op die eerste, doen dat ons opeindig met 4, 8, 15, 23, 16 - kennisgewing dat 16 en 23 is uit plek. Dit is omdat die 2 elemente wat in die saamgesmelte lys moet verskyn agtereenvolgende is in dieselfde aanvanklike lys. Beide 15 en 16 is in die lys aan die linkerkant. Die truuk is om voordeel te trek uit die feit dat beide lyste word reeds gesorteer. Dit beteken dat as ons net kyk na die eerste elemente van beide lyste - hier, 4 en 8 - een van hulle moet ook die eerste element van die saamgesmelte lys. Wel, hoekom is dit? Beide van hierdie lyste is reeds gesorteer, en so 4 of 8 moet die kleinste element wees wanneer ons kombineer die 2 lyste. In hierdie geval, die kleinste is 4, sodat ons kan neem 4 en maak dit die eerste element van die saamgesmelte lys. Nou moet ons voortgaan met die samesmelting van die oorblywende 3 elemente van die eerste lys en 4 elemente van die tweede lys. 

Weereens, ons moet net om te kyk na die eerste element van beide lyste. Die kleiner van die 2 die tweede element van ons saamgesmelte lys moet wees. Hierdie tyd, tussen 8 en 15 die kleinste is 8, en sodat ons voeg dat as die tweede element van ons gesorteerde lys. Ons kan voortgaan om die eerste elemente van beide lyste te vergelyk en die verwydering van die kleiner van die 2. Vergelyking van 15 en 23, 15, is kleiner en so dit is ons derde element. Nou vergelyk 16 en 23, 16 is kleiner. So dit is die vierde element. 

Let op dat 2 elemente kom uit dieselfde lys in 'n ry. Dit is waarom die saamgesmelte lys kan nie net alternatiewe elemente van die 2 lyste. Vergelyking van 50 en 23, 23 is kleiner, so ons kies dat. Tussen 50 en 42, 42 is kleiner. Tussen 50 en 108, 50 is kleiner. En, uiteindelik, ons moet net 108, so dit moet gaan op die einde van die lys. Let op dat ons het 'n mooi, gesorteerde lys. Elke keer as ons vergelyk met die eerste 2 elemente van die 2 lyste ons was in staat om die volgende element van die saamgesmelte lys te bepaal. Dit beteken dat indien die finale lys bevat N getalle, waar n is hier 8, dan moet ons op die meeste N vergelykings al daardie getalle in die regte plek te kry. So 'n algoritme word gesê in lineêre tyd uit te voer, maar moenie worry nie oor wat hier. 

Die gebruik van ons algoritme vir die kombinering, kan ons 'n vinnige merge soort algoritme. So, laat ons weer ons lyste. Daar is 2 groot stappe in die proses van merge soort. Eerste, voortdurend in twee helftes verdeel die lys van koppies totdat ons het 'n klomp van die lyste met net 1 koppie in hulle. Moenie bekommerd wees as 'n lys bevat 'n onewe getal en jy kan nie 'n volkome skoon sny tussen hulle. Net arbitrêr kies watter lys die ekstra koppie. In te sluit So, laat ons hierdie lyste verdeel. Nou het ons het 2 lyste. Nou het ons het 4 lyste. 

En nou het ons 8 lyste met 'n beker in elke lys. So wat is dit vir stap 1. Vir stap 2, het ons herhaaldelik saamsmelt pare van lyste met behulp van die kombinering algoritme wat ons geleer het. Kombineer 108 en 15, ons eindig met die lys 15, 108. Kombineer 50 en 4, ons eindig met 4, 50. Kombineer 8 en 42, het ons uiteindelik met 8, 42. En samesmelting 23 en 16, het ons uiteindelik met 16, 23. Nou al ons lyste is van grootte 2. Let daarop dat elk van die 4 lyste is gesorteer. 

Sodat ons kan begin met die samesmelting weer pare van lyste. Kombineer 15 en 108 en 4 en 50 - die eerste maal in die 4, dan is die 15, dan is die 50, dan is die 108. Kombineer 8, 42 en 16, 23, neem ons die eerste keer die 8, dan is die 16, dan 23, dan is die 42. So nou het ons net 2 lyste van grootte 4, wat elk gesorteer. So nou het ons saamsmelt hierdie 2 lys. Eerstens neem ons die 4. Dan neem ons die 8. Dan neem ons die 15 en 16, dan 23, dan 42, dan 50, dan is 108. En ons klaar is. Ons het nou 'n gesorteerde lys. So hoe vinnig was dit presies? In tegniese terme, merge soort is O (n log n), terwyl al borrel soort, invoeging soort, en seleksie soort is O (n ²). In werklikheid, as jy sal gou leer, sal jy nie in staat wees om vorendag te kom met 'n soort wat presteer beter as O (n log n) in die algemene geval. Weereens, moenie bekommerd wees oor hierdie groot-O notasie as jy dit nog nie gesien het nie. 

Weet net dat dit beteken as ons wou 'n baie groot lys te sorteer borrel soort, invoeging soort en die seleksie soort kan potensieel aansienlik langer as saamsmelt soort. Dit beteken nie dat merge soort sal vinniger wees vir alle lyste of selfs vir 'n enkele lys onder 'n sekere grootte. Byvoorbeeld, invoeging soort die vinnigste soort vir alle lyste kleiner as 5 elemente. In die praktyk, merge soort is gewoonlik vinniger lyste so klein as 50 elemente. 

Maar hierdie ekstra spoed nie sonder 'n prys gekom. Anders as ons ander vorme, wat 'n lys en die lys in plek te verander totdat ons 'n gesorteerde lys, merge soort moet 'n paar ekstra ruimte 2 lyste saam te smelt. Ons kan nie dadelik gebruik om die lyste wat word saamgevoeg om die saamgesmelte lys te stoor want ons kan oorheers elemente wat nog moet word saamgevoeg. Hierdie ruimte is 'n bietjie van 'n prys, maar dit gewoonlik is nie onredelik nie. En dit is dit vir merge soort. 

My naam is Rob Bowden, en dit is CS50. [CS50.TV] - En seleksie soort. [Lag] O, het ook om uit te neem, want ek oorgeskakel hoe ek dit was die aanbieding. Lys aan die linkerkant. Dit was 'n tikfout. [Misspoke] Ek screwed up - [Lag] Ek weet nie wat -