>> [Muzikos grojimo]
>> Doug LLOYD: Gerai, todėl sujungti Rūšiuoti dar vienas algoritmas
, kad mes galime naudoti norėdami išsiaiškinti Iš masyvo elementai.
Bet, kaip matysime, ji atšoko labai esminis skirtumas
nuo atrankos rūšiuoti, burbulas Rūšiuoti ir įterpimo Rūšiuoti
kad padaryti tai tikrai gana protingas.
>> Pagrindinė idėja suliejimo Rūšiuoti yra rūšiuoti mažesnių masyvai
ir tada sujungti tuos masyvus kartu, arba sujungti them--
taigi ir rūšiuotų kad name--.
Taip, kad sujungti rūšiuoti daro tai nukreipdama įrankį
vadinamas rekursija, o tai, ką mes ketiname kalbėti apie netrukus,
bet mes ne tikrai kalbėjo apie dar.
>> Štai pagrindinė idėja merge rūšiuoti.
Rūšiuoti kairįjį pusę masyvo, darant prielaidą, kad n yra didesnis už 1.
Ir ką aš turiu galvoje, kai aš sakau darant prielaidą, kad n yra didesnis už 1, yra,
Manau, mes galime susitarti, kad jei masyvo sudaro tik vienas elementas,
tai rūšiuojamos.
Mes ne iš tikrųjų reikia nieko daryti su juo.
Mes galime tik pripažinti ją turi būti išspręstos.
Tai tik vienas elementas.
>> Taigi Pseudocode, vėl, yra rūšiuoti kairįjį pusę masyvo,
tada rūšiuoti teisė pusė masyvas, tada sujungti dvi puses kartu.
Dabar jau galite būti galvoju, kad tipo tik
skamba kaip jūs atkalba the-- jūs ne iš tikrųjų ką nors.
Jūs sakote rūšiuoti į kairę pusę, rūšiuoti tinkamą pusę,
bet esate ne pasakoti man, kaip jūs darote.
>> Bet nepamiršti, kad taip ilgai, kaip masyvo yra vienas elementas,
mes galime pripažinti ją rūšiuojami.
Tada mes galime tiesiog sujungti juos kartu.
Ir tai iš tikrųjų pagrindinė idėja merge rūšiuoti,
yra ją padalyti taip, kad Jūsų matricos dydžio vieno.
Ir tada jūs atkurti iš ten.
>> Sujungti Rūšiuoti tikrai sudėtingas algoritmas.
Ir tai taip pat šiek tiek sudėtinga įsivaizduoti.
Taigi tikiuosi, vizualizacija, kad aš turime čia padės jums sekti kartu.
Ir aš pabandyti mano geriausia pasakoti dalykus ir pereikite per tai šiek tiek daugiau
lėtai, nei kitų tie tik tikiuosi gauti savo galvą
aplink atsilieka merge rūšiuoti idėjas.
>> Taigi, mes turi tą patį kaip ir į nustatomas masyvo kiti rūšiavimo algoritmas video
Jei mačiau them-- šešių elementų masyvas.
Ir mūsų Pseudocode kodas čia yra tarsi kairė pusė, rūšiuoti tinkamą pusę,
sujungti dvi puses kartu.
Taigi leiskite pasinaudoti šia labai tamsiai raudonų plytų masyvas ir rūšiuoti kairįjį pusę jo.
>> Taigi šiuo metu, mes ketiname ignoruoti dešinėje stuff.
Tai ten, bet mes ne tame etape dar.
Mes ne rūšiuos teisė pusė masyvo.
Mes ne Rūšiuoti kairėje pusė masyvo.
Ir tik vardan , kad jis turi šiek tiek daugiau
aišku, kad aš galiu kreiptis kas žingsnis mes apie,
Aš ruošiuosi perjungti spalva šio rinkinio į oranžinę.
Dabar, mes vis dar kalbame apie pati kairėje pusėje, pirminio masyvo.
Bet aš tikiuosi, kad galėtų kreiptis į įvairių daiktų spalvas,
jis bus padaryti jį šiek tiek daugiau išvalyti tai, kas vyksta čia.
>> Gerai, kad dabar mes turime trijų elementų masyvas.
Kaip mes rūšiuoti kairėje pusėje, tai masyvo, kuris yra dar šis žingsnis?
Mes stengiamės rūšiuoti į kairę pusė plytinio raudonumo array--
kairė pusė, kuri Aš dabar spalvos oranžinė.
>> Na, mes galime išbandyti ir vėl pakartokite šį procesą.
Taigi mes vis dar viduryje bando rūšiuoti
kairėje pusėje, visiškai masyvo.
Kairėje pusė masyvas, aš tik ketina
savavališkai nuspręsti, kad kairė pusė bus mažesnis nei dešinės pusę,
nes tai atsitinka sudarytas iš trijų dalių.
>> Ir todėl aš ruošiuosi pasakyti, kad kairė pusė kairėje pusėje masyvo
yra tik elementas penki.
Penki, būdamas vienas elementas masyvas, mes žinome, kaip rūšiuoti.
Ir taip penkis rūšiuojamos.
Mes tik ketina paskelbti, kad.
Tai vienas elementas masyve.
>> Taigi dabar mes surūšiuoti kairė pusė kairėje half--
arba, tiksliau, mes surūšiuoti kairėje pusėje, oranžinės spalvos.
Taigi, dabar, siekiant dar baigtas į bendrą masyvo kairės pusės pusę,
turime rūšiuoti tinkamą pusę iš apelsinų, ar šios medžiagos.
Kaip mes tai padaryti?
Na, mes turime dvi elementų masyvas.
Taigi, mes galime rūšiuoti kairįjį pusę masyvo, kuris yra du.
Du yra vienas elementas.
Taigi jis rūšiuojami pagal nutylėjimą. Tada mes galime rūšiuoti tinkamą pusę
tos masyvo, pavaizduoto porcijoje.
Tai tarsi pagal nutylėjimą.
>> Šiuo metu tai yra pirmą kartą mes pasiekėme suliejimo žingsnį.
Baigėme, nors mes dabar rūšies įdėtos down--
ir tai tarsi keblus dalykas su Rekursija yra
Jums reikės išlaikyti savo galvą apie tai, kur mes esame.
Taigi mes tarsi kairėje pusė apelsinų porcijoje.
>> Ir dabar, mes vidury rūšiavimas teisę pusė apelsinų porcijoje.
Ir tame procese, mes esame dabar ketinate būti žingsnis,
sujungti dvi puses kartu.
Kai pažvelgiame į dvi dalis masyvo, matome du ir vienas.
Kuris elementas yra mažesnis?
Vienas.
>> Tada kuris elementas yra mažesnis?
Na, tai dviejų ar nieko.
Taigi, tai du.
Taigi, dabar, tik dar kartą rėmo kur mes esame kontekste,
mes surūšiuoti kairė pusė apelsino
ir teisę pusė kilmės.
Aš žinau, aš pasikeitė spalvas vėl, bet tai kur mes buvome.
Ir aš priežastis tai padarė yra todėl, kad šis procesas yra
ketina nesustoti, Iteracja žemyn.
Mes rūšiuojami į kairę pusė buvusios oranžinė
ir teisę pusė buvusios oranžinės spalvos.
>> Dabar, mes turime sujungti tuos dvi dalis kartu per daug.
Štai žingsnis mes apie.
Taigi, mes apsvarstyti visus elementai, kurie dabar žalia,
kairėje pusėje, pirminio masyvo.
Ir mes sulieti tuos naudojant tą patį procesą
mes padarėme sujungimo du ir prieš tik vienas momentas.
>> Kairėje pusę, mažiausias elementas kairėje pusėje yra penki.
Mažiausias elementas teisė pusė yra vienas.
Kuris iš jų yra mažesnė?
Vienas.
>> Mažiausias elementas kairė pusė yra penki.
Mažiausias elementas teisė pusė yra du.
Kas yra mažiausia?
Du.
Ir tada galiausiai penkių nieko, mes galime pasakyti, penki.
>> Gerai, kad Big Picture, tegul atsipūsti sekundę
ir išsiaiškinti, kur mes esame.
Jei mes pradėjome nuo Pačioje pradžioje mes
jau baigtas bendras masyvas tik
vienas žingsnis Pseudocode kodas čia.
Mes surūšiuoti kairė pusė masyvo.
>> Prisiminkite, kad originalus Kad buvo penki, du, vienas.
Išgyvena šį procesą ir lizdus žemyn ir kartoti,
toliau pertrauka problemą žemyn į mažesnes dalis,
mes jau baigė vieną iš Pseudocode žingsnis
už visą atskaitos masyvo.
Mes rūšiuojami savo kaire puse.
>> Taigi dabar galime užšaldyti ten.
O dabar tegul rūšiuoti teisę pusė pradinio masyvo.
Ir mes ketiname daryti, kad išgyvena tą patį kartotinis
procesas kad dalykų žemyn ir tada sujungti juos kartu.
>> Taigi kairė pusė raudona, arba yra kairėje pusėje
iš dešinės pusės originalo masyvas, aš ruošiuosi pasakyti trys.
Vėlgi, aš vis nuoseklūs čia.
Jei turite nelyginis skaičius elementų, ją
tikrai ne klausimas, ar jums padaryti liko vienas mažesnis
arba vienas teisingas mažesnis.
>> Svarbu tai, kad, kai jūs susiduriate su šia problema vykdant
Sujungimas, jūs turite būti nuoseklūs.
Jūs arba visada reikia padaryti kairėje pusėje mažesnis
ar visada reikia padaryti dešinėje pusėje mažesnis.
Čia, aš pasirinko, kad visada padaryti kairėje pusėje mažesnis
kai mano masyvas, ar mano Sub-masyvas, yra nelyginis dydžio.
>> Trys yra vienas elementas, ir todėl ji yra rūšiuojami.
Mes skolintomis šią prielaidą per visą mūsų procese iki šiol.
Taigi dabar galime rūšiuoti teisę pusė dešinės pusę,
arba į dešinę pusę raudonos.
>> Vėlgi, mes turime išskaidyti tai žemyn.
Tai ne vienas elementas masyve.
Mes negalime pripažinti ją rūšiuojami.
Ir todėl pirmiausia, mes ketiname rūšiuoti yra kairėje pusėje.
>> Kairysis pusė yra vienas elementas, todėl rūšiuoti pagal nutylėjimą.
Tada mes ketiname rūšiuoti teisę pusė, kuri yra vienas elementas.
Tai rūšiuojami pagal nutylėjimą. Ir dabar, mes galime sujungti šių dviejų kartu.
Keturių yra mažesnis, ir Tada šeši yra mažesnis.
>> Vėlgi, ką mes padarėme šiuo metu?
Mes rūšiuojami į kairę pusė dešinės pusę.
Arba grįžta į originalą spalvos, kad ten buvo,
mes rūšiuojami į kairę pusė minkštesnė raudonai.
Iš pradžių buvo tamsiai plytų raudona ir dabar tai minkštesnė raudona,
ar tai buvo minkštesnė raudona.
>> Ir tada mes surūšiuoti teisė pusė minkštesnė raudona.
Dabar gerai, jie žali dar kartą, tik nes mes ketiname per procesą.
Ir mes turime kartoti ir per šį daugiau.
>> Taigi, dabar mes galime sujungti tuos dvi dalis kartu.
Ir tai, ką mes darome čia.
Taigi juoda linija tiesiog suskirstyti kairįjį pusę
ir teisė pusė šios rūšies dalis.
>> Mes lyginame mažiausią vertę kairėje pusėje array--
arba atsiprašau, mažiausias vertė kairės pusę
mažiausiam vertės dešinę pusę ir rasti, kad trys yra mažesnis.
Ir dabar, kai jos buvo optimizuoti tiek, tiesa?
Yra tikrai nieko paliktas kairėje pusėje.
>> Nėra nieko likę kairėje pusėje,
todėl mes galime efektyviai tik move-- mes galime paskelbti
likusios yra iš tikrųjų rūšiuojamos ir tik smeigtuko ją
apie, nes nėra nieko dar palyginti prieš.
Ir mes žinome, kad dešinė pusė iš dešinės pusės yra rūšiuojami.
>> Gerai, kad dabar galime užšaldyti ir vėl išsiaiškinti, kur mes esame į istoriją.
Bendroje masyvas, Ką mes pasiekiama?
Mes iš tikrųjų pasiekti dabar vienas ir žingsnis dviem etapais.
Mes rūšiuojami yra kairėje pusėje, o surūšiuota tinkamą pusę.
>> Taigi dabar belieka mums sujungti šias dvi puses kartu.
Taigi mes palyginti žemiausias vertinami elementas kiekvieno masyvo pusėje
savo ruožtu ir toliau.
Vienas iš jų yra mažesnis kaip trys, taip, vienas eina.
>> Du yra mažesnis kaip trys, taip, du eina.
Trys yra mažesnis nei 5, todėl trijų eina.
Keturi yra mažesnis nei 5, todėl keturių eina.
Tada penki yra mažesnis nei šešių, šeši yra viskas, išlieka.
>> Dabar, aš žinau, kad buvo daug žingsnių.
Ir mes palikome daug atminties mūsų tinklą.
Ir tai, ką tie pilki kvadratėliai.
Ir tai tikriausiai jaučiau, kad paėmė daug ilgiau nei įterpimo rūšiuoti, burbulas
Rūšiuoti arba atranka rūšiuoti.
>> Bet iš tikrųjų, nes daug iš šių procesų
vyksta tuo pačiu LAIKĄ_ kuri yra kažkas, mes vėl
kalbėti apie kai kalbame apie rekursija į ateitį video--
Šis algoritmas iš tikrųjų aiškiai yra iš esmės
kitoks, nei nieko mes matėme prieš
bet taip pat yra žymiai efektyviau.
>> Kodėl taip yra?
Na, blogiausiu scenarijaus atveju, mes turime
padalinti n elementų iki ir tada rekombinuoja juos.
Bet kai mes rekombinuoja jiems, ką mes darome
iš esmės dubliuoti dydis iš mažesnių matricos.
Mes turime vieno elemento krūva masyvai, kad mes iš tikrųjų
sujungti į dvi elementų matricos.
Ir tada mes tie du elementas masyvai
ir sujungti juos kartu į keturi element matricas ir tt,
ir taip toliau, ir taip toliau, kol mes turėti vieną n elementų masyvas.
>> Bet kiek dubliavimǐ užtrunka gauti n?
Pagalvokite atgal į telefonų knygos pavyzdyje.
Kiek kartų mes turime ašara telefonų knyga per pusę, kiek daugiau
kartų mes turime ašara telefono knyga per pusę, jei telefono knygos dydis
dvigubai?
Yra tik vienas, tiesa?
>> Taigi ten kažkokia logaritminė elementas čia.
Tačiau mes taip pat dar turi bent ieškoti visi n elementų.
Taigi, blogiausiu atveju, sujungti rūšiuoti veikia n log n.
Mes turime pažvelgti į visi n elementų,
ir mes turime juos sujungti kartu log n rinkinių žingsnius.
Geriausiu atveju, masyvas puikiai rūšiuojami.
Tai puiku.
Tačiau remiantis algoritmu mes čia, mes vis dar turime išskaidyti ir rekombinuoja.
Nors šiuo atveju, apsauginio apvalkalo rūšies neveiksmingas.
Tai nėra būtinas.
Bet mes vis dar eiti per visas procesas vistiek.
>> Taigi geriausiu atveju o blogiausiu atveju,
Šis algoritmas veikia n log n metu.
Sujungti Rūšiuoti tikrai tiek sudėtingesnis nei kitų pagrindinių rūšiavimo algoritmų
mes kalbėjome apie CS50 bet gerokai galingesnis.
>> Ir todėl, jei jūs kada nors rasti proga reikia
arba naudoti jį rūšiuoti didelė duomenų rinkinys, gauti
jūsų galva aplink rekursijos idėjos bus tikrai galingas.
Ir jis ketina padaryti jūsų programos tikrai yra daug veiksmingiau
naudojant sujungti rūšiuoti palyginti kas nors kitas.
Aš Doug Lloyd.
Tai CS50.