[Ag seinm ceoil] 

DOUG LLOYD: OK, mar sin chumasadh Is saghas fós algartam eile gur féidir linn a úsáid chun réiteach na gnéithe de eagar. Ach de réir mar beidh orainn a fheiceáil, tá sé fuair a difríocht an-bhunúsach ó saghas roghnú, mboilgeog a shórtáil, agus a chur isteach a shórtáil go mbeadh sé i ndáiríre cliste go leor. 

An smaoineamh bunúsach taobh thiar de merge Is saghas a shórtáil arrays níos lú agus ansin le chéile na arrays le chéile, nó a chumasadh them-- mar sin, an name-- in ord sórtáilte. An bealach go chumasadh saghas dhéanann tá sé seo ag giaráil uirlis ar a dtugtar athchúrsáil, a bhfuil cad táimid ag dul a bheith ag caint faoi go luath, ach ní mór dúinn Labhair i ndáiríre faoi go fóill. 

Seo an smaoineamh bunúsach taobh thiar de merge sórtáil. Sórtáil an leath clé den eagar, Is ag glacadh leis n níos mó ná 1. Agus cad is ciall agam nuair a rá liom Is ag glacadh leis n níos mó ná 1, I mo thuairimse, is féidir linn aontú go má eagar ach comhdhéanta de ghné amháin, tá sé curtha in eagar. Ní gá go hiarbhír aon ní a dhéanamh dó. Is féidir linn a dhearbhú ach é a bheith curtha in eagar. Tá sé ach eilimint amháin. 

Mar sin, an pseudocode, arís é, shórtáil an leath clé den eagar, ansin shórtáil an leath ceart an eagar, ansin chumasadh leis an dhá leath le chéile. Anois, cheana féin, d'fhéadfá a bheith ag smaoineamh, sé de chineál ar díreach fuaimeanna cosúil tú ag cur amach the-- nach bhfuil tú ag déanamh go hiarbhír rud ar bith. Tú ag rá shórtáil ar an taobh clé leath, a shórtáil an leath ceart, ach nach bhfuil tú ag insint dom conas atá tú a dhéanamh air. 

Ach cuimhnigh go chomh fada agus Is sraith gné amháin, Is féidir linn a dhearbhú curtha in eagar é. Ansin is féidir linn a chur le chéile ach iad le chéile. Agus sin i ndáiríre an smaoineamh bunúsach taobh thiar de merge sórtáil, Is é a bhriseadh síos ionas go tá do arrays de mhéid amháin. Agus ansin tú a atógáil ó ann. 

Merge sort Is cinnte algartam casta. Agus tá sé chomh maith le beagán casta a shamhlú. Mar sin tá súil againn, an léirshamhlú go bhfuil mé tá anseo cabhróidh leanann tú chomh maith. Agus beidh mé iarracht mo dhícheall chun rudaí a narrate agus dul ar aghaidh tríd an beagán níos mó moille ná na cinn eile ach a fháil tá súil againn do cheann ar fud na smaointe taobh thiar merge sórtáil. 

Mar sin, ní mór dúinn an sraith céanna leis an Físeáin algartam sórtáil eile má tá tú ag féachaint them-- raon sé gné. Agus is é ár cód pseudocode anseo saghas an leath chlé, shórtáil an leath ceart, chumasadh leis an dhá leath le chéile. Mar sin, a ligean ar ghlacadh an dearg bríce an-dorcha eagar agus a shórtáil an leath clé de. 

Mar sin, de thuras na huaire, táimid ag dul neamhaird a dhéanamh ar an stuif ar an gceart. Tá sé ann, ach tá muid Ní ag an céim go fóill. Níl muid ag saghas an leath ceart an eagar. Tá muid ag saghas an taobh clé leath de na eagar. Agus díreach ar mhaithe de bheith ina beagán níos mó soiléir, mar sin is féidir liom a tharchur leis an méid a céim táimid ar, Tá mé ag dul a athrú ar an dath an tacar a oráiste. Anois, tá muid ag caint go fóill mar gheall ar an leath clé céanna an eagar bunaidh. Ach tá mé ag súil go trí a bheith in ann a tharchur chuig na dathanna de na míreanna éagsúla, beidh sé a dhéanamh sé beagán níos soiléir cad atá ar siúl anseo. 

OK, mar sin anois ní mór dúinn a trí eagar eilimint. Conas is féidir linn a shórtáil an leath clé den eagar, atá fós an taisceadh sin? Táimid ag iarraidh a shórtáil ar an taobh clé leath de na brící dearga array-- an leath clé díobh Tá mé daite anois oráiste. 

