>> [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.