[Muzika] 

DOUG Lloyd: OK, kështu që një merge lloj është edhe një algoritmi që ne mund të përdorni për të zgjidhur elementet e një grup. Por si ne do të shohim, atë e mori një Dallimi themelor shumë nga zgjedhja e renditjes, flluskë lloj, dhe futje lloj që e bëjnë atë të vërtetë goxha i zgjuar. 

Ideja themelore prapa bashkohen lloj është për të zgjidhur vargjeve të vogla dhe pastaj të kombinoni ato vargjeve së bashku, ose shkrihen, porsi kështu name-- në mënyrë renditura. Mënyra se si shkrihet lloj bën kjo është nga leveraging një mjet quajtur Recursion, e cila është ajo ne jemi duke shkuar për të folur për së shpejti, por ne nuk kemi biseduar shumë rreth ende. 

Ja ideja themelore prapa merge lloj. Lloj gjysmën e majtë të vektorit, supozuar n eshte me e madhe se 1. Dhe çfarë dua të them kur them supozuar n eshte me e madhe se 1 është, Unë mendoj se ne mund të bien dakord se në qoftë se një grup vetëm përbëhet nga një element të vetme, është e renditura. Ne nuk mund të vërtetë nevojë të bëjë asgjë për të. Ne vetëm mund ta deklarojë atë të zgjidhet. Kjo është vetëm një element i vetëm. 

Pra pseudokod, përsëri, është e lloj gjysmën e majtë të vektorit, pastaj lloj gjysma e drejtë array, pastaj bashkojë dy gjysmave së bashku. Tani, tashmë ju mund të jetë të menduarit, ai lloj i vetëm tingëllon si ju jeni duke off the-- ju nuk jeni në të vërtetë duke bërë asgjë. Ju jeni duke thënë lloj majtë gjysmë, lloj gjysmën e djathtë, por ju nuk jeni duke u thënë mua se si ju jeni duke bërë atë. 

Por mos harroni se për aq kohë sa një grup është një element të vetme, ne mund ta deklarojë atë të renditura. Atëherë ne mund vetëm të kombinuar ato së bashku. Dhe kjo është në fakt Ideja themelore prapa merge lloji, është që të thyejnë atë poshtë në mënyrë që Vargjeve tuaja janë të një madhësie. Dhe pastaj ju rindërtuar nga atje. 

Merge lloj është padyshim një algorithm komplikuar. Dhe kjo është gjithashtu një pak komplikuar për të kujtoj. Kështu që shpresojmë se, vizualizimi që unë kemi këtu do të ju ndihmojë të ndjekin së bashku. Dhe unë do të përpiqet tim më të mirë për të rrëfej gjëra dhe të vazhdojë me këtë më pak ngadalë se ato e tjera vetëm për shpresë të marrë kokën tuaj rreth ideve prapa merge lloj. 

Pra, ne kemi të njëjtin grup si më të sorting video tjera algorithm në qoftë se ju keni parë, porsi një grup gjashtë element. Dhe kodi ynë pseudokod këtu është lloj gjysmën e majtë, lloj gjysmën e djathtë, bashkojë dy gjysmave së bashku. Pra, le të marrin këtë kuqe shumë të errët tulla array dhe lloj gjysmën e majtë të saj. 

Pra, për momentin, ne jemi duke shkuar të injorojë gjëra në të djathtë. Ajo është aty, por ne jemi jo në atë hap ende. Ne nuk jemi në Lloj gjysma e djathtë e vektorit. Ne jemi në lloj nga e majta gjysma e vektorit. Dhe vetëm për hir për të qenë pak më shumë i qartë, kështu që unë mund të referohen me atë që ne jemi në hap, Unë jam duke shkuar për të kaluar Ngjyra e këtij grupi në portokalli. Tani, ne jemi ende duke folur për njëjtë gjysma e majtë e vektorit origjinale. Por unë jam duke shpresuar se duke qenë në gjendje të referohen ngjyrat e sendeve të ndryshme, ajo do të bëjë atë një pak më shumë të qartë se çfarë po ndodh këtu. 

