Merge SortYouTube↗  IA↗(long shot)
Education  38.2K views 180 likes 23 dislikes   07 Oct 2015
CS50 2.4M subscribers United States YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
>> [Musika jotzen]
>> [MUSIC SPILLE]
>> DOUG LLOYD: Ados, beraz bateratze bat moduko da oraindik algoritmoa beste
>> DOUG LLOYD: OK, så et flette sort er nok en algoritme
Hori ordenatzeko erabili ahal izango dugu array bateko elementu.
som vi kan bruke til å sortere ut elementene i en matrise.
Baina ikusi dugu, nik lortu bat oso funtsezko aldea
Men som vi skal se, det har en veldig fundamental forskjell
aukeraketa ordenatu, burbuila-tik ordenatu, eta txertatzeko ordenatu
fra utvalget sortere, boble sortere og innsetting sort
Hori egiteko benetan polita clever da.
som gjør det egentlig ganske smart.
>> Oinarrizko ideia batzea atzean moduko da arrayak txikiagoa ordenatzeko
>> Den grunnleggende ideen bak merge sorter er å sortere mindre arrays
eta, ondoren, array horiek konbinatu elkarrekin, edo batu Horietako
og deretter kombinere disse arrays sammen, eller flette them--
horregatik ordena ordenatuko izen du.
derav name-- i sortert rekkefølge.
Modu ordenatu egiten batu hau tresna bat aprobetxatuz da
Måten fusjonere slags gjør dette er ved å utnytte et verktøy
errekurtsio deitzen zaio, hau da, zer ari gara, laster izango da buruz hitz egitera doa,
kalt rekursjon, som er hva vi skal snakke om å bli snart,
baina ez, benetan oraindik buruz hitz egin dugu.
men vi har egentlig ikke snakket om ennå.
>> Hemen oinarrizko ideia sort batu atzean.
>> Her er den grunnleggende ideen bak merge sort.
Ordenatzeko ezker array erdia, suposatuz n 1 baino handiagoa da.
Sortere venstre halvdel av tabellen, forutsatt at n er større enn 1.
Eta zer esango dizut, esan nahi dut suposatuz n baino 1 handiagoa da,
Og hva jeg mener når jeg sier forutsatt at n er større enn 1 er,
Uste dut ados ahal izango dugu array bat bada bakarrik elementu bakar bat osatzen dute,
Jeg tror vi kan være enige om at hvis en matrise bare består av et enkelt element,
ordenatuko da.
det er sortert.
Egia esan, ez behar dugu ezer egin behar da.
Vi har ikke egentlig trenger å gjøre noe til det.
Daiteke besterik aldarrikatzen dugu ordenatuko da.
Vi kan bare erklære det som skal sorteres.
Elementu bakar bat besterik ez da.
Det er bare et enkelt element.
>> Beraz pseudocode, berriro ere, Ezkerretik array erdia ordenatzeko,
>> Så pseudokode, igjen, er sortere venstre halvdel av tabellen,
ondoren, array eskuineko erdia ordenatzeko, ondoren batu bi erdi elkarrekin.
deretter sortere høyre halvdel av tabellen, deretter slå sammen de to halvdelene sammen.
Orain, dagoeneko duzun liteke pentsatzen, mota besterik ez da
Nå, allerede kan du være tenkning, den slags bare
off ari zara jartzen bezalako the-- soinuak Oraindik ez benetan ezer egin duzu.
høres ut som du sette av the-- du faktisk ikke gjør noe.
Oraindik ordenatzeko ezkerreko esanez duzu erdia, eskuineko erdia ordenatzeko,
Du sier sortere venstre halvparten, sortere høyre halvdel,
baina zuk ez diozu me nola egiten ari zarenean.
men du er ikke å fortelle meg hvordan du gjør det.
>> Baina gogoratu, betiere hori array baten elementu bakar bat da,
>> Men husk at så lenge en matrise er et enkelt element,
deklaratu ahal izango dugu horrela antolatu.
vi kan erklære det sortert.
Ondoren, besterik ezin dugu konbinatu horiek elkarrekin.
Da kan vi bare kombinere dem sammen.
Eta hori da, benetan, sort batu atzean oinarrizko ideia,
Og det er faktisk den Grunntanken bak merge sort,
da apurtu behera, beraz, Zure arrayak tamaina bat dira.
er å bryte det ned slik at arrays er av størrelse en.
Eta gero birsortu hortik duzu.
Og så du gjenoppbygge derfra.
>> Batu ordenatu da betiko Algoritmo korapilatsu bat.
>> Flett typen er definitivt en komplisert algoritme.
Eta, gainera, apur bat da konplikatua den ikusteko.
Og det er også litt komplisert å visualisere.
Beraz, espero dugu, bistaratzea dudala hemen batera jarraitu ahal izango duzu.
Så forhåpentligvis, visualisering som jeg har her vil hjelpe deg å følge med.
Eta nire onena saiatuko naiz gauzak kontatzeko eta pixka bat gehiago bidez jarraitu
Og jeg skal prøve mitt beste for å fortelle ting og gå gjennom dette litt mer
Poliki-poliki beste batzuk baino Besterik ez duzu, zorionez, zure burua lortu
saktere enn de andre bare for å forhåpentligvis få hodet
sort batu atzean ideia inguruan.
rundt ideene bak merge sort.
>> Beraz, array gisa berean egin behar dugu beste ordena bildu bideoak
>> Så vi har samme utvalg som andre sorteringsalgoritme videoer
ikusi dituzun bada Horietako sei elementu sorta bat.
Hvis du har sett them-- en seks element array.
Eta gure pseudocode kodea da hemen ordenatu ezkerreko erdian, eskuineko erdia ordenatzeko,
Og vår pseudokoden her er liksom venstre halvdel, sortere høyre halvdel,
bi erdi batzea elkarrekin.
fusjonere de to halvdelene sammen.
Beraz, dezagun adreiluzko oso ilun gorri honetan array eta ezkerreko erdia ordenatzeko.
Så la oss ta dette veldig mørk mursteinsrød matrise og sortere igjen halvparten av det.
>> Beraz, oraingoz, goazen eskubidea stuff ikusi egiteko.
>> Så for tiden, vi skal å ignorere ting til høyre.
Hemen da, baina ez gara Ez urrats hori oraindik ere.
Den er der, men vi er ikke i det skrittet enda.
Ez gara modukoak eskuineko array erdia.
Vi er ikke i form til høyre halvdel av tabellen.
Oraindik moduko ezkerreko aldean dugu array erdia.
Vi er på liksom venstre halvparten av tabellen.
Eta besterik mesedetan apur bat gehiago izatea
Og bare for moro skyld for å være litt mer
argi, beraz, kontsultatu ahal izan nuen zer urratsera ari gara,
klart, så jeg kan referere til hva skritt vi er på,
Pizten noa laranja multzo honen kolorea.
Jeg kommer til å slå Fargen på dette settet til oransje.
Orain, oraindik ere ari gara buruz hitz egiten bera ezker jatorrizko array erdia.
Nå er vi fremdeles snakker om samme venstre halvdel av den opprinnelige matrisen.
Baina espero dut hori egiteko gai izatea hainbat elementu koloreak izendatzeko,
Men jeg håper at ved å være i stand til å refererer til fargene på ulike elementer,
apur bat gehiago egin beharko da argi zer gertatzen da hemen.
det vil gjøre det litt mer klart hva som skjer her.
>> Ados, beraz, gaur egun dugun bat Hiru elementu sorta.
>> OK, så nå har vi en tre-element array.
Zelan geratzen honen erdia ordenatzeko dugu array, horrek urrats hau ez da oraindik?
Hvordan vi sorterer gjør den venstre halvdelen av dette array, som fortsatt er dette trinnet?
Ezkerreko ordenatzeko saiatzen ari gara adreiluzko array gorria erdia
Vi prøver å sortere venstre halvparten av mursteinsrød array--
Ezkerreko erdia Nik orain koloretako I laranja.
venstre hvorav halvparten Jeg har nå farget oransje.
>> Beno, saiatu izan dugu, eta Prozesu hau errepikatu berriro.
>> Vel, vi kan prøve og gjenta denne prosessen på nytt.
Beraz, oraindik ez gara hasi ordenatzeko saiatzen erdian
Så vi er fortsatt i midten av prøver å sortere
ezkerreko multzo osoa erdia.
den venstre halvdel av en fullstendig matrise.
Ezkerreko erdia array, besterik ez dut joan
Den venstre halvdel av matrise, jeg bare går
arbitrarioki erabaki ezkerreko zatian eskuineko erdia baino txikiagoa izango da,
å vilkårlig bestemme at den venstre halvdelen vil være mindre enn den høyre halvdel,
Hori gertatzen delako Hiru elementu osatuko dute.
fordi dette skjer med bestå av tre elementer.
>> Eta beraz, ez dut esan nahi duten joan ezker array ezkerreko erdia erdia
>> Og så kommer jeg til å si at venstre halvdel av den venstre halvdel av matrisen
besterik elementu bost.
er bare element fem.
Bost, elementu bakar bat izateaz array, nola ordenatzeko badakigu.
Five, som er en enkelt element array, vet vi hvordan vi skal sortere det.
Eta orain bost ordenatuko da.
Og så five blir sortert.
Besterik ez gara hori aldarrikatzen joan.
Vi er bare nødt til å erklære det.
Elementu array bakar bat da.
Det er et enkelt element array.
>> Beraz, gaur egun antolatuta gara ezkerreko ezker half-- erdia
>> Så vi har nå sortert venstre halvdel av venstre half--
edo, hobeto esanda, horrela antolatu dugu egin ezker laranja erdia.
eller rettere sagt, har vi sortert venstre halvdel av oransje.
Beraz, orain, ahal izateko, oraindik osatu Array orokorra ezkerreko erdia,
Så nå, for å fortsatt komplett den samlede tabellens venstre halvdel,
eskuineko erdia ordenatzeko behar dugu laranja, edo gauza hau.
vi trenger å sortere høyre halvdel av den oransje, eller slike ting.
Nola egiten dugu?
Hvordan gjør vi det?
Beno, bi elementu array bat dugu.
Vel, vi har en to element array.
Beraz ezkerreko erdian ordenatzeko dezakegu array, bi da.
Så vi kan sortere venstre halvdel i matrisen, som er to.
Bi elementu bakar bat da.
To er et enkelt element.
Beraz lehenetsita ordenatuko. Ondoren eskuineko erdia ordenatzeko dezakegu
Så det er sortert etter standard. Da kan vi sortere høyre halvdel
Array, bat-zati hori.
av den del av matrisen, at en.
Hori da Ordena lehenetsita.
Det er liksom som standard.
>> Hau da, gaur egun, lehen aldiz Nik batzea urrats bat lortu dugu.
>> Dette er nå første gang vi har nådd et flette trinn.
Osatu dugu, nahiz eta Oraindik orain, mota horretako habiaratu Behera dugu
Vi har gjennomført, selv om vi nå slags nestet down--
eta hori da, delikatua moduko errekurtsio gauza da,
og det er liksom den vanskelige Saken med rekursjon er,
Zure mantendu behar duzu zertan garen joatea.
du trenger for å holde hodet om hvor vi er.
Beraz moduko dugu ezkerraren laranja zati erdia.
Så vi har liksom venstre halvparten av den oransje partiet.
>> Eta orain, ez gara ordenazio-erdian eskuin laranja zati erdia.
>> Og nå er vi i midten av sortering den høyre halvdel av den oransje partiet.
Eta prozesu horretan, gauden Gaur egun gauza urratsa izango da,
Og i denne prosessen, er vi nå i ferd med å bli på trinnet,
bi erdi batzea elkarrekin.
fusjonere de to halvdelene sammen.
Noiz begiratu bi erdi egon ginen Array, bi eta bat ikusiko dugu.
Når vi ser på de to halvdelene av tabellen, ser vi to og en.
Zein elementu txikiagoa da?
Hvilket element er mindre?
One.
En.
>> Orduan, zein elementu txikiagoa da?
>> Så hvilket element er mindre?
Beno, bi edo ezer.
Vel, det er to eller ingenting.
Beraz, bi da.
Så det er to.
Beraz, gaur egun, besterik gabe, berriro markoa non daude testuinguruan dugu,
Så nå, bare for å igjen ramme hvor vi er i sammenheng,
ordenatuko ditugu ezker laranja erdia
Vi har sortert venstre halvdel av oransje
eta eskuineko jatorria erdia.
og den høyre halvdel av opprinnelsen.
Aldatu dut koloreak ezagutzen dut berriro, baina hori non geunden.
Jeg vet jeg har endret fargene igjen, men det er der vi var.
Eta arrazoia nik egin dut prozesu hori delako
Og grunnen til at jeg gjorde dette er fordi denne prosessen er
jarraitzea, behera errepikatzean joan.
kommer til å holde det gående, itera ned.
Ezkerreko horrela antolatu dugu laranja ohia erdia
Vi har sortert venstre halvparten av det tidligere orange
eta eskuin laranja ohia erdia.
og den høyre halvparten av det tidligere orange.
>> Orain, horiek batu behar ditugu bi erdi elkarrekin too.
>> Nå trenger vi å fusjonere de to halvdeler sammen også.
Hori urratsa ari gara ezagutzen da.
Det er det trinnet vi er på.
Beraz, kontuan hartzen badugu guztia Hori berdea dira orain elementuak,
Så vi vurdere alle elementer som nå er grønn,
ezker jatorrizko array erdia.
den venstre halvdel av den opprinnelige matrisen.
Eta horiek batu ditugu prozesua bera erabiliz
Og vi slå sammen de ved hjelp av den samme prosessen
bi batuz genuen eta duela une bat.
vi gjorde for å slå sammen to og en bare et øyeblikk siden.
>> Ezkerreko erdia, txikiena elementu ezkerreko erdia bost da.
>> Venstre halvdel, den minste element på den venstre halvdelen er fem.
On txikiena elementu eskuineko erdia da.
Det minste elementet på høyre halvdel er en.
Horietako Zein txikiagoa da?
Hvilken av disse er mindre?
One.
En.
>> On txikiena elementu Ezkerreko erdia bost da.
>> Det minste elementet på den venstre halvdelen er fem.
On txikiena elementu eskuineko erdia bi da.
Det minste elementet på høyre halvdel er to.
Zer da txikiena?
Hva er det minste?
Bi.
Two.
Eta gero, azkenik, bost eta ezer ez, bost esan dezakegu.
Og så til slutt fem og ingenting, kan vi si fem.
>> Ados, irudi hain handia, dezagun atseden bat hartu bigarren bat
>> OK, så store bildet, la oss ta en pause for en andre
eta irudikatu non gauden.
og finne ut hvor vi er.
Hasi ginen badu Oso hasieran, dugu
Hvis vi startet fra helt i begynnelsen, vi
dute orain osatuta array orokorra besterik
har nå fullført for den generelle matrisen bare
pseudocode kodearen urrats bat hemen.
ett trinn av pseudokode her.
Ordenatuko ditugu ezker array erdia.
Vi har sortert venstre halvdel av tabellen.
>> Gogoratzen original dela Ordena bost, bi, bat izan zen.
>> Husk at den opprinnelige For var fem, to, en.
Prozesu honen bidez, joan By eta behera, habia eta errepikatuz,
Ved å gå gjennom denne prosessen og hekkende ned og gjenta,
Arazoa hausteko etengabeko behera zatiak eta txikiago sartu,
fortsetter å bryte problemet ned i mindre og mindre deler,
bukatu dugu pseudocode bat zapaldu
Vi har nå fullført trinn en av pseudokode
hasierako array osoa da.
for hele start matrisen.
Bere ezkerreko erdia ordenatuko ditugu.
Vi har sortert sin venstre halvdel.
>> Beraz, gaur egun dezagun izoztea ez.
>> Så nå kan vi fryse der.
Eta orain ordenatzeko eskubidea utzi jatorrizko array erdia.
Og nå la oss sortere riktig halvparten av den opprinnelige matrisen.
Eta ari gara hori egin dituen joan Etorriko bera igaro
Og vi kommer til å gjøre det ved å gå gjennom den samme iterativ
Gauzak hautsi behera prozesua eta gero batuz elkarrekin.
Prosessen med å bryte ned ting og deretter flette dem sammen.
>> Beraz, ezkerreko erdia gorria, edo ezkerreko erdia
>> Så den venstre halvdel av rød, eller venstre halvdel
eskubidea jatorrizkoaren erdiaren array, ez dut esango hiru da.
av den høyre halvparten av den opprinnelige array, kommer jeg til å si er tre.
Berriz ere, koherentea hemen ari naiz.
Igjen, jeg er å være konsekvent her.
Bakoitiak bat baldin baduzu elementu kopurua da,
Hvis du har en merkelig antall elementer, det
Ez du axola ala txikiago ezkerrekoa egin duzu
spiller ingen rolle om du gjøre det igjen ett mindre
edo eskuineko bat txikiagoa.
eller den rette mindre.
>> Zer axola, betiere duzula realización arazo hau topo
>> Det som betyr noe er at når du opplever dette problemet i å gjennomføre
bateratze bat, koherentea izan behar duzu.
en sammenslåing, må du være konsekvent.
Bai duzu beti behar den ezkerretik bat txikiagoak egin
Du enten alltid trenger å ta til venstre side mindre
edo beti behar egiteko Eskuinaldean txikiagoa.
eller alltid trenger å gjøre høyre side mindre.
Hemen, beti aukeratu dudan Ezkerreko aldean, txikiagotu
Her har jeg valgt å alltid gjøre venstre side mindre
nire array, edo nire Azpi-sorta, tamaina bat bakoitiak da.
da min array, eller min deloppstilling, er av et odde størrelse.
>> Hiru elementu bakar bat da, eta beraz ordenatuko da.
>> Tre er et enkelt element, og så er det sortert.
Eta hipotesi horren dugu leveraged gure prozesu osoan orain arte.
Vi drar nytte av at antakelsen gjennom hele prosessen så langt.
Beraz, gaur egungo ordenatzeko eskubidea utzi eskuineko erdia erdiak,
Så nå la oss sortere riktig halvparten av den høyre halvdel,
edo eskuineko gorria erdia.
eller høyre halvdel av rødt.
>> Berriz ere, hau zatitu behera egin behar dugu.
>> Igjen, vi trenger å dele dette ned.
Hau ez da elementu sorta bakar batean.
Dette er ikke et enkelt element array.
Ezin dugu deklaratzen da ordenatuta.
Vi kan ikke erklære det sortert.
Eta, beraz, lehen, goazen ezkerreko erdia ordenatzeko.
Og så først skal vi til å sortere den venstre halvdelen.
>> Ezker seihilekoan elementu bakar bat da, beraz Ordena da lehenetsita.
>> Den venstre halvdel er et enkelt element, så det er liksom som standard.
Ondoren gaude eskubidea ordenatzeko joan erdia, elementu bakar bat da.
Så skal vi til å sortere riktig halvparten, noe som er et enkelt element.
Honez lehenetsita ordenatuko. Eta, orain, batu ditugu bi horiek elkarrekin.
Den er sortert etter standard. Og nå, vi kan slå sammen de to sammen.
Lau txikiagoa da, eta txikiago orduan sei da.
Fire er mindre, og deretter seks er mindre.
>> Berriz ere, zer egin puntu honetan dugun?
>> Igjen, hva har vi gjort på dette punktet?
Ezkerreko horrela antolatu dugu eskuineko erdia erdiak.
Vi har sortert venstre halvparten av den høyre halvdel.
Edo atzera egingo jatorrizkoaren egon ziren koloreak,
Eller gå tilbake til den opprinnelige farger som var der,
ezkerreko horrela antolatu dugu leunagoak gorria erdia.
vi har sortert venstre halvparten av det mykere rødt.
Jatorriz zen adreiluzko ilun bat egiten gorria eta orain gorri leunagoak da,
Det var opprinnelig en mørk murstein rød og nå er det en mykere rød,
edo gorria leunagoak izan zen.
eller det var en mykere rødt.
>> Eta gero ordenatuko dugun eskubidea leunagoak gorria erdia.
>> Og så har vi sortert høyre halvdel av mykere rødt.
Orain, bai, berde berriro ari dira, besterik prozesu baten bidez ari garelako.
Nå, vel, de er grønne igjen, bare fordi vi går gjennom en prosess.
Eta errepikatu behar dugu baino gehiago hau eta gehiago.
Og vi må gjenta dette igjen og igjen.
>> Beraz, gaur egun horiek batu ditugu bi erdi elkarrekin.
>> Så nå kan vi slå sammen de to halvdeler sammen.
Eta hori da, zer egiten dugu hemen.
Og det er det vi gjør her.
Beraz, lerro beltzak besterik Ezkerreko erdia banatzen
Så den svarte linjen bare delt den venstre halvdelen
eta eskubidea moduko zatia honen erdia.
og høyre halvdel av denne typen delen.
>> Balio txikiena alderatu dugu ezker array du bestaldean
>> Vi sammenligner den minste verdien på venstre side av array--
edo Barkatu, txikiena Ezkerraldean erdia balio
eller unnskylde meg, den minste Verdien av den venstre halvdel
eskubidearen balio txikiena erdi eta aurkitu duten hiru txikiagoa da.
til den minste verdi av den rette halvparten og finner ut at tre er mindre.
Eta orain optimizazioa bat apur bat, ezta?
Og nå litt av en optimalisering, ikke sant?
Ez, egia esan, ez da ezer ezkerraldean geratzen.
Det er faktisk ingenting igjen på venstre side.
>> Ez dago ezer gainerako Ezkerreko aldean,
>> Det er ingenting igjen på venstre side,
beraz, modu eraginkorrean egin ahal izango dugu besterik move-- deklaratu ahal izango dugu
så vi kan effektivt bare move-- vi kan erklære
gainerako benetan ordenatuta eta besterik Tack da
resten av det faktisk sortert og bare tack det
an, zeren ez dago ezer bestela aurka alderatu.
på, fordi det er ingenting annet å sammenligne mot.
Eta badakigu Eskuinaldean dagoela Eskuinaldean ordenatuko da.
Og vi vet at høyre side på høyre side er sortert.
>> Ados, beraz, orain dezagun izoztu berriro eta irudikatu non daude istorioa dugu.
>> OK, så nå la oss fryse igjen og finne ut hvor vi er i historien.
Array orokorrean aztertuta, zer izan dugu lortzen?
I den generelle array, hva har vi oppnådd?
Nik, egia esan, egiten dugu orain bat eta urrats bi urrats.
Vi har faktisk utrette trinn nå en og trinn to.
Ezkerreko erdia ordenatuko ditugu, eta eskuineko erdia ordenatuko ditugu.
Vi sortert venstre halvdel, og vi sortert høyre halvdel.
>> Beraz, gaur egun, ez da geratzen dena da guretzat da bi erdi horiek elkarrekin batzeko.
>> Så nå, er for oss alt som gjenstår å slå sammen de to halvdelene sammen.
Beraz, parte hartu izana txikiena alderatu dugu array Zati bakoitzaren elementu
Så sammenligner vi den laveste verdsatt element i hver halvdel av matrisen
Aldi berean, eta jarraitu.
igjen og fortsette.
Bat da hiru baino gutxiago, beraz, bat doa.
Det ene er mindre enn tre, så man går.
>> Bi edo hiru baino gutxiago da, beraz, bi doa.
>> To er mindre enn tre, så to går.
Hiru 5 baino txikiagoa da, beraz, hiru doa.
Tre er mindre enn 5, så tre går.
Lau 5 baino txikiagoa da, beraz, lau doa.
Fire er mindre enn 5, så fire går.
Ondoren, bost, sei baino gutxiago da, eta sei dela geratzen.
Da fem er mindre enn seks, og seks er alt som gjenstår.
>> Orain, badakit, urrats handia izan zen.
>> Nå, jeg vet, det var mange av trinnene.
Eta asko utzi dugu Gure estela oroimenaren.
Og vi har ikke mye minne i kjølvannet.
Eta hori da, lauki gris horiek dira.
Og det er det de grå rutene er.
Eta seguruenik sentitu bezala Partiduaren Asko txertatzeko ordenatu baino luzeagoa, burbuila
Og det sannsynligvis føltes som det tok mye lenger enn innsetting sortere, boble
ordenatu, edo hautaketa ordena.
sortere, eller valg liksom.
>> Baina, egia esan, bat delako Prozesu horietako asko
>> Men faktisk, fordi en Mange av disse prosessene
dira, aldi berean gertatzen bertan dugun zerbait da, berriro,
Det skjer på samme tid-- som er noe vi vil, igjen,
denean buruz hitz egin dugu buruz hitz egin etorkizun batean errekurtsio video--
snakke om når vi snakker om rekursjon i en fremtidig video--
Algoritmo hau benetan Argi eta garbi dago, funtsean,
denne algoritmen faktisk klart er fundamentalt
Ezer baino ezberdinak Aurrez aipatu dugun
annerledes enn noe vi har sett før
baina, era berean, nabarmen eraginkorragoa.
men er også betydelig mer effektiv.
>> Zergatik da hori?
>> Hvorfor det?
Beno, txarrenean kasurik, ez dugu
Vel, i verste case scenario, har vi
n elementu zatitu egin eta, ondoren, birkonbinatu horiek.
å splitte n elementer opp og deretter rekombinere dem.
Baina orduan birkonbinatu dugu horiek, zer egiten ari garen
Men når vi rekombinerer dem, hva vi gjør
Funtsean bikoiztu du arrayak txikiagoa tamaina.
er i utgangspunktet doble størrelsen av de mindre matriser.
Elementu bat mordo bat daukagu arrayak eraginkortasunez dugu
Vi har en haug av ett element arrays at vi effektivt
elementu bi multzo zitezen.
kombinere i to element arrays.
Eta gero horiek hartuko dugu elementu bi multzo
Og så tar vi dem to element arrays
eta elkarrekin konbinatu horiek sartu elementu lau multzo dute, eta, beraz,
og kombinere dem sammen til fire element arrays, og så videre,
eta abar, eta abar, ez dugu arte n elementu array bakar bat izatea.
og så videre, og så videre, helt til vi ha en enkelt n elementsatsen.
>> Baina zenbat aldiz biderkatu duela to n lortzeko hartu?
>> Men hvor mange doblinger tar det å komme til n?
Think telefono book Adibidez itzuli.
Tenk tilbake til telefonboken eksempel.
Zenbat aldiz egin alderik daukagu Telefono liburuaren erdia, zenbat gehiago
Hvor mange ganger må vi rive telefonboken i to, hvor mange flere
aldiz egin telefono liburua alderik daukagu erdia, bada telefono book tamainaren
ganger må vi rive telefonboken i to, hvis størrelsen på telefonboken
bikoiztu?
doblet?
Ez dago beste besterik ez da, ezta?
Det er bare en, ikke sant?
>> Beraz, ez dago nolabaiteko da logarithmic elementu hemen.
>> Så det er en slags logaritmisk element her.
Baina, era berean, oraindik ez dugu nahi, gutxienez n elementu guztiak begiratu.
Men vi har også fortsatt til minst se på alle de n elementene.
Txarrenean ere, orain, ordenatu batzea ere n log n exekutatzen.
Så i verste fall fusjonere slags kjører i n log n.
Begiratzen dugu n elementu guztiak,
Vi må se på alle av de n elementene
eta konbinatu egin behar dugu elkarrekin log n urrats multzo batean.
og vi må kombinere dem sammen i log n sett med trinn.
Kasurik onenean ere, Array primeran ordenatuko da.
I beste fall matrisen er perfekt sortert.
Hori handia.
Det er flott.
Baina algoritmoan oinarritutako hemen dugu, oraindik zatitu eta birkonbinatu ditugu.
Men basert på algoritmen vi har her, vi har fortsatt å splitte og rekombinerer.
Kasu honetan badira ere, gurutzagarria eragingabeak mota da.
Selv om det i dette tilfellet rekombinerende er slags ineffektiv.
Ez da beharrezkoa.
Det er ikke nødvendig.
Baina oraindik ere igaroko ditugu prozesu osoan, hala ere.
Men vi fortsatt gå gjennom hele prosessen uansett.
>> Beraz, kasu onenean eta kasurik okerrenean ere,
>> Så i beste fall og i verste fall
Algoritmo hau n log n denbora exekutatzen.
denne algoritmen kjører i n log n gang.
Batu ordenatu da, zalantzarik gabe, pixka bat zailagoa Beste ordenazio algoritmo nagusiak baino
Merge sort er definitivt litt mer komplisert enn de andre hovedsorteringsalgoritmer
CS50 hitz egin dugu, baina ez da funtsean ahaltsuagoa.
vi har snakket om CS50 men er vesentlig kraftigere.
>> Eta hala bada inoiz aurkituko duzu Oraingoan da behar den
>> Og så hvis du skulle finne anledning til å trenge det
edo hura erabiltzeko a ordenatzeko Datu handiak ezarri, lortzean
eller å bruke den til å sortere en store datasett, får
Zure burua errekurtsio ideiaren inguruan da benetan indartsua izango.
hodet rundt ideen om rekursjon kommer til å være veldig kraftig.
Eta hori egiteko joan zure programak benetan askoz eraginkorragoa
Og det kommer til å gjøre programmer egentlig mye mer effektiv
batu ordenatu beste ezer versus erabiliz.
bruker fusjonere slags versus noe annet.
Naiz Doug Lloyd.
Jeg er Doug Lloyd.
Hau CS50 da.
Dette er CS50.
Similar videos:

