[Musika jotzen] 

DOUG LLOYD: Ados, beraz bateratze bat moduko da oraindik algoritmoa beste Hori ordenatzeko erabili ahal izango dugu array bateko elementu. Baina ikusi dugu, nik lortu bat oso funtsezko aldea aukeraketa ordenatu, burbuila-tik ordenatu, eta txertatzeko ordenatu Hori egiteko benetan polita clever da. 

Oinarrizko ideia batzea atzean moduko da arrayak txikiagoa ordenatzeko eta, ondoren, array horiek konbinatu elkarrekin, edo batu Horietako horregatik ordena ordenatuko izen du. Modu ordenatu egiten batu hau tresna bat aprobetxatuz da errekurtsio deitzen zaio, hau da, zer ari gara, laster izango da buruz hitz egitera doa, baina ez, benetan oraindik buruz hitz egin dugu. 

Hemen oinarrizko ideia sort batu atzean. Ordenatzeko ezker array erdia, suposatuz n 1 baino handiagoa da. Eta zer esango dizut, esan nahi dut suposatuz n baino 1 handiagoa da, Uste dut ados ahal izango dugu array bat bada bakarrik elementu bakar bat osatzen dute, ordenatuko da. Egia esan, ez behar dugu ezer egin behar da. Daiteke besterik aldarrikatzen dugu ordenatuko da. Elementu bakar bat besterik ez da. 

Beraz pseudocode, berriro ere, Ezkerretik array erdia ordenatzeko, ondoren, array eskuineko erdia ordenatzeko, ondoren batu bi erdi elkarrekin. Orain, dagoeneko duzun liteke pentsatzen, mota besterik ez da off ari zara jartzen bezalako the-- soinuak Oraindik ez benetan ezer egin duzu. Oraindik ordenatzeko ezkerreko esanez duzu erdia, eskuineko erdia ordenatzeko, baina zuk ez diozu me nola egiten ari zarenean. 

Baina gogoratu, betiere hori array baten elementu bakar bat da, deklaratu ahal izango dugu horrela antolatu. Ondoren, besterik ezin dugu konbinatu horiek elkarrekin. Eta hori da, benetan, sort batu atzean oinarrizko ideia, da apurtu behera, beraz, Zure arrayak tamaina bat dira. Eta gero birsortu hortik duzu. 

Batu ordenatu da betiko Algoritmo korapilatsu bat. Eta, gainera, apur bat da konplikatua den ikusteko. Beraz, espero dugu, bistaratzea dudala hemen batera jarraitu ahal izango duzu. Eta nire onena saiatuko naiz gauzak kontatzeko eta pixka bat gehiago bidez jarraitu Poliki-poliki beste batzuk baino Besterik ez duzu, zorionez, zure burua lortu sort batu atzean ideia inguruan. 

Beraz, array gisa berean egin behar dugu beste ordena bildu bideoak ikusi dituzun bada Horietako sei elementu sorta bat. Eta gure pseudocode kodea da hemen ordenatu ezkerreko erdian, eskuineko erdia ordenatzeko, bi erdi batzea elkarrekin. Beraz, dezagun adreiluzko oso ilun gorri honetan array eta ezkerreko erdia ordenatzeko. 

Beraz, oraingoz, goazen eskubidea stuff ikusi egiteko. Hemen da, baina ez gara Ez urrats hori oraindik ere. Ez gara modukoak eskuineko array erdia. Oraindik moduko ezkerreko aldean dugu array erdia. Eta besterik mesedetan apur bat gehiago izatea argi, beraz, kontsultatu ahal izan nuen zer urratsera ari gara, Pizten noa laranja multzo honen kolorea. Orain, oraindik ere ari gara buruz hitz egiten bera ezker jatorrizko array erdia. Baina espero dut hori egiteko gai izatea hainbat elementu koloreak izendatzeko, apur bat gehiago egin beharko da argi zer gertatzen da hemen. 

