[Powered by Google Translate] [SORT swigen]
[JACKSON STEINKAMP HARVARD UNIVERSITY]
[HWN YW CS50. CS50TV]
Trefnu yn Bubble yn enghraifft o algorithm didoli -
hynny yw, gweithdrefn ar gyfer didoli set o elfennau mewn
trefn esgynnol neu ddisgynnol.
Er enghraifft, os ydych am roi trefn ar amrywiaeth sy'n cynnwys y rhifau
[3, 5, 2, 9], byddai gweithredu cywir Trefnu yn Bubble dychwelyd y
amrywiaeth didoli [2, 3, 5, 9] yn nhrefn esgynnol.
Nawr, dw i'n mynd i egluro mewn pseudocode sut y mae'r algorithm yn gweithio.
>> Lets 'ddeud ein bod yn didoli rhestr o 5 cyfanrifau - 3, 2, 9, 6, a 5.
Mae'r algorithm yn dechrau drwy edrych ar y ddwy elfen gyntaf, 3 a 2,
a gwirio os ydynt yn allan o drefn mewn perthynas â'i gilydd.
Maent yn - 3 yn fwy na 2.
I fod er mwyn esgynnol, dylent fod yn ffordd arall o gwmpas.
Felly, rydym yn eu cyfnewid.
Nawr bod y rhestr yn edrych fel hyn: [2, 3, 9, 6, 5].
>> Nesaf, byddwn yn edrych ar yr elfennau ail a'r drydedd, 3 a 9.
Maen nhw yn y drefn gywir mewn perthynas â'i gilydd.
Hynny yw, 3 yn llai na 9 fel nad yw'r algorithm yn eu cyfnewid.
Nesaf, byddwn yn edrych ar 9 a 6. Maen nhw'n allan o drefn.
>> Felly, mae angen i ni eu cyfnewid am 9 yn fwy na 6.
Yn olaf, rydym yn edrych ar y ddau olaf cyfanrifau, 9 a 5.
Maen nhw'n allan o drefn, felly mae'n rhaid iddynt gael eu cyfnewid.
Ar ôl y tocyn cyflawn cyntaf drwy'r rhestr,
mae'n edrych fel hyn: [2, 3, 6, 5, 9].
Ddim yn ddrwg. Mae'n datrys bron.
Ond mae angen i redeg drwy'r rhestr eto i gael ei datrys yn llwyr.
Dau yn llai na 3, felly nid ydym yn eu cyfnewid.
>> Tri yn llai na 6, felly nid ydym yn eu cyfnewid.
Chwech yn fwy na 5. Rydym yn cyfnewid.
Chwech yn llai na 9. Nid ydym yn cyfnewid.
Ar ôl yr Ail drwy basio, mae'n edrych fel hyn: [2, 3, 5, 6, 9]. Perfect.
Nawr, gadewch i ni ysgrifennu yn pseudocode.
Yn y bôn, ar gyfer pob elfen yn y rhestr, mae angen i ni edrych arno
a'r elfen uniongyrchol i'w dde.
Os ydynt yn allan o drefn mewn perthynas â'i gilydd - hynny yw, os yw'r elfen ar y chwith
yn fwy na'r un ar y dde - dylem gyfnewid y ddwy elfen.
>> Rydym yn gwneud hyn ar gyfer pob elfen o'r rhestr, ac rydym wedi gwneud un pasio drwodd.
Nawr rydym yn unig rhaid i ni wneud yr amseroedd pasio drwy ddigon i sicrhau bod y rhestr
yn llawn, didoli yn gywir.
Ond faint o weithiau rhaid i ni fynd trwy'r rhestr i
gwarantu ein bod yn ei wneud?
Wel, y senario gwaethaf-achos os oes gennym restr cwbl yn ôl.
Yna mae'n cymryd nifer o basio-throughs hafal i'r nifer
o elfennau n-1.
Os nad yw hyn yn gwneud synnwyr yn reddfol, meddyliwch am achos syml - mae'r rhestr [2, 1].
>> Mae hyn yn mynd i gymryd un pasio trwodd i ddidoli yn gywir.
[3, 2, 1] - Yr achos gwaethaf yw bod â 3 elfen didoli yn ôl,
mae'n mynd i fynd â 2 iteriadau i ddidoli.
Ar ôl un fersiwn, mae'n [2, 1, 3].
Mae'r cynnyrch ail casgliad didoli [1, 2, 3].
Felly, rydych yn gwybod eich bod byth yn rhaid i chi fynd trwy'r casgliad, yn gyffredinol,
mwy na n-1 gwaith, lle mae n yn nifer o elfennau yn y rhesi.
Mae'n cael ei alw Trefnu yn Bubble oherwydd bod yr elfennau mwyaf yn tueddu i 'swigen-up'
i'r dde yn weddol gyflym.
Mewn gwirionedd, mae hyn yn algorithm wedi ymddwyn yn ddiddorol iawn.
>> Ar ôl fersiynau m trwy'r amrywiaeth gyfan,
yr elfennau m rightmost yn cael eu gwarantu
i gael eu didoli yn eu lle cywir.
Os ydych chi eisiau gweld hyn drosoch eich hun,
gallwn geisio ar restr gwbl yn ôl [9, 6, 5, 3, 2].
Ar ôl un llwyddiant drwy'r rhestr gyfan,
[Gadarn o ysgrifennu]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
yr elfen rightmost 9 yw yn ei le priodol.
Ar ôl yr ail pasio drwy, bydd y 6 wedi 'bubbled-fyny' i'r
yn ail rightmost.
Mae'r ddwy elfen ar y dde - 6 a 9 - bydd yn eu llefydd cywir
ar ôl y ddau gyntaf pasio-throughs.
>> Felly, sut gallwn ddefnyddio hyn i wneud y gorau o algorithm?
Wel, ar ôl un fersiwn trwy'r amrywiaeth
dydyn ni ddim yn angen i chi wirio'r elfen rightmost
oherwydd rydym yn gwybod ei fod yn datrys.
Ar ôl ddau gylch, rydym yn gwybod yn sicr y ddwy rightmost elfennau yn eu lle.
Felly, yn gyffredinol, ar ôl fersiynau k drwy'r amrywiaeth lawn,
gwirio elfennau k olaf yn ddiangen gan ein bod yn gwybod
eu bod yn y lleoliad cywir yn barod.
>> Felly, os ydych yn didoli amrywiaeth o elfennau n,
ar y fersiwn cyntaf - you'll rhaid i ni drefnu pob un o'r elfennau - y cyntaf n-0.
Ar yr ail ailadroddiad, bydd rhaid i chi edrych ar yr holl elfennau, ond yr olaf -
y cyntaf n-1.
Arall efallai optimization fydd gwneud yn siwr os bydd y rhestr yn cael ei datrys eisoes
ar ôl pob iteriad.
Os yw'n datrys eisoes, nid oes angen i ni wneud mwy o iteriadau
drwy'r rhestr.
Sut allwn ni wneud hyn?
Wel, os nad ydym yn gwneud unrhyw cyfnewid ar sail pasio trwodd y rhestr,
mae'n amlwg bod y rhestr yn cael ei datrys eisoes oherwydd nad oeddem yn cyfnewid unrhyw beth.
Felly, rydym yn bendant yn rhaid i ddatrys eto.
>> Efallai y gallech ymgychwyn newidyn baner o'r enw 'ddim yn datrys' i
anwir a chyfnewid 'i at wir os oes rhaid i gyfnewid unrhyw elfennau ar
1 ailadrodd drwy'r casgliad.
Neu yn yr un modd, gwnewch yn groes i gyfrif faint o gyfnewid rydych yn gwneud
ar unrhyw fersiwn a roddwyd.
Ar ddiwedd iteriad, os nad ydych wedi cyfnewid unrhyw un o'r elfennau,
eich bod yn gwybod y rhestr yn cael ei datrys eisoes ac rydych chi wedi gorffen.
Trefnu yn Bubble, fel algorithmau didoli eraill, fod yn
tweaked i weithio i unrhyw elfennau sy'n cael dull archebu.
>> Hynny yw, o ystyried dwy elfen gennych ffordd i ddweud os yw'r un cyntaf
yn fwy na, hafal i neu'n llai na'r ail.
Er enghraifft, gallech roi trefn ar lythrennau'r wyddor drwy ddweud
bod a <b, b <c, ac ati
Neu gallech roi trefn ar ddiwrnod o'r wythnos lle mae Sul yn llai na Dydd Llun
sy'n llai na dydd Mawrth.
>> Trefnu yn Bubble nid yw algorithm didoli effeithlon iawn neu gyflym.
Mae ei gwaethaf runtime yn Big O o n ²
oherwydd bod yn rhaid i chi wneud iteriadau n trwy restr
gwirio holl elfennau n bob pasio drwy, nxn = n ².
Y tro hwn ei redeg yn golygu fod y nifer o elfennau ydych yn didoli yn cynyddu,
yr amser yn rhedeg yn cynyddu quadratically.
>> Ond os nad yw effeithlonrwydd yn bryder mawr o'ch rhaglen
neu os ydych ond yn didoli nifer fach o elfennau,
efallai y byddwch yn dod o hyd i Trefnu yn Bubble ddefnyddiol oherwydd
mae'n un o'r algorithmau symlaf didoli i ddeall
ac i cod.
Mae hefyd yn ffordd wych o gael profiad gyda gyfieithu a damcaniaethol
algorithm i mewn i god gweithredu gwirioneddol.
Wel, dyna Trefnu yn Bubble i chi. Diolch am wylio.
CS50.TV