MARK GROZEN-SMITH: Dia duit, Tá mé Mark Grozen-Smith, agus tá sé seo Quicksort. Díreach cosúil le saghas a chur isteach agus mboilgeog saghas, tá Quicksort algartaim do sórtáil liosta nó sraith de rudaí. Chun simplíocht, a ligean ar glacadh leis go bhfuil sin Tá rudaí ach slánuimhreacha, ach Tá a fhios go n-oibríonn Quicksort do níos mó ná díreach uimhreacha. Is Mearthosú le beagán níos casta ná a chur isteach nó mboilgeog, ach tá sé freisin i bhfad níos éifeachtaí i bhformhór na gcásanna. Fan dara. An ndúirt sé ach "an chuid is mó cásanna, "ní" gach "? Suimiúil go leor, uimh. Tá Níl gach cás mar an gcéanna. Ná bíodh imní ort faoi seo go mion má tá tú nach bhfuil le feiceáil nodaireacht O mór go fóill, ach Is Quicksort O (n cearnógach) algartam ag measa, díreach cosúil a chur isteach nó mboilgeog saghas. Mar sin féin, gníomhaíonn sé de ghnáth i bhfad níos mó cosúil le aschur sean m algartam. Cén fáth? Beidh muid a fháil ar ais go dtí sin ina dhiaidh sin. Ach do anois, a ligean ar fhoghlaim ach conas a oibríonn Quicksort. 

Mar sin, a ligean ar siúl tríd Quicksorting seo sraith de slánuimhreacha ón gceann is lú a is mó. Anseo ní mór dúinn an slánuimhreacha 6, 5, 1, 3, 8, 4, 7, 9, agus 2. Gcéad dul síos, roghnaigh muid an eilimint deiridh de seo sraith - sa chás seo, dhá - agus glaoch go bhfuil an "pivot." Next, ní mór dúinn tús a chur chun breathnú ar dhá rud - ceann amháin, an t-innéacs is ísle, a beidh mé tagairt mar atá ag fanacht leis an gceart an balla, agus, dhá cheann, an leftmost eilimint, a beidh mé glaoch ar an "reatha eilimint. "Cad tá muid ag dul a dhéanamh ná breathnú ar fad na gnéithe eile, eile ná an mhaighdeog, agus go léir a chur ar na gnéithe níos lú ná an mhaighdeog ar an d'fhág an bhalla agus dóibh siúd go léir níos mó ná an mhaighdeog ar an ceart an bhalla. Ansin, ar deireadh, beidh muid ag titim ar an mhaighdeog ar dheis ar an mballa chun é a chur idir na huimhreacha níos lú ná sé agus na uimhreacha níos mó. 

Mar sin, a ligean ar é sin a dhéanamh. Pioc suas an 2, a chur ar an bhalla ag an ag tosú, agus glaoch ar an 6 "reatha eilimint. "Mar sin, ba mhaith linn chun breathnú ar ár n-eilimint ann faoi láthair, an 6. Agus ós rud é tá sé níos mó ná an 2, a fhágann muid é ansin go dtí an ceart an bhalla. Ansin, táimid ag bogadh ar aghaidh chun breathnú ar an 5 mar ár eilimint reatha agus a fheiceáil go bhfuil an is é, arís, níos mó ná an mhaighdeog, mar sin againn fág é ina bhfuil sé ar dheis taobh den bhalla. Táimid bogadh ar aghaidh. Is é ár gné reatha anois 1, agus - OH. Tá sé seo difriúil anois. Is é an ghné reatha anois níos lú ná an mhaighdeog, mar sin ba mhaith linn a chur air ar an taobh clé den bhalla. Chun seo a dhéanamh, a ligean ar aistriú ach an eilimint ann faoi láthair leis an innéacs is ísle ach suí do cheart an bhalla. Anois, sinn ag dul ar an bhalla suas innéacs amháin mar sin tá an 1 ar chlé taobh den bhalla anois. 

Fan. Measctha mé díreach suas na heilimintí ar an taobh na láimhe deise den bhalla, ní raibh mé? Ná bíodh imní ort. Sin breá. An rud amháin a cúram againn faoi do anois is é sin na heilimintí go léir ar an ceart an bhalla go bhfuil níos mó ná an mhaighdeog. Níl aon ordú iarbhír Glactar leis go fóill. 

Anois, ar ais go dtí a shórtáil. Mar sin, leanaimid ar aghaidh ar ag féachaint ar an chuid eile de na heilimintí. Agus sa chás seo, feicimid go bhfuil aon eilimintí eile lú ná an mhaighdeog, mar sin a fhágáil dúinn iad go léir ar an taobh na láimhe deise den bhalla. Mar fhocal scoir, a fháil againn chun an eilimint atá ann faoi láthair agus a fheiceáil go bhfuil sé an mhaighdeog. Anois, Ciallaíonn sé sin go bhfuil muid beirt codanna de na eagar, an chéad á beag ar an mhaighdeog agus ar an taobh clé an bhalla, agus an dara á níos mó ná an mhaighdeog ar an taobh na láimhe deise den bhalla. Ba mhaith linn a chur ar an eilimint mhaighdeog idir an dá, agus ansin beidh a fhios againn go bhfuil an pivot ina cheart áit deiridh curtha in eagar. Mar sin, táimid ag aistriú an chéad eilimint ar an taobh na láimhe deise den bhalla leis an mhaighdeog, agus tá a fhios againn ar an mhaighdeog ar ina sheasamh ceart. 