Ados, beraz, gaur egun dugun bat Hiru elementu sorta. Zelan geratzen honen erdia ordenatzeko dugu array, horrek urrats hau ez da oraindik? Ezkerreko ordenatzeko saiatzen ari gara adreiluzko array gorria erdia Ezkerreko erdia Nik orain koloretako I laranja. 

Beno, saiatu izan dugu, eta Prozesu hau errepikatu berriro. Beraz, oraindik ez gara hasi ordenatzeko saiatzen erdian ezkerreko multzo osoa erdia. Ezkerreko erdia array, besterik ez dut joan arbitrarioki erabaki ezkerreko zatian eskuineko erdia baino txikiagoa izango da, Hori gertatzen delako Hiru elementu osatuko dute. 

Eta beraz, ez dut esan nahi duten joan ezker array ezkerreko erdia erdia besterik elementu bost. Bost, elementu bakar bat izateaz array, nola ordenatzeko badakigu. Eta orain bost ordenatuko da. Besterik ez gara hori aldarrikatzen joan. Elementu array bakar bat da. 

Beraz, gaur egun antolatuta gara ezkerreko ezker half-- erdia edo, hobeto esanda, horrela antolatu dugu egin ezker laranja erdia. Beraz, orain, ahal izateko, oraindik osatu Array orokorra ezkerreko erdia, eskuineko erdia ordenatzeko behar dugu laranja, edo gauza hau. Nola egiten dugu? Beno, bi elementu array bat dugu. Beraz ezkerreko erdian ordenatzeko dezakegu array, bi da. Bi elementu bakar bat da. Beraz lehenetsita ordenatuko. Ondoren eskuineko erdia ordenatzeko dezakegu Array, bat-zati hori. Hori da Ordena lehenetsita. 

Hau da, gaur egun, lehen aldiz Nik batzea urrats bat lortu dugu. Osatu dugu, nahiz eta Oraindik orain, mota horretako habiaratu Behera dugu eta hori da, delikatua moduko errekurtsio gauza da, Zure mantendu behar duzu zertan garen joatea. Beraz moduko dugu ezkerraren laranja zati erdia. 

Eta orain, ez gara ordenazio-erdian eskuin laranja zati erdia. Eta prozesu horretan, gauden Gaur egun gauza urratsa izango da, bi erdi batzea elkarrekin. Noiz begiratu bi erdi egon ginen Array, bi eta bat ikusiko dugu. Zein elementu txikiagoa da? One. 

Orduan, zein elementu txikiagoa da? Beno, bi edo ezer. Beraz, bi da. Beraz, gaur egun, besterik gabe, berriro markoa non daude testuinguruan dugu, ordenatuko ditugu ezker laranja erdia eta eskuineko jatorria erdia. Aldatu dut koloreak ezagutzen dut berriro, baina hori non geunden. Eta arrazoia nik egin dut prozesu hori delako jarraitzea, behera errepikatzean joan. Ezkerreko horrela antolatu dugu laranja ohia erdia eta eskuin laranja ohia erdia. 

Orain, horiek batu behar ditugu bi erdi elkarrekin too. Hori urratsa ari gara ezagutzen da. Beraz, kontuan hartzen badugu guztia Hori berdea dira orain elementuak, ezker jatorrizko array erdia. Eta horiek batu ditugu prozesua bera erabiliz bi batuz genuen eta duela une bat. 

Ezkerreko erdia, txikiena elementu ezkerreko erdia bost da. On txikiena elementu eskuineko erdia da. Horietako Zein txikiagoa da? One. 

On txikiena elementu Ezkerreko erdia bost da. On txikiena elementu eskuineko erdia bi da. Zer da txikiena? Bi. Eta gero, azkenik, bost eta ezer ez, bost esan dezakegu. 

Ados, irudi hain handia, dezagun atseden bat hartu bigarren bat eta irudikatu non gauden. Hasi ginen badu Oso hasieran, dugu dute orain osatuta array orokorra besterik pseudocode kodearen urrats bat hemen. Ordenatuko ditugu ezker array erdia. 