OK, kështu që tani kemi një tre element array. Si nuk kemi zgjidhur gjysmën e majtë të kësaj grup, i cili është ende ky hap? Ne jemi duke u përpjekur për të zgjidhur majtë gjysma e tulla array-- kuqe gjysma e majtë e të cilave Unë tani e kam me ngjyrë portokalli. 

E pra, ne mund të përpiqemi dhe përsëris këtë proces përsëri. Pra, ne jemi ende në mesme e duke u përpjekur për të zgjidhur gjysma e majtë e koleksion të plotë. Gjysma e majtë të grup, unë jam vetëm duke shkuar për të vendosur në mënyrë arbitrare se gjysma e majtë do të jetë më i vogël se gjysma e duhur, sepse kjo ndodh për përbëhet nga tre elemente. 

Dhe kështu që unë jam duke shkuar për të thënë se gjysma e majtë të pjesës së majtë array është vetëm elementi pesë. Pesë, duke qenë një element i vetëm grup, ne e dimë se si për të zgjidhur atë. Dhe kështu pesë është e renditura. Ne jemi vetëm duke shkuar për të deklaruar se. Është një grup i vetëm element. 

Pra, ne kemi renditur tani gjysma e majtë të half-- majtë ose më mirë, ne kemi renditur gjysma e majtë e portokalli. Deri tani, në mënyrë që ende i plotë gjysma e majtë array Në përgjithësi së, ne kemi nevojë për të zgjidhur gjysmën e djathtë e portokalli, apo këtë stuff. Si e bëjmë këtë? E pra, ne kemi një koleksion të dy element. Pra, ne mund të lloj gjysmën e majtë i vektorit, e cila është e dy. Dy është një element i vetëm. Pra, është e renditura nga default. Atëherë ne mund të lloj gjysmën e djathtë e asaj pjese të array, atij. Kjo është lloj i by default. 

Kjo tani është hera e parë ne kemi arritur një hap të bashkohen. Ne kemi përfunduar, edhe pse ne jemi tani lloj i mbivendosur down-- dhe kjo është lloj i ndërlikuar gjë me recursion është, ju duhet të mbani tuaj kreu për ku jemi. Pra, ne kemi lloj të majtë gjysma e pjesës portokalli. 

Dhe tani, ne jemi në mes të sorting gjysma e djathtë e pjesës portokalli. Dhe në këtë proces, ne jemi tani gati të jetë në hap, bashkojë dy gjysmave së bashku. Kur ne shikojmë në dy gjysmave e grup, ne shohim dy dhe një të tillë. Cili element është më i vogël? Një. 

Atëherë cili element është më i vogël? E pra, kjo është dy ose asgjë. Pra, kjo është dy. Deri tani, vetëm të formojë përsëri ku ne jemi në kontekst, ne kemi renditura gjysma e majtë e portokalli dhe gjysma e djathtë e origjinës. Unë e di unë kam ndryshuar ngjyrat përsëri, por kjo është ajo ku ishim. Dhe arsyeja që unë e bëri këtë është për shkak se ky proces është duke shkuar për të mbajtur vazhdim e sipër, iterating poshtë. Ne kemi renditura majtë gjysma e ish-portokalli dhe gjysma e djathtë e ish-portokalli. 

Tani, ne kemi nevojë të bashkojë ato dy gjysmat së bashku shumë. Ky është hapi ne jemi në. Pra, ne e konsiderojmë të gjithë e elemente që tani janë të gjelbër, gjysmën e majtë të vektorit origjinale. Dhe ne bashkojë ata duke përdorur të njëjtin proces ne e bëmë për bashkimin e dy dhe një vetëm një moment më parë. 

Gjysmën e majtë, më të vogël element në gjysmën e majtë është pesë. Elementi më i vogël në gjysma e drejtë është një. Cili prej tyre është më i vogël? Një. 

Elementi më i vogël në gjysmën e majtë është pesë. Elementi më i vogël në gjysma e drejtë është dy. Çfarë është më i vogël? Dy. Dhe pastaj në fund pesë dhe asgjë, ne mund të themi pesë. 

OK, foto kaq i madh, le të të marrë një pushim për një të dytë dhe të kuptoj se ku jemi. Në qoftë se kemi filluar nga fillimi, ne kanë përfunduar tani për array përgjithshme vetëm një hap i kodit pseudokod këtu. Ne kemi renditura gjysma e majtë e vektorit. 