Bhuel, d'fhéadfadh muid a iarracht a dhéanamh agus arís an próiseas seo arís. Mar sin, tá muid fós sa lár an iarraidh a shórtáil an leath clé den sraith iomlán. An leath clé den eagar, tá mé ag dul díreach tar éis chun cinneadh a dhéanamh treallach go bhfuil an leath clé Beidh a bheith níos lú ná an leath ceart, mar gheall ar a tharlaíonn sé seo a comhdhéanta de trí ghné. 

Agus mar sin tá mé ag dul a rá go bhfuil an leath clé den leath chlé an eagar ach an eilimint cúig. Cúig, is eilimint amháin eagar, tá a fhios againn conas a shórtáil sé. Agus mar sin tá sé a cúig curtha in eagar. Táimid ag dul díreach a dhearbhú go. Tá sé ina sraith eilimint amháin. 

Mar sin, tá muid curtha in eagar anois leath clé den half-- chlé nó in áit, tá muid curtha in eagar an leath clé den oráiste. Mar sin anois, d'fhonn a chomhlánú fós an sraith iomlán ar leath chlé, ní mór dúinn a shórtáil an leath ceart den oráiste, nó stuif seo. Conas is féidir linn é sin a dhéanamh? Bhuel, ní mór dúinn a sraith dhá eilimint. Mar sin, is féidir linn a shórtáil an leath chlé an eagar, a bhfuil dhá. Is eilimint amháin a Dó. Mar sin, tá sé curtha in eagar de réir réamhshocraithe. Ansin is féidir linn a shórtáil an leath ceart de chuid sin den eagar, an ceann. Sin saghas de réir réamhshocraithe. 

Tá sé seo anois an chéad uair tá muid bainte amach céim chumasadh. Táimid tar éis a curtha i gcrích, cé go tá muid ag anois de chineál ar neadaithe down-- agus go bhfuil saghas an tricky Is é rud a bhfuil recursion, is gá duit a choinneáil do ceann faoin áit a bhfuil muid. Mar sin, tá muid saghas na láimhe clé leath de na chuid oráiste. 

Agus anois, tá muid i lár an sórtáil an leath ceart an chuid oráiste. Agus sa phróiseas sin, tá muid faoi ​​anois a bheith ar an chéad chéim, chumasadh leis an dhá leath le chéile. Nuair a fhéachaimid ar an dhá leath an eagar, feicimid beirt agus ceann amháin. Cé acu an ghné is lú? One. 

Ansin a ghné is lú? Bhuel, tá sé dhá nó rud ar bith. Mar sin, tá sé dhá. Mar sin anois, ach a fráma arís áit a bhfuil muid i gcomhthéacs, ní mór dúinn curtha in eagar an leath clé den oráiste agus an leath ceart an tionscnaimh. Tá a fhios agam Tá mé athrú na dathanna arís, ach sin áit a raibh muid. Agus an chúis a rinne mé seo toisc go bhfuil an próiseas seo ag dul a choinneáil ag dul, iterating síos. Táimid tar éis curtha in eagar ar an taobh clé leath de na oráiste iar agus an leath ceart an oráiste iar. 

Anois, ní mór dúinn a chumasadh leis na dhá leath le chéile freisin. Sin an chéad chéim táimid ar. Mar sin, a mheasamar a bheith gach ceann de na gnéithe atá glas anois, an leath clé den eagar bunaidh. Agus muid chumasadh iad siúd ag baint úsáide as an bpróiseas céanna rinne muid chun chumasc dhá agus ceann díreach nóiméad ó shin. 

An leath chlé, is lú Is gné ar an leath clé cúig. An eilimint is lú ar Is é an leath ceart amháin. Cé acu de na daoine is lú? One. 

An eilimint is lú ar Is é an leath clé cúig. An eilimint is lú ar Is é an leath ceart dá. Cad é an lú? Dó. Agus ansin ar deireadh cúig agus rud ar bith, is féidir linn a rá cúig. 

OK, pictiúr chomh mór, a ligean ar sos a ghlacadh le haghaidh an dara agus figiúr amach cén áit a bhfuil muid. Má thosaigh muid ó an tús, ní mór dúinn a bheith críochnaithe anois le haghaidh an sraith iomlán ach céim amháin den chód pseudocode anseo. Táimid tar éis a curtha in eagar an leath clé den eagar. 

