[Powered by Google Translate] [Bashkojë Rendit] [Rob Bowden - Universiteti i Harvardit] [Kjo është CS50. - CS50.TV] Le të flasim për lloj bashkohen. Deri tani ju kam parë lloj flluskë, lloj lloj futje, dhe përzgjedhjes. Edhe pse unë do lloj vale dorën time në atë që dua të them me të mirë, bashkojë lloj përgjithësi kryen më mirë se ndonjë nga këto 3 terezi. 

Por, para se të flasim për lloj bashkojë, le të flasim për bashkimin 2 listat e renditura. Ne do të thërrasë në procesin e marrjes së 2 lista të renditura, si këto, dhe duke e bërë një listë të vetme zgjidhet prej tyre - bashkimin e listave. Si mund ta bëjë këtë? E pra, një ide është që të rrinë vetëm një listë të mbyllet në fund të listës të tjera dhe pastaj lloj listën rezulton. 

Ndërsa kjo punon, kjo është një punë shumë e panevojshme. Ne mund të bëjmë atë më shpejt se vetëm zgjidhja. Vini re se një ide e gabuar është që të marrë vetëm gota alternuara nga çdo listë. Ndërkohë që mund të duket si që punon në fillim, duke bërë që ne të përfundojnë me 4, 8, 15, 23, 16 - njoftim se 16 dhe 23 janë jashtë vendit. Kjo është për shkak se 2 elemente që duhet të paraqiten njëpasnjëshëm në listën e bashkuar janë në të njëjtën listë fillestare. Të dyja 15 dhe 16 janë në lista në të majtë. Qëllimi është që të përfitojnë nga fakti se të dyja janë të renditura listat tashmë. Kjo do të thotë se në qoftë se ne vetëm shikojmë në elementet e para të dy listat - këtu, 4 dhe 8 - një prej tyre duhet të jetë gjithashtu elementi i parë i lista bashkuar. E pra, pse është kjo? Të dyja këto lista janë të renditura tashmë, dhe kështu ose 4 ose 8 duhet të jetë elementi më i vogël, kur ne kombinojnë 2 listat. Në këtë rast, më i vogli është 4, kështu që ne mund të merrni nga 4 dhe të bëjë atë elementi i parë i listës sonë bashkuar. Tani ne vazhdojmë bashkimin e mbetura 3 elementet e listës parë dhe 4 elementet e listës së dytë. 

Edhe njëherë, ne vetëm duhet të shikoni në elementin e parë të dyja listat. Sa më i vogël i 2 duhet të jetë elementi i dytë i listës sonë bashkuar. Këtë herë, në mes 8 dhe 15 më i vogli është 8, dhe kështu që ne të futur që si elementin e dytë të listës sonë renditura. Ne mund të vazhdojmë duke krahasuar elementet e para të të dyja listat dhe largimin e vogël e 2. Krahasimi 15 dhe 23, 15 është më i vogël dhe kështu kjo është elementi ynë i tretë. Tani duke krahasuar 16 dhe 23, 16 është më i vogël. Pra, kjo është elementi i katërt. 

Vini re se 2 elemente erdhi nga lista njëjtë në një rresht. Kjo është arsyeja pse lista bashkuar nuk mund vetëm elemente alternative nga 2 listave. Krahasimi 50 dhe 23, 23 është më i vogël, kështu që ne të zgjedhin atë. Midis 50 dhe 42, 42 është më i vogël. Midis 50 dhe 108, 50 është më i vogël. Dhe, së fundi, ne vetëm kemi 108, kështu që ajo duhet të shkojë në fund të listës sonë. Vini re se ne kemi një listë të bukur, të renditura. Çdo herë kemi krahasuar para 2 elementet e listave 2 ne ishim në gjendje për të përcaktuar elementin tjetër të listës bashkuar. Kjo do të thotë se në qoftë se lista përfundimtare përmban numrat n, ku n këtu është 8, atëherë ne kemi nevojë më në krahasimet n të marrë të gjitha ato numra në vendin e duhur. Tillë një algoritmi është thënë për të kandiduar në kohë lineare, por mos u bëni merak për këtë këtu. 