Arrays
CS50
41.2K views 121 likes 5 dislikes 07 Oct 201569% match










Recursion
CS50
45.1K views 0 likes 0 dislikes 13 Oct 201569% match










Binary Search
CS50
128.6K views 0 likes 0 dislikes 26 Sep 201268% match










FAST AND EASY KNIT BABY HAT FOR BEGINNERS 0-12 Month, HOW TO KNIT FOR BEGINNERS, KNITTING FOR BABY
Knitting for Baby
31.3K views 486 likes 19 dislikes 05 Nov 202067% match



Operators
CS50
44.3K views 89 likes 4 dislikes 07 Oct 201567% match










Doubly-Linked Lists
CS50
20.4K views 107 likes 5 dislikes 14 Oct 201567% match










Computational Complexity
CS50
41.4K views 245 likes 12 dislikes 07 Oct 201567% match










Data Structures Summary
CS50
13.8K views 0 likes 0 dislikes 19 Oct 201567% match










Queues
CS50
14.6K views 0 likes 0 dislikes 19 Oct 201566% match










Binary Search
CS50
43.7K views 248 likes 7 dislikes 07 Oct 201566% match










PHP for Web Development
CS50
15.6K views 114 likes 5 dislikes 16 Jun 201666% match










Sneak Peek at Future RENOVATION PROJECT 🛠️💪 | We Want to Restore an ABANDONED HOME in the Mountains!
Samuel and Audrey - Travel and Food Videos
38.3K views 687 likes 8 dislikes 16 Jan 202165% match