Thabhairt chun cuimhne go bhfuil an bunaidh Bhí ordú cúig, dhá, ceann amháin. Trí dul tríd an bpróiseas agus neadaithe síos agus athrá, leanúint ar aghaidh a bhriseadh an bhfadhb síos i gcodanna níos lú agus níos lú, mór dúinn i gcrích anois céim ar cheann de na pseudocode don eagar ag tosú ar fad. Táimid tar éis a curtha in eagar ar a leath chlé. 

Mar sin, anois a ligean ar reo ann. Agus lig anois ar shórtáil an ceart leath de na eagar bunaidh. Agus táimid ag dul a dhéanamh go bhfuil ag dul tríd an atriallach céanna próiseas rudaí a bhriseadh síos agus ansin chumasc le chéile iad. 

Mar sin, an leath clé den dearg, nó an leath clé an leath ceart an bunaidh Tá eagar, tá mé ag dul a rá trí. Arís, tá mé a bheith i gcomhréir anseo. Má tá tú corr roinnt gnéithe, sé nach ábhar i ndáiríre cé acu a dhéanann tú an ceann ar chlé lú nó an ceart amháin níos lú. 

Cad é ábhair go bhfuil aon uair tú bhíonn an fhadhb seo i mbun a chumasadh, ní mór duit a bheith comhsheasmhach. Ní mór duit ceachtar i gcónaí chun dhéanamh taobh clé lú nó is gá i gcónaí a dhéanamh an taobh deas níos lú. Anseo, tá mé a roghnaíodh chun i gcónaí a dhéanamh ar an taobh clé lú nuair a mo eagar, nó mo fo-sraith, is de mhéid corr. 

Is trí eilimint amháin, agus mar sin tá sé curtha in eagar. Táimid tar éis giaráilte go toimhde ar fud ár bpróiseas ar fad go dtí seo. Mar sin, anois a ligean ar shórtáil an ceart leath de na leath ceart, nó an leath ceart an dearg. 

Arís, ní mór dúinn a roinnt ar an síos. Ní hé seo an eagar eilimint amháin. Ní féidir linn a dhearbhú curtha in eagar é. Agus mar sin an chéad, táimid ag dul a shórtáil an leath clé. 

Is é an leath clé gné amháin, mar sin tá sé saghas de réir réamhshocraithe. Ansin táimid ag dul a shórtáil an ceart leath, a bhfuil gné amháin. Tá sé seo curtha in eagar de réir réamhshocraithe. Agus anois, Is féidir linn a chumasadh dá chéile. Ceithre níos lú, agus ansin tá sé níos lú. 

Arís, ní mór an méid atá déanta againn ag an bpointe seo? Táimid tar éis curtha in eagar ar an taobh clé leath de na leath ceart. Nó ag dul ar ais go dtí an bunaidh dathanna a bhí ann, tá muid curtha in eagar ar an taobh clé leath de na dearg níos boige. Bhí sé ar dtús bríce dorcha dearg agus anois tá sé ina dearg níos boige, nó go raibh sé ina dearg níos boige. 

Agus ansin tá muid curtha in eagar an leath do cheart an dearg níos boige. Anois, go maith, tá siad glas arís, ach mar gheall orainn ag dul trí phróiseas. Agus ní mór dúinn a dhéanamh arís an thar agus os a chionn. 

Mar sin, anois is féidir linn a chumasadh iad siúd dhá leath le chéile. Agus sin an méid a dhéanaimid anseo. Mar sin, an líne dhubh díreach roinneadh an leath clé agus an leath ceart an chuid saghas. 

Déanaimid comparáid idir an luach is lú ar an taobh clé den array-- nó leithscéal dom, an ceann is lú luach an leath clé leis an luach is lú de na gceart leath agus a fháil go bhfuil trí níos lú. Agus anois le beagán de leas iomlán a bhaint, ceart? Níl aon rud i ndáiríre fágtha ar an taobh clé. 

Níl rud ar bith fágtha ar an taobh clé, ionas gur féidir linn a héifeachtach ach is féidir linn a dhearbhú move-- tá an chuid eile de sé i ndáiríre curtha in eagar agus díreach tack é ar, mar níl rud ar bith eile a chur i gcomparáid i gcoinne. Agus tá a fhios againn go bhfuil an taobh dheis de an taobh deas atá curtha in eagar. 