Táimid arís ansin an próiseas seo do na subarrays chlé agus ar dheis ar an mhaighdeog. Ós rud é go bhfuil an subarray seo caite ach amháin eilimint fada, tá a fhios againn go bhfuil cheana féin sórtáilte mar gheall ar conas is féidir leat a bheith as a ordú má tá tú ach eilimint amháin? Chun an taobh dheis de na subarray, táimid ag a fheiceáil go bhfuil an pivot 5, agus an balla fágtha ach na 6. Agus an eilimint atá ann faoi láthair chomh maith Tosaíonn amach mar an 6. Mar sin, tá 6 níos mó ná 5. Saoire againn sé i gcás ina bhfuil sé ar an taobh na láimhe deise den bhalla. Anois, ag bogadh ar aghaidh, tá 3 níos lú ná 5. Mar sin, táimid ag aistriú sé leis an chéad eilimint díreach i gceart ar an bhalla. Anois, bhog mé an balla suas amháin. Anois, ag bogadh ar aghaidh go dtí an 8. 8 Tá níos mó ná 5, agus mar sin a fhágann muid é. Is é an 4 níos lú ná 5, mar sin athrú dúinn é. Agus ar. Agus ar. 

Gach uair arís againn ar an bpróiseas ar an taobh chlé agus ar dheis ar an eagar. againn roghnú mhaighdeog agus a dhéanann na comparáidí agus a chruthú ar leibhéal eile ar chlé agus subarrays ceart. Beidh an glao athchúrsach ar aghaidh go dtí a bhaint amach againn an deireadh nuair a tá muid roinnte suas an sraith iomlán i ach subarrays d'fhad 1. Ó ann, tá a fhios againn go bhfuil an sraith curtha in eagar toisc go bhfuil gach eilimint, ag pointe áirithe, ina mhaighdeog. I bhfocail eile, do gach eilimint, gach Is iad na huimhreacha ar an taobh clé lú luachanna agus na huimhreacha go dtí an Tá luachanna níos mó ceart. 

Oibríonn an modh seo an-maith má tá an Is é luach an mhaighdeog roghnaithe thart i lár raon de luachanna liosta. Chiallódh sé seo go, tar éis dúinn bogadh eilimintí thart, tá thart ar an oiread gnéithe ar an taobh clé den mhaighdeog mar go bhfuil go dtí an ceart. Agus nádúr scoilt-agus-conquer an Tá algartam Quicksort tógadh ansin buntáiste iomlán de. Cruthaíonn sé seo runtime O (n logáil n,) an n toisc go bhfuil muid a dhéanamh n lúide 1 comparáidí ar gach glúin agus logáil n toisc go bhfuil muid a roinnt ar an liosta logáil amanna n. Mar sin féin, sna cásanna is measa, an Is féidir le algartam a iarbhír O (n cearnógach.) Cuir ar gach glúin, an mhaighdeog tharlaíonn ach sin a bheith ar an is lú nó an ceann is mó de na uimhreacha táimid ag sórtáil. Chiallódh sé seo a bhriseadh síos ar an liosta n amanna agus ag déanamh n lúide 1 comparáidí gach uair amháin. Dá bhrí sin, o n cearnógach. 

Conas is féidir linn feabhas a chur ar an modh? Is é ceann bhealach maith chun feabhas a chur ar an modh a ghearradh síos ar an dóchúlacht go Is é an runtime riamh iarbhír o n cearnógach. Cuimhnigh seo measa, cás is measa Is féidir tarlú ach amháin nuair a Is mhaighdeog a roghnaíodh i gcónaí ar an airde nó an luach is ísle sa eagar. Chun a chinntiú go bhfuil sé seo níos lú seans ann go dtarlódh, is féidir linn teacht ar an mhaighdeog ag roghnú eilimintí éagsúla agus ag cur an luach meánach. 

Is é mo ainm Mark Grozen-Smith, agus tá sé seo CS50. 

Chun simplíocht, a ligean ar glacadh leis go bhfuil sin Tá rudaí ach slánuimhreacha, ach Tá a fhios go bhfuil Quicksert - Quicksert? Tá brón orm. 

Anseo ní mór dúinn an slánuimhreacha 6, 5, 1, 3, 8, 4, 9. 

Cainteoir 1: really? 

Cainteoir 2: Ná stop a chur ann. 

Cainteoir 1: really?