[Glazbom] 

Doug LLOYD: U redu, tako da spajanje vrsta je još jedan algoritam koje možemo koristiti kako bi se riješili elementi niz. No, kao što ćemo vidjeti, to je dobio Vrlo temeljna razlika od odabira vrste, mjehura sortiranje i umetanje sortiranje da bi to stvarno prilično pametan. 

Osnovna ideja spajanja sorta je razvrstati manjih polja a zatim kombinirati one polja zajedno, ili spojiti them-- stoga name-- u sortiranog bi. Način na koji spajaju vrsta ne to utjecati alat zove rekurzija, što je ono ćemo govoriti o uskoro, ali nismo stvarno razgovarali o još. 

Evo Osnovna ideja spajanje vrste. Sortiraj lijevu polovicu polja, uz pretpostavku da je n veći od 1. A što mislim kad kažem uz pretpostavku da je n veći od 1 je, Mislim da se možemo složiti da ako niz Samo se sastoji od jednog elementa, to je riješeno. Mi zapravo ne treba ništa učiniti za njega. Mi samo možemo izjaviti da se sortirati. To je samo jedan element. 

Tako je pseudokod, opet, sortirati utakmice pola polja, zatim sortirati pravo pola niz, zatim spojiti dvije polovice zajedno. Sada, već da bi moglo biti razmišljanja, ona vrsta samo Zvuči kao da ste stavljanjem off the-- niste zapravo radi ništa. Kažeš sortirati lijevu pola, sortiranje desnu polovicu, ali ne govoriš mi kako to radite. 

Ali zapamtite da dokle god niz je jedan element možemo proglasiti razvrstani. Onda mi samo možemo ih povezati. I to je zapravo Temeljna ideja spajanje vrste, je da ga razbiti tako da Vaši polja su veličine jednog. I onda se obnoviti od tamo. 

Spajanje vrsta definitivno kompliciran algoritam. I to je također malo komplicirano vizualizirati. Dakle, nadamo se, vizualizacija da sam imamo ovdje će vam pomoći pratiti zajedno. I ja ću probati moj najbolji pripovijedati stvari i nastavite kroz to malo više Polako od ostalih samo nadam da bi dobili svoju glavu oko ideje iza pisma vrste. 

Dakle, imamo isti niz kao ostali sortiranje algoritam videa ako ste vidjeli them-- niz od šest elemenata. I naš pseudokod broj ovdje je vrsta lijeva polovica, sortiranje desnu polovicu, spojiti dvije polovice zajedno. Tako ćemo iskoristiti ovu vrlo tamno crvenosmeda polje i sortirati utakmice pola od toga. 

Tako za sada, idemo ignorirati stvari na desnoj strani. To je bilo, ali smo Nije na još taj korak. Nismo na sortirati Pravo polovice polja. Mi smo na kakve lijevo polovica polja. I samo zbog da bude malo više jasno, tako da mogu odnositi na ono što je korak smo na, Idem za prebacivanje Boja ovog skupa na naranče. Sada, mi još uvijek govorimo o Isto lijeve polovice izvornog polja. Ali ja sam u nadi da će se moći odnose na boje raznih predmeta, to će učiniti malo više jasno što se ovdje događa. 

U redu, tako da sada imamo tri elementa polje. Kako sortirati lijevoj polovici ove niz, što je još uvijek taj korak? Pokušavamo riješiti lijevu pola cigle crvene array-- kojih lijevu polovicu Sada sam obojen narančasto. 

Pa, mogli bismo pokušati ponovite ovaj postupak ponovno. Dakle, mi smo još uvijek u Sredina pokušava riješiti lijeva polovina cijelog niza. Lijeva polovica niz, ja samo idem samovoljno odluče da je lijeva polovica će biti manji od desnoj polovici, jer ovo se događa sastoji se od tri elementa. 

I tako ću reći da je lijeva polovica lijeve polovice polja je samo element pet. Pet, kao jedan element niz, znamo kako to riješiti. I tako pet je riješeno. Mi samo će izjaviti da. To je jedan element matrice. 

Dakle, sada smo razvrstani lijeva polovica lijeve half-- odnosno, da smo razvrstani lijeva polovica naranče. Tako sada, kako bi se još uvijek potpuna ukupnu Array lijeva polovica, moramo sortirati desnu polovicu od naranče, ili ove stvari. Kako ćemo to učiniti? Pa, imamo dva elementa niza. Tako možemo sortirati utakmice polovicu od polja, koje je dva. Dva je jedan element. Dakle, to je razvrstani po defaultu. Tada možemo sortirati desnu polovicu tog dijela polja, na jedan. To je vrsta po defaultu. 

