>> [CHWARAE CERDDORIAETH]
DOUG LLOYD: pob hawl, felly didoli swigen yn algorithm
gallwch ei ddefnyddio i ddatrys cyfres o elfennau.
Gadewch i ni edrych ar sut y mae'n gweithio.
>> Felly, y syniad sylfaenol y tu ôl math swigen yn hyn.
Rydym yn gyffredinol yn awyddus i symud yn uwch elfennau gwerthfawr yn gyffredinol ar y dde,
ac yn is elfennau gwerthfawr yn gyffredinol ar y chwith, fel y byddem yn ei ddisgwyl.
Rydym am i'r pethau isaf i fod ar y dechrau, a'r pethau uwch
i fod ar y diwedd.
>> Sut ydym ni'n gwneud hyn?
Yn dda yn y cod pseudocode, gallem ddweud, gadewch i ni
gosod cownter cyfnewid at werth nad yw'n sero.
Cawn weld pam rydym yn gwneud hynny mewn eiliad.
Ac yna rydym yn ailadrodd y canlynol broses nes bod y cownter cyfnewid yn 0,
neu hyd nes y byddwn yn gwneud unrhyw gyfnewidiadau o gwbl.
>> Ailosod y cownter cyfnewid i 0 os nad yw'n barod 0.
Yna edrych ar bob pâr cyfagos o elfennau.
Os bydd y ddwy elfen yn Nid yw mewn trefn, cyfnewid nhw,
ac yn ychwanegu 1 i'r cownter cyfnewid.
Os ydych chi'n meddwl am hyn cyn i chi ddychmygu iddo,
yn sylwi y bydd hyn yn symud yn is elfennau gwerthfawr i'r chwith
ac elfennau ar y dde gwerthfawr uwch, wneud yn effeithiol yr hyn yr ydym am ei wneud,
sydd yn symud grwpiau hynny o elfennau yn y ffordd honno.
Gadewch i ddychmygu sut mae hyn yn Gallai edrych ddefnyddio ein amrywiaeth
ein bod yn eu defnyddio i brofi allan algorithmau hyn.
Mae gennym amrywiaeth heb ei ddidoli yma unwaith eto, a nodir gan bob un o'r elfennau
bod mewn coch.
Ac yr wyf yn gosod fy cownter cyfnewid at werth nonzero.
Yr wyf yn fympwyol dewis negyddol 1-- nid yw'n 0.
Rydym yn awyddus i ailadrodd y broses hon nes bod y cownter cyfnewid yw 0.
Dyma pam yr wyf yn gosod fy cyfnewid groes i ryw werth heb fod yn sero,
oherwydd fel arall y Byddai cownter gyfnewid fod yn 0.
Ni fyddem yn hyd yn oed yn dechrau ar y proses y algorithm.
Felly eto, y camau yw-- ailosod y cownter cyfnewid
i 0, ac yna edrych ar bob cyfagos pâr, ac os ydyn nhw allan o drefn,
cyfnewid nhw, ac yn ychwanegu 1 at y cownter cyfnewid.
Felly gadewch i ni ddechrau y broses hon.
Felly, y peth cyntaf yr ydym yn ei wneud yw rydym yn gosod y cownter cyfnewid i 0,
ac yna rydym yn dechrau edrych ym mhob pâr cyfagos.
>> Felly, rydym yn gyntaf dechrau edrych ar 5 a 2.
Rydym yn gweld eu bod allan o archebu ac felly rydym yn eu cyfnewid.
Ac rydym yn ychwanegu 1 i'r cownter cyfnewid.
Felly nawr ein cownter cyfnewid yw 1, a 2 a 5 wedi cael eu diffodd.
Nawr rydym yn ailadrodd y broses eto.
>> Rydym yn edrych ar y pâr cyfagos nesaf, 5 a 1-- maen nhw hefyd allan o drefn,
felly rydym yn eu cyfnewid ac ychwanegu 1 i'r cownter cyfnewid.
Yna, rydym yn edrych ar 5 a 3.
Maent yn cael eu allan o drefn, felly rydym yn gyfnewid iddynt ac rydym yn ychwanegu 1 i'r cownter cyfnewid.
Yna, rydym yn edrych ar 5 a 6.
Maen nhw mewn trefn, felly nid ydym yn ei wneud mewn gwirionedd Mae angen i gyfnewid unrhyw beth y tro hwn.
Yna, rydym yn edrych ar 6 a 4.
Maen nhw hefyd allan o drefn, felly rydym yn gyfnewid iddynt ac rydym yn ychwanegu 1 i'r cownter cyfnewid.
>> Nawr sylwi ar yr hyn sydd wedi digwydd.
Rydym wedi symud 6 yr holl ffordd i'r diwedd.
Felly, yn y math dewis, os ydych chi wedi gweld bod fideo, yr hyn a wnaethom oedd
rydym yn dod i ben i fyny yn symud y elfennau lleiaf yn adeilad
yr amrywiaeth ddidoli yn y bôn o o'r chwith i'r dde, o'r lleiaf i'r mwyaf.
Yn achos math swigen, os ydym yn yn dilyn hyn algorithm penodol,
rydym yn mewn gwirionedd yn mynd i gael ei adeiladu yr amrywiaeth ddidoli o'r dde
i'r chwith, mwyaf i'r lleiaf.
Rydym wedi bubbled 6, mae'r effeithiol gwerth mwyaf, yr holl ffordd hyd y diwedd.
>> Ac felly y gallwn ddatgan yn awr bod hynny'n cael ei ddidoli,
ac yn y dyfodol iterations-- mynd drwy'r llu again--
Nid oes rhaid i ni ystyried 6 anymore.
Dim ond i ni ystyried yr elfennau heb eu didoli
pan fyddwn yn edrych ar barau cyfagos.
Felly rydym wedi gorffen un mynd trwy fath swigen.
Felly nawr rydym yn mynd yn ôl at y cwestiwn, ailadrodd nes bod y cownter cyfnewid yw 0.
Wel y cownter cyfnewid yw 4, felly rydym yn mynd
i gadw ailadrodd y broses hon eto.
>> Rydym yn mynd i ailosod y cownter cyfnewid i 0, ac yn edrych ar bob pâr cyfagos.
Felly, rydym yn dechrau gyda 2 a 1-- eu bod allan o drefn, felly rydym yn eu gyfnewid
ac rydym yn ychwanegu 1 i'r cownter cyfnewid.
2 a 3, eu bod mewn trefn.
Nid oes angen i ni wneud unrhyw beth.
3 a 5 mewn trefn.
Nid oes angen i ni wneud unrhyw beth yno.
>> 5 a 4, maent yn cael eu allan o drefn, ac felly rydym yn
Mae angen i gyfnewid nhw ac ychwanegu 1 i'r cownter cyfnewid.
Ac yn awr rydym wedi symud 5, yr elfen fwyaf nesaf,
hyd at ddiwedd y gyfran heb eu didoli.
Felly, gallwn yn awr yn galw hynny rhan o'r gyfran didoli.
>> Nawr eich bod yn edrych ar y sgrin ac yn ôl pob tebyg yn gallu dweud,
ag y gallaf, fod yr amrywiaeth yn cael ei datrys ar hyn o bryd.
Ond ni allwn brofi hynny eto.
Nid oes gennym warant ei fod yn datrys.
Ond dyma lle mae'r cyfnewid cownter yn mynd i ddod i chwarae.
>> Felly rydym wedi cwblhau tocyn.
Mae'r cownter cyfnewid yw 2.
Felly rydym yn mynd i ailadrodd y broses hon eto,
ailadrodd nes bod y cownter cyfnewid yw 0.
Ailosod y cownter cyfnewid i 0.
Felly byddwn yn ei ailosod.
>> Nawr edrychwch ar bob pâr cyfagos.
Dyna mewn trefn, 1 a 2.
2 a 3 yn eu trefn.
3 a 4 mewn trefn.
Felly, yn y fan hon, yn sylwi ein bod wedi cwblhau edrych ar bob pâr cyfagos,
ond y cownter cyfnewid yn dal i fod 0.
>> Os nad oes gennym i newid unrhyw elfennau, yna maent
rhaid iddo fod mewn trefn, gan yn rhinwedd y broses hon.
Ac felly effeithlonrwydd o ryw fath, y mae gwyddonwyr yr ydym cyfrifiadur caru,
yn y gallwn ddatgan yn awr rhaid i'r amrywiaeth cyfan
eu didoli, oherwydd nid ydym yn gwneud rhaid i gyfnewid unrhyw elfennau.
Dyna 'n bert' n glws.
>> Felly beth yw'r achos gwaethaf senario gyda'r math swigen?
Yn yr achos gwaethaf yr amrywiaeth yn er mwyn gwbl cefn,
ac felly mae'n rhaid i bob swigen o'r elfennau mawr i gyd
y ffordd ar draws y rhesi.
Ac mae gennym hefyd effeithiol i swigen holl elfennau bach yn ôl
yr holl ffordd ar draws yr amrywiaeth, hefyd.
Felly, mae pob un o'r elfennau n yn gorfod symud ar draws pob un o'r elfennau n arall.
Felly dyna y senario achos gwaethaf.
Yn yr achos gorau senario fodd bynnag, mae hyn yn
ychydig yn wahanol fath dethol.
Mae'r amrywiaeth yn barod datrys pan fyddwn yn mynd i mewn.
Nid oes rhaid i ni wneud unrhyw cyfnewidiadau ar y tocyn cyntaf.
Felly gallai fod yn rhaid inni edrych yn llai o elfennau, dde?
Nid oes rhaid i ni ailadrodd hyn prosesu sawl gwaith drosodd.
>> Felly beth mae hynny'n ei olygu?
Felly beth yw'r sefyllfa waethaf ar gyfer y math swigod, a beth sy'n
y senario achos gorau ar gyfer y math swigen?
A wnaethoch chi ddyfalu hyn?
Yn yr achos gwaethaf yn rhaid i chi ailadrodd ar draws yr holl elfennau n amserau n.
Felly yr achos gwaethaf ei sgwâr n.
>> Os yw'r amrywiaeth yn berffaith ddidoli fodd bynnag, dim ond
rhaid i ni edrych ar bob o'r elfennau unwaith.
Ac os y cownter cyfnewid yn dal i fod 0, gallwch ddweud amrywiaeth hwn yn cael ei datrys.
Ac felly yn yr achos gorau, mae hyn yn mewn gwirionedd yn well na ddethol
sort-- mae'n omega o n.
>> Rwy'n Doug Lloyd.
Mae hyn yn CS50.