DOUG LLOYD: Mar sin, i CS50 d'fhoghlaim muid faoi ar éagsúlacht na sórtáil agus cuardach halgartaim. Agus uaireanta is féidir é a bheith beag tricky a choinneáil dhéanann súil a choinneáil ar cén algartam cad. Tá muid i ndáiríre ach bearrtha an dromchla freisin, tá go leor eile chuardach agus halgartaim sórtáil. Mar sin, i físeán seo a ligean ar ach cúpla nóiméad a ghlacadh chun iarracht a dhéanamh agus a distill gach algartam síos go dtí a eilimintí lárnacha ionas gur féidir leat cuimhneamh ar an chuid is mó eolas tábhachtach mar gheall orthu agus a bheith in ann a chur in iúl ar an difríochtaí, más gá. 

Is é an chéad saghas roghnaithe. An smaoineamh bunúsach taobh thiar de saghas roghnaithe Tá teacht ar an ghné is lú neamhshórtáilte i sraith agus bhabhtáil sé leis an chéad eilimint neamhshórtáilte den eagar. Dúirt muid go raibh an ceann is measa ar chás reáchtáil am sin bhí n cearnógach. Agus más mian leat a thabhairt chun cuimhne cén fáth, a chur a féachaint ar na físeáin saghas roghnaithe. An t-am is fearr a reáchtáil ar chás Tá n cearnaithe freisin. 

Saghas mboilgeog, an smaoineamh taobh thiar de sin tá sé ar cheann a mhalartú péirí cóngaracha. Mar sin, go bhfuil an eochair a chuidíonn leat cuimhneamh ar an difríocht anseo. Roghnú saghas is é sin, go dtí seo, teacht ar an mboilgeog smallest-- saghas é sin mhalartú péirí cóngaracha. Babhtála táimid ag péirí cóngaracha na n-eilimintí má tá siad atá as ordú, a go héifeachtach boilgeoga gnéithe níos mó leis an gceart, agus ag an am céanna tosaíonn sé freisin chun bogadh eilimintí níos lú ar an taobh clé. An ceann is measa ar chás am cás a reáchtáil de mboilgeog saghas atá cearnaithe n. An t-am is fearr a reáchtáil ar chás de mboilgeog Is saghas n. Toisc i staid sin ní féidir linn a actually-- D'fhéadfadh ní mór dúinn a aon babhtálacha ar chor ar bith. Ní mór dúinn ach a dhéanamh ar cheann pas a fháil ar fud gach gné n. 

I chur isteach a shórtáil, an Tá smaoineamh bunúsach anseo aistriú. Sin an eochairfhocal do chur isteach saghas. Táimid ag dul chun dlús uair amháin trí an sraith ó chlé go deas. Agus mar a bhíonn againn, tá muid dul chun eilimintí aistriú againn le feiceáil cheana féin seomra a dhéanamh le haghaidh cinn níos lú gur gá a d'oirfeadh áit éigin ar ais sa chuid sin curtha in eagar. Mar sin, a thógáil againn ar an sraith sórtáilte amháin eilimint ag an am, ó chlé go deas, agus athrú muid rudaí seomra a dhéanamh. An t-am a reáchtáil is measa ar chás de Tá a chur isteach a shórtáil cearnógach n. Is é an t-am is fearr ar chás reáchtáil n. 

Cumaisc sort-- an eochairfhocal anseo scoilt agus chumasadh. Scoilt muid an sraith iomlán, cibé acu tá sé sé gnéithe, ocht ngné, 10,000 elements-- scoilt muid é síos ag leath, ag leath, ag leath, go dtí go atá againn faoi eagar de n amháin arrays eilimint. Sraith de n amháin arrays eilimint. Mar sin, thosaigh muid le ceann amháin Sraith 1,000-eilimint, agus a fhaigheann muid go dtí an pointe nuair a muid tá 1,000 eagair aon-eilimint. Ansin muid ag cur tús a chumasadh leis na arrays fo ar ais le chéile san ord ceart. Mar sin, a chur orainn dhá arrays aon-eilimint agus a chruthú sraith dhá-eilimint. A chur orainn dhá arrays dhá eilimint agus a chruthú sraith ceithre eilimint agus mar sin de agus mar sin de go dtí go bhfuil muid arís atógadh amháin eagar gné n. 

An t-am a reáchtáil is measa ar chás de merge sórtáil é sin n uair logáil n. Ní mór dúinn gnéithe n, ach an próiseas seo recombining Bíonn logáil n céimeanna a fháil ar ais go dtí raon iomlán. Is é an cás is fearr am siúl freisin n logáil n toisc nach bhfuil an próiseas seo i ndáiríre cúram an raibh an eagar curtha in eagar nó gan tús a chur leis. Tá an próiseas mar an gcéanna, níl aon bhealach chun rudaí a chuaird gearr. Mar sin, n logáil isteach n sa chás is measa, n logáil isteach n sa chás is fearr. 

Labhair muid thart ar dhá halgartaim cuardach. Dá bhrí sin tá cuardach líneach gheall iterating. Dul ar aghaidh muid trasna an eagar uair amháin, ó chlé go deas, ag iarraidh a fháil ar an líon go bhfuil muid ag lorg. Is é an t-am is measa ar chás reáchtáil O mór de n. D'fhéadfadh sé a ghlacadh chugainn iterating trasna gach gné amháin chun teacht ar an eilimint táimid ag lorg do, bíodh sé sa phost seo caite, nó nach bhfuil ag gach. Ach ní féidir linn a dheimhniú go dtí go tá muid d'fhéach sé ar gach rud. m an chuid is fearr ar chás, feicimid láithreach. An t-am is fearr a reáchtáil-gcás Tá cuardach líneach óimige de 1. 

Ar deireadh, ní raibh cuardaigh dhénártha, a éilíonn eagar assorted. Cuimhnigh go bhfuil an- breithniú tábhachtach iad ag obair le cuardaigh dénártha. Tá sé ina réamhriachtanas chun úsáid a bhaint it-- an eagar go bhfuil tú ag lorg trí Ní mór a shórtáil. Seachas sin, an eochairfhocal Tá deighilt agus conquer. Scoilt an eagar i leath agus deireadh a chur leis ar leath de na heilimintí gach uair mar a théann tú tríd. Mar gheall ar an scoilt agus conquer agus rudaí scoilteadh i gcur chuige leath, an t-am a reáchtáil is measa ar chás Is de cuardaigh dénártha logáil n, atá i bhfad níos fearr ná cuardach líneach ar n. Is é an t-am is fearr ar chás ar siúl fós ar cheann. 

D'fhéadfadh muid a aimsiú láithreach an chéad uair a dhéanamh linn le roinn, ach, arís, cuimhnigh go cé go bhfuil cuardaigh dhénártha go substaintiúil níos fearr ná cuardaigh líneach de bhua a bheith logáil n versus n, a bheadh ​​agat chun dul tríd an obair de sórtáil do eagar ar dtús, a d'fhéadfadh é a dhéanamh chomh héifeachtach ag brath ar an méid de na iterating curtha in eagar. 

Tá mé Doug Lloyd, is é seo CS50.