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