5 tips to be a better public speaker / 5 tips to improve your public speaking
Kionz C
10.3K views 110 likes 8 dislikes 11 Aug 202065% match















GETTING LOST IN BRAZIL 🇧🇷 ROADTRIP TO CHAPADA DIAMANTINA
Alexander Travelbum
48K views 4.7K likes 45 dislikes 10 Jan 202165% match

Knit baby hat for Beginners 0-6M, Crochet for Baby
Crochet for Baby
7.7K views 269 likes 9 dislikes 10 Jan 202165% match



Breakfast in Singapore
Samuel and Audrey - Travel and Food Videos
78.7K views 880 likes 54 dislikes 01 Mar 201765% match

Week 4, continued
CS50
42.2K views 0 likes 0 dislikes 21 Oct 201465% match










Self-Driving Cars
CS50
10K views 85 likes 5 dislikes 10 Nov 201565% match










TYLER ENDS UP IN THE HOSPITAL! | We Are The Davises
We Are The Davises
9.6M views 70.1K likes 5.2K dislikes 27 May 201665% match


Confectioners made ​​Fomy Minnie and Donald
Arte en Tus Manos
190.9K views 2.3K likes 105 dislikes 09 May 201665% match

KAYLA'S HAIR IS CHANGING | We Are The Davises
We Are The Davises
3.4M views 21.2K likes 926 dislikes 30 Sep 201765% match