Ovo je sada prvi put smo dostigli pisma korak. Mi smo završili, iako mi smo sada vrsta ugniježđena down-- i to je vrsta lukav stvar s rekurzije je, morate držati tvoj glavu o tome gdje smo. Dakle, mi smo vrsta lijevo polovica narančastog dijela. 

I sada, mi smo u sredini sortiranja pravo pola naranče dijela. I u tom procesu, mi smo sada o biti na korak, spojiti dvije polovice zajedno. Kada gledamo dvije polovice od polja, vidimo dva i jedan. Koji element je manji? Jedna. 

Zatim element koji je manji? Pa, to je dva ili ništa. Tako da je dva. Tako sada, samo da bi ponovno uokviriti gdje smo u kontekstu, smo razvrstani lijeva polovica naranče i pravo polovica podrijetla. Znam da sam promijenio boje opet, ali to je gdje smo bili. A razlog zbog kojeg sam to učinio je zato taj proces je ide dalje, iterating dolje. Mi smo razvrstani lijevu pola bivše naranče i pravo na pola bivše naranče. 

Sada trebamo spojiti one dvije polovice zajedno previše. To je korak smo na. Tako smo u obzir sve elementi koji su sada zeleni, lijeve polovice izvornog polja. A mi spojiti one koristeći isti postupak što smo učinili za spajanje dva a jedan samo trenutak prije. 

Lijeva polovica, najmanji Element na lijevoj polovici je pet. Najmanji element na pravo na pola je jedan. Koji od njih je manje? Jedna. 

Najmanji element na lijeva polovica je pet. Najmanji element na pravo na pola je dva. Što je najmanji? Dva. A onda na kraju pet i ništa, možemo reći pet. 

U redu, tako da velika slika, neka je Odmorite se na sekundu i shvatiti gdje smo. Ako smo krenuli od samog početka, mi sada završeno za ukupna niz jednostavno jedan korak od pseudokod kod ovdje. Mi smo razvrstani lijeva polovica polja. 

Sjetite se da je izvorna Kako bi bilo pet, dva, jedan. Do prolazi kroz taj proces i gnijezde se i ponavlja, nastavlja razbiti problem u manje i manje dijelove, sada smo završili jedan korak od pseudokod za cijelu početnu polje. Mi smo razvrstani svoju lijevu polovicu. 

Dakle, sada ćemo zamrznuti tamo. A sada ćemo sortirati pravo polovice izvornog polja. I mi ćemo učiniti da se prolazi kroz iste iterativni Proces razbijanje stvari dolje a zatim ih spajaju. 

Tako je lijeva polovica crvena ili lijevu polovicu desne polovice izvornika niz, ja ću reći je tri. Opet, ja sam se ovdje dosljedna. Ako imate neparan broj elemenata je, zapravo ne bitno da li napravite lijevo jedna manja ili pravo jedan manji. 

Ono što je važno je da kad god sastati ovaj problem u provođenju do pripajanja, morate biti dosljedni. Ili uvijek treba napraviti lijeva strana manja ili uvijek je potrebno napraviti desna strana manja. Evo, ja sam izabrao da se uvijek napraviti lijevoj strani manji kad je moj red, ili moja pod-polje, je od neparnog veličine. 

Tri je jedan element i tako je riješeno. Mi smo utjecati da pretpostavka tijekom cijelog našeg procesa dosad. Dakle, sada ćemo sortirati pravo pola desne polovice, ili pravo polovica crvene. 

Opet, moramo podijeliti ovaj dolje. Ovo nije jedan element matrice. Ne možemo proglasiti razvrstani. I tako prvi put, idemo sortirati lijevu polovicu. 

Lijeva polovica je jedan element tako da je nekako po defaultu. Onda ćemo razvrstati pravo polovica, što je jedan element. To je razvrstani po defaultu. A sada, možemo spojiti ta dva zajedno. Četiri je manji, a zatim šest manji. 

Opet, ono što smo učinili u ovom trenutku? Mi smo razvrstani lijevu pola desne polovice. Ili ide natrag u izvorniku Boje koje su tamo, smo razvrstani lijevu pola mekše crveno. To je izvorno tamno cigla crvene i sada je mekši crvena, ili je to bio blaži crveno. 