Kujtojnë se origjinal rendi i pesë, dy, një. Duke kaluar nëpër këtë proces dhe shturë poshtë dhe duke përsëritur, duke vazhduar për të thyer problemin poshtë në pjesë më të vogla dhe të vogla, ne kemi përfunduar tani hap një nga pseudokod për të gjithë array fillimit. Ne kemi renditura gjysmën e saj të majtë. 

Pra, tani le të ngrijë atje. Dhe tani le të lloj të drejtën gjysma e array origjinal. Dhe ne jemi duke shkuar për të bërë këtë nga duke kaluar nëpër të njëjtën gjë përsëritës Procesi i thyer gjëra poshtë dhe pastaj bashkimi i tyre së bashku. 

Pra, gjysma e majtë të kuqe, ose gjysmën e majtë i gjysmës së djathtë të origjinalit grup, unë jam duke shkuar për të thënë është tre. Përsëri, unë jam duke u konsistente këtu. Nëse keni një i rastësishëm Numri i elementeve, atë Nuk ka rëndësi nëse ju bëni një të majtë më të vogël ose një e drejtë më të vogla. 

Ajo që ka rëndësi është se sa herë që ju ndeshen me këtë problem në kryerjen e një bashkojë, ju duhet të jenë në përputhje. Ju ose gjithmonë duhet të të bëjë një Krahu i majtë më të vogël apo gjithmonë duhet të bëni anën e djathtë të vogla. Këtu, unë kam zgjedhur për të gjithmonë të bëjë anën e majtë të vogla kur array ime, ose im nën-grup, është e një madhësi çuditshme. 

Tre është një element i vetëm, dhe kështu ajo është e renditura. Ne kemi leveraged që supozim gjatë gjithë procesit tonë deri tani. Pra, tani le të lloj të drejtën gjysma e pjesës së duhur, ose gjysma e djathtë e kuqe. 

Përsëri, ne kemi nevojë për të ndarë këtë poshtë. Kjo nuk është një grup i vetëm element. Ne nuk mund ta deklarojë atë të renditura. Dhe kështu për herë të parë, ne jemi duke shkuar për të zgjidhur gjysmën e majtë. 

Gjysma e majtë është një element i vetëm, kështu që kjo është lloj i by default. Pastaj ne jemi duke shkuar për të zgjidhur të drejtën gjysma, e cila është një element i vetëm. Është e renditura by default. Dhe tani, ne mund të bashkojë ata të dy së ​​bashku. Katër është më i vogël, dhe atëherë gjashtë është më i vogël. 

Përsëri, çfarë kemi bërë në këtë pikë? Ne kemi renditura majtë gjysma e pjesës së duhur. Ose duke shkuar prapa në origjinal ngjyra që ndodheshin aty, ne kemi renditur e majtë gjysma e kuqe butë. Kjo ishte fillimisht një tullë të errët të kuqe dhe tani kjo është një të kuqe të butë, apo kjo ishte një e kuqe butë. 

Dhe pastaj ne kemi renditur gjysma e djathtë e kuqe butë. Tani, mirë, ata janë të gjelbër përsëri, vetëm sepse ne jemi duke shkuar nëpër një proces. Dhe ne kemi për të përsëritur ky pushim. 

Deri tani ne mund të bashkojë ato dy gjysmat së bashku. Dhe kjo është ajo që ne bëjmë këtu. Pra, të vijë të zezë vetëm ndau gjysmën e majtë dhe gjysma e drejta e kësaj pjese renditjes. 

Ne krahasojmë vlerën më të vogël në anën e majtë të array-- ose më falni, më të vogël Vlera e pjesës së majtë me vlerën më të vogël të së drejtës gjysmë dhe për të gjetur se tre është më i vogël. Dhe tani pak e një optimization, e drejtë? Nuk është në fakt asgjë la në anën e majtë. 

Nuk ka asgjë të mbetur në anën e majtë, kështu që ne mund në mënyrë efikase vetëm move-- ne mund të deklarojë pjesa tjetër e saj është në fakt të renditura dhe vetëm litar atë në, sepse nuk ka asgjë tjetër për të krahasuar kundër. Dhe ne e dimë se ana e djathtë e anën e djathtë është e renditura. 