Gogoratzen original dela Ordena bost, bi, bat izan zen. Prozesu honen bidez, joan By eta behera, habia eta errepikatuz, Arazoa hausteko etengabeko behera zatiak eta txikiago sartu, bukatu dugu pseudocode bat zapaldu hasierako array osoa da. Bere ezkerreko erdia ordenatuko ditugu. 

Beraz, gaur egun dezagun izoztea ez. Eta orain ordenatzeko eskubidea utzi jatorrizko array erdia. Eta ari gara hori egin dituen joan Etorriko bera igaro Gauzak hautsi behera prozesua eta gero batuz elkarrekin. 

Beraz, ezkerreko erdia gorria, edo ezkerreko erdia eskubidea jatorrizkoaren erdiaren array, ez dut esango hiru da. Berriz ere, koherentea hemen ari naiz. Bakoitiak bat baldin baduzu elementu kopurua da, Ez du axola ala txikiago ezkerrekoa egin duzu edo eskuineko bat txikiagoa. 

Zer axola, betiere duzula realización arazo hau topo bateratze bat, koherentea izan behar duzu. Bai duzu beti behar den ezkerretik bat txikiagoak egin edo beti behar egiteko Eskuinaldean txikiagoa. Hemen, beti aukeratu dudan Ezkerreko aldean, txikiagotu nire array, edo nire Azpi-sorta, tamaina bat bakoitiak da. 

Hiru elementu bakar bat da, eta beraz ordenatuko da. Eta hipotesi horren dugu leveraged gure prozesu osoan orain arte. Beraz, gaur egungo ordenatzeko eskubidea utzi eskuineko erdia erdiak, edo eskuineko gorria erdia. 

Berriz ere, hau zatitu behera egin behar dugu. Hau ez da elementu sorta bakar batean. Ezin dugu deklaratzen da ordenatuta. Eta, beraz, lehen, goazen ezkerreko erdia ordenatzeko. 

Ezker seihilekoan elementu bakar bat da, beraz Ordena da lehenetsita. Ondoren gaude eskubidea ordenatzeko joan erdia, elementu bakar bat da. Honez lehenetsita ordenatuko. Eta, orain, batu ditugu bi horiek elkarrekin. Lau txikiagoa da, eta txikiago orduan sei da. 

Berriz ere, zer egin puntu honetan dugun? Ezkerreko horrela antolatu dugu eskuineko erdia erdiak. Edo atzera egingo jatorrizkoaren egon ziren koloreak, ezkerreko horrela antolatu dugu leunagoak gorria erdia. Jatorriz zen adreiluzko ilun bat egiten gorria eta orain gorri leunagoak da, edo gorria leunagoak izan zen. 

Eta gero ordenatuko dugun eskubidea leunagoak gorria erdia. Orain, bai, berde berriro ari dira, besterik prozesu baten bidez ari garelako. Eta errepikatu behar dugu baino gehiago hau eta gehiago. 

Beraz, gaur egun horiek batu ditugu bi erdi elkarrekin. Eta hori da, zer egiten dugu hemen. Beraz, lerro beltzak besterik Ezkerreko erdia banatzen eta eskubidea moduko zatia honen erdia. 

Balio txikiena alderatu dugu ezker array du bestaldean edo Barkatu, txikiena Ezkerraldean erdia balio eskubidearen balio txikiena erdi eta aurkitu duten hiru txikiagoa da. Eta orain optimizazioa bat apur bat, ezta? Ez, egia esan, ez da ezer ezkerraldean geratzen. 

Ez dago ezer gainerako Ezkerreko aldean, beraz, modu eraginkorrean egin ahal izango dugu besterik move-- deklaratu ahal izango dugu gainerako benetan ordenatuta eta besterik Tack da an, zeren ez dago ezer bestela aurka alderatu. Eta badakigu Eskuinaldean dagoela Eskuinaldean ordenatuko da. 