Easy Knit Ribbed Hat For Adult Men and Women, How to knit for beginners, Knitting for Baby
Knitting for Baby
133.7K views 2.1K likes 77 dislikes 12 Nov 202065% match




Loops
CS50
42.2K views 95 likes 2 dislikes 07 Oct 201565% match










Malaysia Cuisine : An Introduction to Malaysian Food
Nomadic Samuel - Travel Channel
123.2K views 406 likes 28 dislikes 10 Jul 201465% match

「小白測評」 Mate40 Pro的8個熱點問題！風格大變今年不再爵士了~
Xiaobai's Tech Reviews
11.4K views 236 likes 14 dislikes 31 Oct 202064% match

OUR PUPPY IS ADDICTED TO YOUTUBE! | We Are The Davises
We Are The Davises
114.4K views 1.7K likes 53 dislikes 18 Sep 201664% match


BEST GARAGE SALE EVER
Riding Elevators with Lane
175K views 748 likes 204 dislikes 22 Jul 201264% match












Pune Food Tour! Foreigners trying Indian Sweets and Tandoori Chai in Pune, India
Samuel and Audrey - Travel and Food Videos
36.5K views 800 likes 29 dislikes 03 Jan 201964% match




EASY Knit baby hat for beginners 0-6M, KNIT HAT for baby boys and Girls KNITTING FOR BABY
Knitting for Baby
18.6K views 0 likes 0 dislikes 03 Jan 202164% match



劉伯溫用來鎖住孽龍的殘局：百年未分勝負，今天用AI成功破解【象棋教室】
Chess classroom
11.5K views 186 likes 13 dislikes 08 Nov 202064% match


Settings Privacy About Contact Donate