[Powered by Google Translate] [BUBBLE Ordena]
[JACKSON STEINKAMP Harvardeko Unibertsitateko]
[HAU CS50 DA. CS50TV]
Bubble Ordena ordenatzeko algoritmo baten adibide bat da
hau da, elementu multzo bat ordenatzeko prozedura
goranzko edo beheranzko ordenan.
Esate baterako, nahi duzun array bat ordenatzeko zenbakiak osatutako
[3, 5, 2, 9], Bubble Ordena inplementazio zuzena itzuliko litzateke
ordenatuko array [2, 3, 5, 9] ordena gorakorrean.
Orain, pseudocode algoritmoa nola funtzionatzen duen azaldu noa.
>> Demagun 5 osoko zenbakien zerrenda ari gara ordenatzeko - 3, 2, 9, 6, eta 5.
Algoritmoa lehen bi elementu, 3 eta 2 begira hasten da,
Oraindik dute eta ordena elkarren artean erlatiboa egiaztapena.
Dira - 3 2 baino handiagoa.
Goranzko ordena izango da, beste modu inguruan izan behar dute.
Beraz, trukatu dugu.
[2, 3, 9, 6, 5]: orain, zerrenda honen itxura.
>> Ondoren, begiratu dugu elementu bigarren eta hirugarren, 3 eta 9.
Oraindik beste bakoitzean erlatiboa ordena zuzena dute.
Hau da, 3 9 baino gutxiago, beraz algoritmoa ez swap horiek.
Ondoren, 9 eta 6. Oraindik dute ordena.
>> Beraz, swap 9 6 baino handiagoa delako behar dugu.
Azkenik, begiratzen dugu azken bi zenbaki osoko, 9 eta 5.
Oraindik dute ordena, beraz, truka behar da.
Zerrendan zehar lehen pass osoa ondoren,
itxura hau atsegin du: [2, 3, 6, 5, 9].
Ez dago gaizki. Ia ordenatuko.
Baina zerrenda bidez exekutatu berriro ordenatuko guztiz lortzeko behar dugu.
Bi 3 baino txikiagoa da, beraz, ez ditugu trukatzeko.
>> Hiru 6 baino gutxiago, beraz, ez ditugu trukatzeko.
Sei 5 baino handiagoa da. Dugu trukatuko.
Sei 9 baino gutxiago. Ez dugu trukatu.
Bigarren mendatea eta gero, itxura hau atsegin du: [2, 3, 5, 6, 9]. Perfect.
Orain, idazteko pseudocode en.
Funtsean, zerrendako elementu bakoitza, begiratu behar dugu
eta zuzenean haren eskuinaldean elementu.
Dira bada beste bakoitzean erlatiboa, hau da, ezker aldean elementu bada
eskubidea baino handiagoa da, bi elementu swap behar dugu.
>> Horretarako dugu zerrendan elementu guztietan, eta bat egin dugu pass bidez.
Orain pass-bidez behar adina aldiz egin besterik ez dugu zerrenda bermatzeko
guztiz, behar bezala ordenatuko da.
Baina zenbat aldiz ez zerrenda pasatzen dugu
bermatzen dugu Bukatutakoan?
Beno, kasurik txarrenean ditugu erabat atzera zerrendan.
Ondoren, gainditu-throughs kopurua kopurua berdina hartzen du
elementu n-1.
Honek ez badu zentzurik intuizioz, kasu sinple bat uste zerrenda [2, 1].
>> Pass bat-hartu behar bezala ordenatzeko.
[3, 2, 1] - txarrena kasua da, 3 elementu hauek ordenatuko atzeraka,
2 iterazio sort eraman dute.
Iterazio ondoren, [2, 1, 3] da.
Bigarren errendimendu ordenatzen array [1, 2, 3].
Array bidez inoiz ez duzu, oro har, badakizu,
n-1 aldiz, non n array elementu kopurua baino gehiago.
Deitzen Bubble Sort handiena elementu 'burbuila-up' ohi delako
eskubidea nahiko azkar.
Izan ere, algoritmo hau oso interesgarria portaera du.
>> Array bitartez osoa m iterazio ondoren,
eskuinekoa m elementu bermatuta
leku zuzena izan behar ordenatuko da.
Nahi duzun hau ikusteko zeure burua bada,
dastatu ahal izango dugu zerrenda bat erabat atzeraka [9, 6, 5, 3, 2].
Zerrenda osoa bitartez pass bat egin ondoren,
[Idatziz soinua]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
eskuinekoa elementu 9 bere leku egokia da.
Bigarren pass-bidez ondoren, 6 izango ditu 'bubbled-up'
leku bigarren eskuinekoa.
6 eta 9 - eskuineko bi elementu bere leku zuzena
lehen bi pass-throughs ondoren.
>> Beraz, nola egin dezaket hau erabili dugu algoritmoa optimizatzeko?
Beno, array bidez iterazio ondoren
Egia esan, ez dugu eskuineko elementu egiaztatu beharko
ezagutzen dugulako ordenatuko da.
Bi iterazio ondoren, ziur eskuinekoa bi elementu dira ezagutzen dugu.
Beraz, oro har,, k osoa array bidez iterazio ondoren,
k azken elementu egiaztapena erredundante ezagutzen da geroztik dugu
Oraindik kokaleku zuzena dute dagoeneko.
>> Beraz, bada, n elementu multzo bat ari zaren ordenatzeko,
lehen iterazio - you'll elementu guztiak ordenatzeko lehen n-0.
Bigarren iterazio On, elementu guztiak, baina azken begiratu duzu
lehen n-1.
Optimizazioa Another zerrenda ordenatuko dagoeneko egiaztatu ahal
iterazio bakoitzaren ondoren.
Badago ordenatuta, ez dugu gehiago iterazioak egin behar
zerrendan zehar.
Nola egin dezakegu hori?
Beno, egin ez badugu trukeak edozein zerrendaren pass-bidez,
argia da zerrenda dagoeneko horrela antolatu genuen trukatzeko ezer ez delako.
Beraz, behin betiko, ez dugu berriro ordenatzeko.
>> Agian izeneko 'ez da horrela antolatu' Ez aldagai bat hasieratzean ahal izango duzu
ezezkoan eta aldatzeko benetako elementuak edozein swap nahi izanez gero
array bidez iterazio.
Edo, era berean, zenbat trukeak egiten duzun counter bat zenbatzen
edozein iterazio.
Iterazio baten amaieran, ez baduzu swap edozein elementu,
Zerrenda dagoeneko horrela antolatu, eta Bukatutakoan badakizu.
Bubble Sort, Ordenatzeko beste algoritmoak bezala, izan daiteke
tweaked ordena metodo bat duen edozein elementu.
>> Hau da, bi elementu modu bat esan behar duzu lehenengo bada
handiagoa, baino berdina edo segundo baino gutxiago.
Esate baterako, alfabetoaren letra ordenatzeko diozu
<b, b <c, etab
Edo asteko egun ordenatzeko non igandea astelehena baino gutxiago
asteartea baino gutxiago esan nahi du horrek.
>> Bubble Ordena ez da oso eraginkorrak edo azkar ordenatzea algoritmoa esan nahi du.
Bere kasurik txarrenaren exekuzio Big n O ²
n iterazioak egin zerrenda baten bidez delako
bakoitzean pass-bidez egiaztatuko n elementu guztiak, nxn = n ².
Exekutatu denbora Horrek esan nahi du elementu kopurua handitzen ari zaren ordenatzeko,
exekuzio-denbora handitzen du quadratically.
>> Baina eraginkortasuna ez da zure programa kezka nagusia
ari zaren edo elementu kopuru txiki bat besterik ez bada ordenatzeko,
Bubble Ordena erabilgarria duelako
ordenatzeko errazena algoritmo bat da ulertzeko
eta kodea.
Teoriko bat itzultzen esperientzia lortzeko modu handi bat da
benetako funtzionamendua kodea sartu algoritmoa.
Beno, hori Bubble Ordena zuretzat. Eskerrik asko ikusteko.
CS50.TV