Ados, beraz, orain dezagun izoztu berriro eta irudikatu non daude istorioa dugu. Array orokorrean aztertuta, zer izan dugu lortzen? Nik, egia esan, egiten dugu orain bat eta urrats bi urrats. Ezkerreko erdia ordenatuko ditugu, eta eskuineko erdia ordenatuko ditugu. 

Beraz, gaur egun, ez da geratzen dena da guretzat da bi erdi horiek elkarrekin batzeko. Beraz, parte hartu izana txikiena alderatu dugu array Zati bakoitzaren elementu Aldi berean, eta jarraitu. Bat da hiru baino gutxiago, beraz, bat doa. 

Bi edo hiru baino gutxiago da, beraz, bi doa. Hiru 5 baino txikiagoa da, beraz, hiru doa. Lau 5 baino txikiagoa da, beraz, lau doa. Ondoren, bost, sei baino gutxiago da, eta sei dela geratzen. 

Orain, badakit, urrats handia izan zen. Eta asko utzi dugu Gure estela oroimenaren. Eta hori da, lauki gris horiek dira. Eta seguruenik sentitu bezala Partiduaren Asko txertatzeko ordenatu baino luzeagoa, burbuila ordenatu, edo hautaketa ordena. 

Baina, egia esan, bat delako Prozesu horietako asko dira, aldi berean gertatzen bertan dugun zerbait da, berriro, denean buruz hitz egin dugu buruz hitz egin etorkizun batean errekurtsio video-- Algoritmo hau benetan Argi eta garbi dago, funtsean, Ezer baino ezberdinak Aurrez aipatu dugun baina, era berean, nabarmen eraginkorragoa. 

Zergatik da hori? Beno, txarrenean kasurik, ez dugu n elementu zatitu egin eta, ondoren, birkonbinatu horiek. Baina orduan birkonbinatu dugu horiek, zer egiten ari garen Funtsean bikoiztu du arrayak txikiagoa tamaina. Elementu bat mordo bat daukagu arrayak eraginkortasunez dugu elementu bi multzo zitezen. Eta gero horiek hartuko dugu elementu bi multzo eta elkarrekin konbinatu horiek sartu elementu lau multzo dute, eta, beraz, eta abar, eta abar, ez dugu arte n elementu array bakar bat izatea. 

Baina zenbat aldiz biderkatu duela to n lortzeko hartu? Think telefono book Adibidez itzuli. Zenbat aldiz egin alderik daukagu Telefono liburuaren erdia, zenbat gehiago aldiz egin telefono liburua alderik daukagu erdia, bada telefono book tamainaren bikoiztu? Ez dago beste besterik ez da, ezta? 

Beraz, ez dago nolabaiteko da logarithmic elementu hemen. Baina, era berean, oraindik ez dugu nahi, gutxienez n elementu guztiak begiratu. Txarrenean ere, orain, ordenatu batzea ere n log n exekutatzen. Begiratzen dugu n elementu guztiak, eta konbinatu egin behar dugu elkarrekin log n urrats multzo batean. Kasurik onenean ere, Array primeran ordenatuko da. Hori handia. Baina algoritmoan oinarritutako hemen dugu, oraindik zatitu eta birkonbinatu ditugu. Kasu honetan badira ere, gurutzagarria eragingabeak mota da. Ez da beharrezkoa. Baina oraindik ere igaroko ditugu prozesu osoan, hala ere. 

Beraz, kasu onenean eta kasurik okerrenean ere, Algoritmo hau n log n denbora exekutatzen. Batu ordenatu da, zalantzarik gabe, pixka bat zailagoa Beste ordenazio algoritmo nagusiak baino CS50 hitz egin dugu, baina ez da funtsean ahaltsuagoa. 

Eta hala bada inoiz aurkituko duzu Oraingoan da behar den edo hura erabiltzeko a ordenatzeko Datu handiak ezarri, lortzean Zure burua errekurtsio ideiaren inguruan da benetan indartsua izango. Eta hori egiteko joan zure programak benetan askoz eraginkorragoa batu ordenatu beste ezer versus erabiliz. Naiz Doug Lloyd. Hau CS50 da.