[Powered by Google Translate] [Flett Sorter] [Rob Bowden - Harvard University] [Dette er CS50. - CS50.TV] La oss snakke om sammenslåing slag. Så langt du har sett boble sortere, innsetting sortere og utvalg slag. Selv om jeg vil slags bølge min hånd på hva jeg mener med bedre, flette slags utfører generelt bedre enn noen av disse tre slag. 

Men før du snakker om fletting sortere, la oss snakke om sammenslåing to sorterte lister. Vi kaller prosessen med å ta to sorterte lister, som disse, og lage en enkelt sortert liste ut av dem - sammenslåing listene. Hvordan kan vi gjøre dette? Vel, er en idé å bare holde en liste på enden av den andre listen og deretter sortere listen som åpnes. 

Selv om dette fungerer, er det mye unødvendig arbeid. Vi kan gjøre det raskere enn bare sortering. Legg merke til at en feil idé er å bare ta vekslende kopper fra hver liste. Selv om det kan virke som det fungerer i begynnelsen, gjør at vi ender opp med 4, 8, 15, 23, 16 - legg merke til at 16 og 23 er malplassert. Dette er fordi to elementer som skal vises på rad i det fusjonerte liste er i samme opprinnelige listen. Både 15 og 16 er i listen til venstre. Trikset er å dra nytte av det faktum at begge listene er allerede sortert. Dette betyr at hvis vi bare ser på de første elementene i begge listene - her, 4 og 8 - må en av dem også være den første del av det fusjonerte listen. Vel, hvorfor er det? Begge disse listene er allerede sortert, og så enten 4 eller 8 må være den minste element når vi kombinerer to listene. I dette tilfellet, er det minste 4, slik at vi kan ta ut 4 og gjøre det første elementet i vår fusjonerte liste. Nå fortsetter vi å flette de resterende 3 elementer av den første listen og 4 deler av den andre listen. 

Igjen, vi trenger bare å se på det første elementet i begge listene. Den minste av de to må være det andre elementet av vårt fusjonerte liste. Denne tid, mellom 8 og 15 den minste er 8, og så vi setter at som det andre element av vårt sorterte listen. Vi kan fortsette å sammenligne de første elementene av begge listene og fjerne den minste av to. Sammenligning 15 og 23, 15 er mindre og slik at det er vår tredje element. Nå sammenligne 16 og 23, 16 er mindre. Så det er det fjerde elementet. 

Legg merke til at to elementer kom fra samme liste i en rad. Dette er grunnen til at det fusjonerte listen kan ikke bare alternative elementer fra de 2 listene. Sammenligning 50 og 23, 23 er mindre, så vi velger det. Mellom 50 og 42, er 42 mindre. Mellom 50 og 108, er 50 mindre. Og, til slutt, vi må bare 108, så det må gå på slutten av vår liste. Legg merke til at vi har en fin, sortert liste. Hver gang vi sammenlignet de 2 første elementene i de 2 listene vi var i stand til å bestemme den neste element av det flettede listen. Dette betyr at hvis den endelige listen inneholder n antall, hvor n her er 8, da trenger vi høyst n sammenligninger for å få alle disse tallene inn på rett sted. Slikt algoritme sies å kjøre i lineær tid, men ikke bekymre deg om det her. 

Ved å bruke vår algoritme for sammenslåing, kan vi gjøre en rask sammenslåing slags algoritme. Så, la oss tilbakestille våre lister. Det er 2 store skritt i prosessen med sammenslåing slag. Først, kontinuerlig delt listen over kopper i halvdeler før vi har en haug med lister med bare en kopp i dem. Ikke bekymre deg hvis en liste inneholder et oddetall og du ikke kan gjøre en perfekt rent kutt mellom dem. Bare vilkårlig velge hvilke listen for å inkludere ekstra kopp i. Så, la oss dele disse listene. Nå har vi to lister. Nå har vi fire lister. 

Og nå har vi åtte lister med én kopp i hver liste. Så det er det for trinn 1. For trinn 2, vi gjentatte ganger slå parene av lister ved hjelp av flettingen algoritmen vi lært før. Sammenslåing 108 og 15, ender vi opp med listen 15, 108. Sammenslåing 50 og 4, ender vi opp med 4, 50. Sammenslåing 8 og 42, ender vi opp med 8, 42. Og sammenslåing 23 og 16, ender vi opp med 16, 23. Nå er alle våre lister er av størrelse 2. Legg merke til at hver av de fire lister er sortert. 

Så kan vi begynne å flette par lister igjen. Sammenslåing 15 og 108 og 4 og 50 - først ta 4, deretter 15, deretter 50, deretter 108. Flette 8, 42 og 16, 23, vi først ta 8, deretter 16, deretter 23, deretter 42. Så nå har vi bare to lister over størrelsen 4, som hver sortert. Så nå er vi slå sammen disse to listene. Først tar vi 4. Så tar vi den 8. Da vi ta 15 og 16, deretter 23, deretter 42, deretter 50, deretter 108. Og vi er ferdige. Vi har nå en sortert liste. Så hvor fort dette var, egentlig? I tekniske termer, er merge slags O (n log n), mens alle boble sortere, innsetting sortere og utvalg slag er O (n ²). Faktisk, som du vil lære snart, vil du ikke være i stand til å komme opp med en slags som utfører bedre enn O (n log n) i det generelle tilfellet. Igjen, ikke bekymre deg for dette store O notasjon hvis du ikke har sett den ennå. 

Bare vet at dette betyr at hvis vi ønsket å sortere en virkelig stor liste boble sortere, innsetting sortere og utvalg slags potensielt ta betydelig lengre enn flette slag. Det betyr ikke at flettingen type vil være raskere for alle lister eller selv for en enkelt liste under en viss størrelse. For eksempel kan innsetting sortere være den raskeste slag for alle lister mindre enn 5 elementer. I praksis er merge slags regel raskere for lister så små som 50 elementer. 

Men denne ekstra hastigheten ikke kommet uten en pris. I motsetning til våre andre former, som tar en liste og endre listen på plass inntil vi får en sortert liste, trenger merge sortere litt ekstra plass å fusjonere to listene sammen. Vi kan ikke umiddelbart bruke listene som blir slått sammen til å lagre det sammenslåtte liste siden vi kan overstyre elementer som fortsatt trenger å bli slått sammen. Denne plassen er litt av en pris, men det er vanligvis ikke urimelig. Og det er det for flettingen slag. 

Mitt navn er Rob Bowden, og dette er CS50. [CS50.TV] - Og valg slag. [Ler] Oh, fikk til å ta det ut også fordi jeg byttet hvordan jeg presentere det. Listen til venstre. Det var en skrivefeil. [Misspoke] Jeg skrudd opp - [Ler] Jeg vet ikke hva -