OK, mar sin anois a ligean ar reo arís agus figiúr amach áit a bhfuil muid sa scéal. Sa eagar foriomlán, an méid atá i gcrích againn? Táimid tar éis a chur i gcrích i ndáiríre céimeanna anois ar cheann agus céim a dó. Curtha in eagar muid an leath chlé, agus curtha in eagar muid an leath ceart. 

Mar sin anois, tá gach uile go bhfanann dúinn a chumasadh iad siúd dá leath le chéile. Mar sin, táimid i gcomparáid leis an líon is ísle luacháil eilimint de gach leath den eagar seal agus dul ar aghaidh. Is é ceann níos lú ná trí, mar sin téann amháin. 

Dhá níos lú ná trí, mar sin de dhá téann. Trí níos lú ná 5, mar sin trí téann. Ceithre níos lú ná 5, mar sin téann ceithre. Ansin tá cúig lú ná sé, agus tá sé go léir go bhfanann. 

Anois, tá a fhios agam, go raibh a lán de na céimeanna. Agus tá muid fhág a lán de chuimhne in ár ndiaidh. Agus sin cad iad na cearnóga liath. Agus bhraith sé is dócha mar tharla go lán níos faide ná a chur isteach a shórtáil, mboilgeog saghas, nó a shórtáil roghnóireachta. 

Ach i ndáiríre, mar gheall ar a lán de na próisis seo atá ag tarlú ag an time-- céanna a bhfuil rud éigin go mbainfidh linn a, arís, labhairt faoi nuair a labhairt linn faoi athchúrsáil i todhchaí video-- an algartam iarbhír Is léir go bunúsach éagsúla ná rud ar bith feicthe againn roimh ach freisin go suntasach níos éifeachtaí. 

Cén fáth é sin? Bhuel, i an ceann is measa scéal cás, ní mór dúinn a scoilt n-eilimintí suas agus ansin iad a recombine. Ach nuair recombine linn a iad, cad táimid ag déanamh Tá dúbailt bunúsach ar an méid de na arrays níos lú. Ní mór dúinn a bunch de ghné amháin arrays go ndéanaimid go héifeachtach le chéile i dhá arrays eilimint. Agus ansin a chur orainn iad siúd dhá arrays eilimint agus iad a chur le chéile le chéile i ceithre eagair eilimint, agus mar sin de, agus mar sin de, agus mar sin de, go dtí go táimid ag go mbeadh sraith eilimint n aonair. 

Ach cé mhéad doublings a thógann sé chun a fháil chun n? Smaoinigh ar ais go dtí an sampla leabhar gutháin. Cé mhéad uair a dhéanann againn le clib an leabhar teileafóin i leath, cé mhéad níos mó amanna a dhéanann ní mór dúinn a cuimilt an leabhar teileafóin i leath, más rud é an méid de na leabhar teileafóin dhó? Níl ach ceann amháin, ceart? 

Mar sin, níl chineál éigin eilimint logartamach anseo. Ach ní mór dúinn freisin go fóill ar a laghad féachaint ar gach ceann de na heilimintí n. Mar sin, i chás is measa, chumasadh Ritheann saghas i n logáil n. Ní mór dúinn chun breathnú ar gach ceann de na heilimintí n, agus ní mór dúinn a chur le chéile iad le chéile i logáil n tacair de céimeanna. Sa chás is fearr, Tá an eagar curtha in eagar go foirfe. Go mór. Ach atá bunaithe ar an algartam bhfuil muid anseo, ní mór dúinn fós a scoilt agus recombine. Cé gur sa chás seo, an Is recombining de chineál ar neamhéifeachtach. Níl sé ag teastáil. Ach táimid ag dul go fóill trí an próiseas iomlán ar aon nós. 

Mar sin, sa chás is fearr agus i gcás is measa, Ritheann an algartam i n logáil n am. Merge saghas Is cinnte le beagán trickier ná na halgartaim eile príomh sórtáil tá muid Labhair faoi CS50 ach tá i bhfad níos cumhachtaí. 

Agus mar sin má tú riamh ócáid ​​a bhfuil sé de dhíth nó é a úsáid a shórtáil ar tacar sonraí mór, ag fáil do cheann ar fud an smaoineamh recursion ag dul a bheith i ndáiríre cumhachtacha. Agus tá sé ag dul a dhéanamh do Cláir i ndáiríre i bhfad níos éifeachtaí ag baint úsáide as merge sórtáil i gcoinne aon rud eile. Tá mé Doug Lloyd. Is é seo an CS50.