[Powered by Google Translate] [Sammanfoga Sortera]
[Rob Bowden - Harvarduniversitetet]
[Detta är CS50. - CS50.TV]
Låt oss tala om sammanslagning slag.
Hittills har du sett bubbla sortera, införande sortera och välja sortera.
Även om jag ska typ av våg min hand på vad jag menar med bättre,
samman Sortera presterar generellt bättre än någon av dessa 3 slag.
>> Men innan jag talar om sammanslagning sortera, låt oss tala om sammanslagning 2 sorterade listor.
Vi ringer processen att ta 2 sorterade listor, som dessa,
och göra en enda sorterad lista av dem - sammanslagning av listorna.
Hur kan vi göra det?
Tja, är en idé att bara sticka en lista på slutet av den andra listan
och sedan sortera det resulterande listan.
>> Även om detta fungerar, det är en hel del onödigt arbete.
Vi kan göra det snabbare än att bara sortera.
Lägg märke till att en felaktig uppfattning är att bara ta alternerande koppar från varje lista.
Även om det kan verka som det fungerar i början,
gör att vi slutar med 4, 8, 15, 23, 16 - märker att 16 och 23 är på sin plats.
Detta beror på att 2 element som ska visas i rad i den sammanslagna listan
är i samma ursprungliga listan.
Både 15 och 16 finns i listan till vänster.
Tricket är att dra nytta av det faktum att båda listorna redan är sorterade.
Det innebär att om vi bara ser på de första delarna av båda listorna -
Här, 4 och 8 - måste en av dem vara också den första delen av det sammanslagna listan.
Tja, varför är det?
Båda dessa listor är redan sorterade,
och så antingen 4 eller 8 måste vara det minsta elementet när vi kombinerar de 2 listorna.
I detta fall är den minsta 4,
så att vi kan ta ut 4 och göra det den första delen av vår sammanslagna lista.
Nu fortsätter vi att slå samman de återstående 3 element i den första listan
och 4 element i den andra listan.
>> Återigen behöver vi bara titta på den första delen av båda listorna.
Den mindre av de 2 skall vara den andra delen av vår sammanslagna lista.
Den här gången, mellan 8 och 15 den minsta är 8, så vi sätter att
som den andra delen av vår sorterade listan.
Vi kan fortsätta att jämföra de första delarna av båda listorna
och avlägsnande av mindre av 2.
Jämföra 15 och 23, 15 är mindre och så det är vår tredje elementet.
Nu jämföra 16 och 23, 16 är mindre.
Så det är det fjärde elementet.
>> Observera att 2 delar kom från samma lista i en rad.
Det är därför det sammanslagna listan kan inte bara alternativa element från 2 listor.
Jämföra 50 och 23, 23 är mindre, så vi väljer att.
Mellan 50 och 42, är 42 mindre.
Mellan 50 och 108, är 50 mindre.
Och slutligen, vi bara har 108, så det måste gå på slutet av vår lista.
Observera att vi har en fin, sorterad lista.
Varje gång vi jämfört de första 2 delarna av de 2 listorna
vi kunde bestämma nästa del av sammanslagna listan.
Detta innebär att om den slutgiltiga listan innehåller n tal, där n här är 8,
då behöver vi i de flesta n jämförelser för att få alla dessa siffror till rätt plats.
En sådan algoritm sägs att köra i linjär tid,
men oroa dig inte om det här.
>> Med vår algoritm för att slå samman, kan vi göra en snabb merge sort algoritm.
Så, låt oss återställa våra listor.
Det finns 2 stora steg i processen sammanslagning slag.
Först, kontinuerligt dela listan av koppar i halvor
tills vi har ett gäng listor med bara 1 kopp i dem.
Oroa dig inte om en lista innehåller ett udda antal
och du kan inte göra en helt ren snitt mellan dem.
Bara godtyckligt välja vilken lista att inkludera extra kopp i.
Så, låt oss dela dessa listor.
Nu har vi 2 listor.
Nu har vi 4 listor.
>> Och nu har vi 8 listor med en enda kopp i varje lista.
Så det är det för steg 1.
För steg 2, slå ihop vi upprepade par av listor med sammanslagningen algoritmen vi lärt tidigare.
Sammanslagningen av 108 och 15 hamnar vi med listan 15, 108.
Sammanslagningen av 50 och 4 hamnar vi med 4, 50.
Sammanslagningen av 8 och 42, hamnar vi med 8, 42.
Och sammanslagning 23 och 16, hamnar vi med 16, 23.
Nu är alla våra listor är av storlek 2.
Lägg märke till att var och en av de 4 listorna sorteras.
>> Så vi kan börja sammanslagning par av listor igen.
Sammanslagning 15 och 108 och 4 och 50 -
först ta 4, sedan 15, sedan 50, sedan 108.
Sammanfoga 8, 42 och 16, 23,
vi tar först 8, sedan 16, sedan 23, sedan 42.
Så nu har vi bara 2 listor med storlek 4, är var och en sorterad.
Så nu har vi ihop dessa 2 listor.
Först tar vi 4.
Sen tar vi 8.
Då vi tar 15 och 16, sedan 23, sedan 42, sedan 50, sedan 108.
Och vi är klara.
Vi har nu en sorterad lista.
Så hur snabbt var, exakt?
I tekniska termer är sammanslagning Sortera O (n log n),
medan hela bubbla sortera, införande sortera och val Sortera är O (n ²).
I själva verket, eftersom du kommer lära dig snart, kommer du inte att kunna komma med ett slags
som presterar bättre än O (n log n) i det allmänna fallet.
Återigen, oroa dig inte om detta stora O notation om du inte har sett den ännu.
>> Bara vet att detta innebär att om vi ville sortera en riktigt stor lista
bubbla sortera, införande sortera och val Sortera skulle kunna ta
betydligt längre än samman sort.
Det betyder inte att merge sort kommer att bli snabbare för alla listor
eller ens för en enskild lista under en viss storlek.
Till exempel kan insättningen Sortera vara den snabbaste Sortera alla listor mindre än 5 element.
I praktiken är merge sort oftast snabbare för listor så små som 50 element.
>> Men denna extra fart kommer inte utan ett pris.
Till skillnad från våra andra slag, som tar en lista och ändra listan på plats
tills vi får en sorterad lista behöver merge sort några extra utrymme
att sammanfoga 2 listor tillsammans.
Vi kan inte omedelbart använda de listor som håller samman för att lagra den sammanslagna listan
eftersom vi kan åsidosätta element som fortfarande behöver slås samman.
Detta utrymme är lite av ett pris, men det brukar inte orimligt.
Och det är det för sammanfogningen sorteringen.
>> Mitt namn är Rob Bowden, och detta är CS50.
[CS50.TV]
- Och urval sortera.
[Skrattar]
Åh, fick ta ut det också eftersom jag bytte hur jag visade upp det.
Listan till vänster. Det var ett stavfel.
[Misspoke] Jag klantade -
[Skrattar]
Jag vet inte vad -