Duke përdorur algorithm tonë për bashkimin, ne mund të bëjë një algoritmi të shpejtë bashkojë renditjes. Pra, le të rivendosur listat tona. Ka 2 hapa të mëdha në procesin e lloj bashkohen. Së pari, vazhdimisht ndarë listën e gota në gjysmave deri sa ne kemi një bandë e listave me vetëm 1 filxhan në to. Mos u shqetësoni nëse një listë përmban një numër të rastësishëm dhe ju nuk mund të bëjë një prerje të përkryer të pastër në mes tyre. Vetëm arbitrare të vini të cilën listë të përfshijë kupën ekstra in Pra, le të ndahen këto lista. Tani ne kemi 2 listat. Tani ne kemi 4 listat. 

Dhe tani ne kemi 8 listat me një filxhan të vetëm në çdo listë. Pra, kjo është ajo për hapin 1. Për hapin e 2, ne vazhdimisht bashkojë palë e listave duke përdorur algoritmin bashkojë kemi mësuar më parë. Bashkimi i 108 dhe 15, deri ne fund me listën e 15, 108. Bashkimi 50 dhe 4, ne fund me 4, 50. Bashkimi 8 dhe 42, deri ne fund me 8, 42. Dhe bashkimin 23 dhe 16, ne fund me 16, 23. Tani të gjitha listat tona janë të madhësisë 2. Njoftim që secili prej 4 listave është renditura. 

Kështu që ne mund të fillojë bashkimin palë e listave përsëri. Bashkimi 15 dhe 108 dhe 4 dhe 50 - së pari të marrë 4, pastaj 15, pastaj 50, pastaj 108. Bashkimin 8, 42 dhe 16, 23, ne së pari të marrë 8, pastaj 16, pastaj 23, pastaj 42. Deri tani ne kemi vetëm 2 listat e madhësisë 4, secila prej të cilave është renditura. Deri tani ne bashkojë këto 2 listat. Së pari ne kemi marrë 4. Pastaj kemi marrë 8. Pastaj ne kemi marrë 15 dhe 16, pastaj 23, pastaj 42, pastaj 50, pastaj 108. Dhe ne jemi duke bërë. Ne tani kemi një listë të renditura. Pra, se sa shpejt ishte ky, saktësisht? Në terma teknike, lloj bashkojë është O (n log n), ndërsa të gjitha lloj flluskë, lloj lloj futje, dhe përzgjedhjes janë të O (n ²). Në fakt, si ju do të mësoni shpejt, ju nuk do të jetë në gjendje për të dalë me një lloj që kryen më mirë se O (n log n) në rastin e përgjithshëm. Përsëri, mos u bëni merak për këtë simbol Big O qoftë se ju nuk e keni parë atë ende. 

Vetëm e di se kjo do të thotë në qoftë se ne të kërkuar për të zgjidhur një listë me të vërtetë e madhe lloj flluskë, lloj futje, dhe përzgjedhja lloj potencialisht mund të marrë dukshëm më shumë se bashkohen lloj. Kjo nuk do të thotë se do të jetë lloj bashkojë të shpejtë për të gjitha listat apo edhe për ndonjë listë të vetme nën një madhësi të caktuar. Për shembull, mund të jetë lloj futje lloj shpejtë për të gjitha listat e më të vogla se 5 elementeve. Në praktikë, lloj bashkojë është zakonisht më të shpejtë për listat si të vogla si 50 elemente. 

Por kjo shpejtësi ekstra nuk ka ardhur pa një çmim. Ndryshe nga llojet tona të tjera, të cilat marrin një listë dhe modifikojë listën në vend deri sa të kemi një listë të renditura, lloj bashkojë nevojë për një hapësirë ​​shtesë të bashkojë 2 listat së bashku. Ne nuk mund të përdorni menjëherë listat që janë duke u bashkuar për të ruajtur listën e shkrirë që ne mund të pranoj elementet që ende duhet të bashkohen. Kjo hapësirë ​​është pak e një çmim, por kjo zakonisht nuk është e paarsyeshme. Dhe kjo është ajo për lloj bashkohen. 

Emri im është Rob Bowden, dhe kjo është CS50. [CS50.TV] - Dhe zgjedhja lloj. [Qesh] Oh, marrë për të marrë atë jashtë shumë, sepse unë kaloi si unë u paraqitur atë. Lista në të majtë. Kjo ishte një typo. [Misspoke] I dehur - [Qesh] Unë nuk e di se çfarë -