OK, kështu që tani le të ngrijë përsëri dhe kuptoj se ku jemi në histori. Në grup të përgjithshëm, çfarë kemi arritur? Ne kemi në fakt të kryer tani hapa një dhe hap dy. Ne renditura gjysmën e majtë, dhe ne të renditura gjysmën e djathtë. 

Deri tani, të gjitha që mbetet është për ne të bashkojë këto dy gjysmave së bashku. Pra, ne krahasojmë më të ulët të vlerësuar element i secilit gjysma e vektorit nga ana e tij dhe të vazhdojë. Njëra është më pak se tre, kështu shkon. 

Dy është më pak se tre, kështu që dy shkon. Tre është më pak se 5, kështu që tre shkon. Katër është më pak se 5, kështu që katër shkon. Atëherë pesë është më pak se gjashtë, dhe gjashtë është e tëra që mbetet. 

Tani, unë e di, se ishte një shumë e hapa. Dhe ne kemi lënë shumë e kujtesës në prag tonë. Dhe kjo është ajo që këto sheshe janë gri. Dhe kjo ndoshta ndjehet si ajo mori një shumë më të gjatë se futje lloji, flluskë lloj, apo përzgjedhja lloj. 

Por në fakt, për shkak se një shumë prej këtyre proceseve janë duke ndodhur në të njëjtën time-- e cila është diçka që ne do të, përsëri, flasim për kur flasim për Recursion në një të ardhme video-- ky algoritëm fakt në mënyrë të qartë është krejtësisht ndryshe se çdo gjë ne kemi parë më parë por është gjithashtu në mënyrë të konsiderueshme më efikase. 

Pse eshte ajo? E pra, në më të keq skenari, ne kemi për të ndarë n elemente lart dhe pastaj recombine tyre. Por, kur ne recombine ata, ajo që ne jemi duke bërë është në thelb dyfishuar Madhësia e vargjeve të vogla. Ne kemi një bandë e një elementi vargjeve që ne në mënyrë efektive kombinohen në dy vargjeve element. Dhe pastaj ne kemi marrë ato dy vargjeve element dhe të kombinuar ato së bashku në katër vargjeve element, dhe kështu me radhë, dhe kështu me radhë, dhe kështu me radhë, deri sa ne kanë një të vetme koleksion element n. 

Por sa doublings nuk është marrë për të marrë në n? Mendoni përsëri për shembull librin e telefonit. Sa herë ne duhet të heq libri telefon në gjysmë, sa më tepër herë nuk kemi të heq librin e telefonit në gjysmë, në qoftë se madhësia e librin e telefonit dyfishuar? Ka vetëm një, e drejtë? 

Pra, ka disa lloj element logaritmike këtu. Por ne gjithashtu ende duhet të paktën shikoni në të gjitha elementet n. Pra, në rastin më të keq, bashkojë lloj shkon në log n n. Ne duhet të shikojmë në të gjithë elementet n, dhe ne kemi për të kombinuar ato së bashku në log n grupe të hapave. Në rastin më të mirë, array është renditur në mënyrë të përkryer. Kjo është e madhe. Por bazuar në algorithm ne kemi këtu, ne ende kemi për të ndarë dhe recombine. Edhe pse në këtë rast, recombining është lloj i paefektshëm. Ajo nuk është e nevojshme. Por ne ende kalojnë nëpër i gjithë procesi gjithsesi. 

Pra, në rastin më të mirë dhe në rastin më të keq, kjo algorithm shkon në log n n kohë. Merge lloj është padyshim pak i komplikuar se algoritme tjera kryesore klasifikim ne kemi biseduar për CS50, por është në thelb më të fuqishme. 

Dhe kështu që nëse ju ndonjëherë gjeni rast të ketë nevojë për atë ose të përdorin atë për të zgjidhur një grup i madh të dhënave, duke marrë kokën tuaj rreth idesë së recursion do të jetë me të vërtetë i fuqishëm. Dhe kjo do të bëjë tuaj Programet me të vërtetë shumë më të efektshme duke përdorur bashkojë lloj kundrejt çdo gjë tjetër. Unë jam Doug Lloyd. Kjo është CS50.