[Powered by Google Translate] [Spoji Sortiraj] [Rob Bowden - Sveučilište Harvard] [Ovo je CS50. - CS50.TV] Ajmo pričati o spajanja vrste. Do sada ste vidjeli mjehurić vrsta, umetanja sortiranje i odabir vrste. Iako ću vrsta vala moju ruku na što mislim bolje, spojiti vrsta uglavnom obavlja bolje od bilo koje od tih triju vrsta. 

No, prije nego što se govori o spajanja vrste, pričajmo o spajanju dvije sortirane liste. Mi ćemo pozvati proces uzimanja dvije sortirane liste, kao što su ovi, i stvaranje jednog sortirani popis od njih - spajanje popise. Kako možemo to učiniti? Pa, jedan ideja je da se samo držati jedan popis na kraju drugog popisa a zatim sortirati dobivenog popisa. 

Dok to radi, to je puno nepotrebnog posla. Možemo to učiniti brže nego samo sortiranje. Obavijest da je jedan krivo Ideja je da samo uzeti izmjenične šalice sa svake liste. Dok se to može činiti kao da se radi na prvi, događaj koji smo završili s 4, 8, 15, 23, 16 - najave da 16 i 23 su izvan mjesta. To je zato dva elementa koji bi se trebao pojaviti zaredom u pripojenoga popisu su u istom početnom popisu. Oba 15 i 16 su u popisu na lijevoj strani. Trik je iskoristiti činjenicu da su obje liste već su poredani. To znači da, ako mi samo pogledate prvi elementima obje liste - ovdje, 4 i 8 - jedan od njih također mora biti prvi element spojeni popisa. Pa, zašto je to? Obje ove liste već su razvrstani, i tako bilo 4 ili 8 mora biti najmanji element kada smo kombinirati dvije liste. U ovom slučaju, najmanji je 4, tako da možemo uzeti četiri i učiniti ga prvi element naše spojene popisu. Sada ćemo nastaviti spajanjem preostale tri elemente prvog popisa i 4 elementi drugom popisu. 

Opet, trebamo samo gledati na prvom elementu oba popisa. Manji od 2 mora biti drugi element naše spojene popisu. Ovaj put, između 8 i 15 najmanji je osam, i tako smo ubaciti da kao drugi element našeg sortirani popis. Možemo nastaviti uspoređujući prvi elemente oba popisa i uklanjanje manji od 2. Uspoređujući 15 i 23, 15 je manji i da je naš treći element. Sada usporedbom 16 i 23, 16 je manji. Dakle, to je četvrti element. 

Primijetit ćete da dva elementa došao iz istog popisa u nizu. To je razlog zašto je nastao popis ne može samo izmjenjuju elementi iz dvije liste. Uspoređujući 50 i 23, 23 je manji, pa smo odlučili da. Između 50 i 42, 42 je manji. Između 50 i 108, 50 je manji. I, konačno, imamo samo 108, tako da se mora ići na kraju našeg popisa. Primijetit ćete da imamo lijep, sortirani popis. Svaki put kad smo usporedili prvi dvije elemente dvije liste bili smo u mogućnosti kako bi se utvrdilo sljedeći element spojeni popisu. To znači da, ako konačni popis sadrži n brojeva, gdje je n ovdje je 8, onda moramo na većini n usporedbe dobiti sve od tih brojeva u pravo mjesto. Takav algoritam je rekao da se izvoditi u linearnom vremenu, ali ne brinite o tome ovdje. 

Koristeći naš algoritam za spajanjem, možemo napraviti brzo spajanje algoritam sortiranja. Dakle, ajmo ponovno naše liste. Postoje dvije velike korake u procesu spajanja vrste. Prvo, kontinuirano podijeliti popis šalice na polovice dok imamo hrpu liste sa samo jednom šalicom u njima. Ne brinite ako popis sadrži neparan broj i ne možete napraviti savršeno čisti rez između njih. Samo proizvoljno odabrati koji popis uključiti dodatni šalicu u. Dakle, ajmo podijeliti ove liste. Sada imamo dvije liste. Sada imamo četiri liste. 

I sada imamo 8 liste s jednom šalicom u svakom popisu. Dakle, to je to za 1. koraku. Za koraku 2, smo u više navrata spajanje parova popisa pomoću spajanja algoritam smo naučili prije. Stapanje 108 i 15, mi završiti s popisa 15, 108. Stapanje 50 i 4, mi završiti s 4, 50. Spajanje 8 i 42, mi završiti s osam, 42. A spajanjem 23 i 16, mi završiti s 16, 23. Sada svi naši popisi su veličine dva. Primijetite da svaka od 4 lista je razvrstan. 

Dakle, možemo početi spajanjem parova popisima ponovno. Stapanje 15 i 108 i 4 i 50 - najprije od 4, a zatim 15, a zatim 50, a zatim 108. Spajanje 8, 42 i 16, 23, prvo se 8, a zatim 16, zatim 23, zatim 42. Tako sada imamo samo dvije liste veličine 4, od kojih je svaki razvrstani. Dakle, sada smo spojiti ove dvije liste. Najprije smo se 4. Onda smo se osam. Onda smo se 15 i 16, zatim 23, zatim 42, zatim 50, a zatim 108. I mi smo gotovi. Mi sada imamo sortirani popis. Dakle, koliko brzo je to točno? U tehničkom smislu, spajanje vrsta je O (n log n), a sve mjehurića vrste, umetanja sortirati i izbor sortirati su O (n ²). U stvari, kao što ćete saznati uskoro, nećete biti u mogućnosti da se s nekom vrstom koji obavlja bolje od O (n log n) u općem slučaju. Opet, ne brinite o ovom velikom O notaciji, ako niste ga vidjeli još. 

Samo znam da to znači da ako želimo sortirati stvarno velik popis mjehurić vrsta, umetanje vrsta, a izbor vrsta potencijalno mogao uzeti znatno duže od pisama vrsta. To ne znači da je spajanje vrsta će biti brži za sve popise ili čak za jednu popisu pod određenu veličinu. Na primjer, za umetanje vrsta može biti najbrži vrsta za sve popise manje od pet elemenata. U praksi, spajanje vrsta je obično brže za popise kao mali kao 50 elemenata. 

No, ovaj dodatni brzina ne dolazi bez cijene. Za razliku od naših drugih vrsta, koja se popis i mijenjati popis u mjestu dok smo dobili sortiran popis, spajanje vrsta treba neki dodatni prostor spojiti dvije liste zajedno. Mi ne može odmah koristiti popise koje se spojili za pohranu spojene popis jer smo mogli pregaziti elemente koji još uvijek treba spajati. Ovaj prostor je malo cijeni, ali to obično nije nerazumna. I to je to za spajanje vrste. 

Moje ime je Rob Bowden, a ovo je CS50. [CS50.TV] - I odabir vrsta. [Smijeh] Oh, moram poduzeti da se previše jer sam se prebacio kako sam ga predstaviti. Popis na lijevoj strani. To je bila pogreška pri upisu. [Misspoke] ja zeznuo - [Smijeh] Ne znam što -