A onda smo razvrstani Pravo pola mekše crveno. Sada, dobro, oni su zeleni opet, samo jer idemo kroz proces. I moramo ponoviti to više i više. 

Tako sada možemo spojiti one dvije polovice zajedno. I to je ono što mi radimo ovdje. Dakle crne linije samo podijeliti lijevu polovicu a pravo pola ove vrste dijelu. 

Uspoređujemo najmanju vrijednost na lijevoj strani array-- ili me ispričajte, najmanji vrijednost lijeve polovice na najmanju vrijednost prava pola i da tri manja. A sada malo o optimizaciji, zar ne? Tu je zapravo ništa lijevo na lijevoj strani. 

Nema ništa preostalo na lijevoj strani, tako da mogu učinkovito Samo move-- možemo proglasiti ostalo od njega je zapravo razvrstani i samo ga tack na, jer nema ništa drugo za usporedbu protiv. A mi znamo da je desna strana desne strane je riješeno. 

U redu, tako da sada idemo opet i zamrzavanje shvatiti gdje smo u priči. U ukupnom nizu, Što smo postigli? Mi zapravo smo ostvarili Sada korake jedan i dva koraka. Razvrstani smo lijevu polovicu, a smo razvrstani desnu polovicu. 

Pa sada, sve što ostaje za nas spojiti te dvije polovice zajedno. Dakle, usporedimo najniža vrijednosti element svake polovice polja pak i nastaviti. Jedan od njih je manje od tri, tako da jedan ide. 

Dva manja od tri, pa dvije ide. Tri je manji od 5, pa tri ide. Četiri je manji od 5, pa četiri prolazi. Tada pet je manji od šest, a šest je sve što je ostalo. 

Sad, znam da je puno koraka. A mi smo ostavili puno memorije u našem probuditi. I to je ono što ti sive trgovi. I to je vjerojatno osjećao kao da je uzeo puno više od unosa vrsta, mjehurić vrsta, ili odabir vrsta. 

Ali zapravo, jer Puno tih procesa se događa u isto time-- što je nešto što ću, opet, razgovarati o tome kada govorimo o rekurzija u budućnosti video-- Ovaj algoritam zapravo jasno je iz temelja drugačije od svega smo vidjeli ali je također značajno učinkovitije. 

Zašto je to? Pa, u najgore scenarij, imamo podijeliti n elemenata gore a zatim ih recombine. No, kada smo se nanovo ih, što radimo u osnovi je udvostručenje Veličina manjih polja. Imamo hrpu jednog elementa nizovi koje smo uspješno kombinirati u dva elementa polja. I onda uzmemo one dva elementa polja i kombinirati ih zajedno u Četiri elementa polja, i tako dalje, i tako dalje, i tako dalje, sve dok ne n imaju jedan element matrice. 

Ali koliko podvostručenja je potrebno da bi se n? Razmislite ponovno u imenik primjer. Koliko puta smo do suza telefonski imenik na pola, koliko više puta moramo suza telefonski imenik na pola, ako je veličina imeniku udvostručila? Postoji samo jedan, zar ne? 

Dakle, postoji neka vrsta logaritamska elementa ovdje. Ali, mi također još uvijek imaju najmanje pogledajte sve n elemenata. Dakle, u najgorem slučaju, spojiti vrsta radi u n log n. Moramo pogledati sve n elemenata, i moramo ih kombinirati zajedno u zapisniku n stubišta. U najboljem slučaju, Niz je savršeno razvrstani. To je odlično. No, na temelju algoritma imamo ovdje još moramo podijeliti i rekombinaciju. Iako je u ovom slučaju, rekombiniranje je vrsta nedjelotvornim. To nije potrebno. Ali mi još uvijek prolaze cijeli proces svejedno. 

Dakle, u najboljem slučaju au najgorem slučaju, Ovaj algoritam radi u n log n puta. Spajanje vrsta je definitivno nešto složenije od ostalih glavnih sortiranja algoritama smo razgovarali o CS50, ali je znatno moćniji. 

I tako, ako ste ikada pronaći prigoda za to je potrebno ili ga koristiti za sortiranje Veliki podaci skup, uzimajući glavu oko ideje rekurzije će biti jako moćna. I to će učiniti vaš Programi stvarno mnogo učinkovitiji pomoću spajanja vrsta u odnosu na bilo što drugo. Ja sam Doug Lloyd. Ovo je CS50.