[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