[CHWARAE CERDDORIAETH] 

DOUG LLOYD: Felly fath gosod yn un arall algorithm gallwn ei ddefnyddio i ddatrys arae. Y syniad y tu ôl i algorithm hwn yw i adeiladu eich array ddidoli yn eu lle, gan symud elfennau y tu allan i y ffordd wrth i chi fynd, i wneud lle. Mae hyn ychydig yn wahanol o fath dethol neu swigod didoli, er enghraifft, lle rydym yn addasu y lleoliadau, lle rydym yn gwneud cyfnewidiadau. 

Yn yr achos hwn yr hyn rydym yn mewn gwirionedd wneud yw elfennau symudol drosodd, allan o'r ffordd. Sut mae algorithm hwn gweithio mewn pseudocode? Wel gadewch i ni jyst fympwyol dweud bod y Elfen gyntaf y rhesi yn cael ei datrys. Rydym yn adeiladu yn ei lle. 

Rydym yn gonna yn mynd un elfen ar y tro a adeiladu, ac felly y peth cyntaf a welwn yn un elfen arae. A thrwy ddiffiniad, yn un Elfen amrywiaeth yn cael ei datrys. 

Yna byddwn yn ailadrodd y broses hon until-- byddwn yn ailadrodd y broses ganlynol nes bod yr holl elfennau yn cael eu datrys. Edrychwch ar yr elfen heb eu didoli nesaf ac mewnosod i mewn y rhan ddidoli, drwy symud y nifer gofynnol o elfennau allan o'r ffordd. Gobeithio delweddu hwn Bydd yn eich helpu i weld yn union beth sydd mynd ymlaen gyda'r math fewnosod. 

Felly eto, dyma ein array heb eu didoli cyfan, yr holl elfennau a nodir mewn coch. A gadewch i ni ddilyn y camau ar ein pseudocode. Y peth cyntaf a wnawn, yn cael ei alwn y Elfen gyntaf y rhesi, didoli. Felly rydym yn unig lais gonna pump, rydych yn datrys erbyn hyn. 

Yna, rydym yn edrych ar y nesaf Elfen heb eu didoli y rhesi ac yr ydym am i fewnosod bod i mewn i'r gyfran didoli, drwy symud elfennau drosodd. Felly ddau yw heb eu didoli y nesaf elfen y rhesi. Yn amlwg mae'n perthyn gerbron y pump, felly yr hyn yr ydym yn gonna ei wneud yn fath o cynnal dau o'r neilltu am eiliad, sifft pump drosodd, ac yna rhowch dau cyn pump, ble i fynd. Ac yn awr gallwn ddweud bod dau yn cael ei datrys. 

Felly, fel y gwelwch, mae gennym dim ond hyd yn hyn edrych ar ddwy elfen y rhesi. Nid ydym wedi edrych ar y gorffwys o gwbl, ond rydym wedi got rhai ddwy elfen trefnu yn ôl ffordd y mecanwaith symud. 

Felly, rydym yn ailadrodd y broses eto. Edrychwch ar y heb eu didoli nesaf Elfen, dyna un. Gadewch i ni ddal hynny o'r neilltu am eiliad, symud popeth drosodd, a rhowch un lle y dylai fynd. 

Unwaith eto, yn dal, rydym wedi dim ond erioed edrych ar un, dau, a phump. Nid ydym yn gwybod beth arall yn dod, ond rydym wedi datrys tair elfen hynny. 

Elfen heb eu didoli nesaf yw tri, felly byddwn yn gosod o'r neilltu. Byddwn yn newid dros yr hyn yr ydym Mae angen sydd, y tro hwn Nid yw popeth fel yn yr blaenorol dau achos, dim ond y pum. Ac yna byddwn yn cadw tri yn, rhwng y ddau a'r pump. 

Chwech yw'r nesaf heb eu didoli elfen i'r casgliad. Ac yn wir chwech yn fwy na phump, felly Nid oes angen hyd yn oed i ni wneud unrhyw gyfnewid. Gallwn jyst tac chwe dde i'r diwedd y gyfran didoli. 

Yn olaf, pedwar yn y Elfen heb eu didoli diwethaf. Felly, byddwn yn gosod o'r neilltu, newid drosodd yr elfennau y mae angen i symud drosodd, ac yna ei roi pedwar lle mae'n perthyn. Ac yn awr yn edrych, rydym wedi didoli o'r holl elfennau. Sylwch â mewnosod didoli, nid oedd gennym i fynd yn ôl ac ymlaen ar draws y rhesi. Byddwn ond yn mynd ar draws yr amrywiaeth un tro, ac yr ydym yn symud pethau y byddem yn dod ar eu traws yn barod, er mwyn i wneud lle ar gyfer yr elfennau newydd. 

Felly beth yw'r achos gwaethaf senario gyda'r math fewnosod? Yn yr achos gwaethaf, mae'r amrywiaeth yn ôl. Mae'n rhaid i chi symud pob un o'r elfennau n hyd i swyddi n, bob tro yr ydym yn sengl gwneud mewnosod. Mae hynny'n llawer o symud. 

Yn yr achos gorau, mae'r amrywiaeth yn cael ei ddidoli yn berffaith. Ac yn fath o fel hyn a ddigwyddodd gyda pump a chwech yn yr enghraifft, lle y gallai rydym yn unig tac ymlaen heb orfod gwneud unrhyw symud, byddem yn ei hanfod yn gwneud hynny. 

Os ydych yn dychmygu y bydd ein arae yn un drwy chwech, byddem yn dechrau ffwrdd gan datgan un yn cael ei datrys. Mae dau yn dod ar ôl un, felly y gallwn yn unig dweud, OK, wel un a dau yn cael eu didoli. Tair dod ar ôl dwy felly, OK, un a dau a thri yn cael eu didoli. 

Nid ydym yn gwneud unrhyw cyfnewidiadau, rydym yn dim ond symud y llinell hon mympwyol rhwng didoli a heb eu didoli wrth i ni fynd. Mor effeithiol ag y gwnaethom yn yr enghraifft, troi elfennau glas, wrth i ni fwrw ymlaen. Felly beth yw'r Rhedeg achos gwaethaf, felly? Cofiwch, os oes rhaid inni symud pob un o'r yr elfennau n swyddi n bosibl, gobeithio sy'n rhoi i chi syniad bod yr achos gwaethaf Rhedeg yn O Big n sgwâr. 

Os yw'r amrywiaeth yn berffaith didoli, pob mae'n rhaid i ni wneud yn edrych ar bob elfen unigol unwaith, ac yna rydym yn ei wneud. Felly, yn yr achos gorau, mae'n omega o n. 

Rwy'n Doug Lloyd. Mae hyn yn CS50.