1 00:00:00,500 --> 00:00:02,840 [Powered by Google Translate] [BUBBLE Ordena] 2 00:00:02,840 --> 00:00:04,560 [JACKSON STEINKAMP Harvardeko Unibertsitateko] 3 00:00:04,560 --> 00:00:07,500 [HAU CS50 DA. CS50TV] 4 00:00:08,000 --> 00:00:11,730 Bubble Ordena ordenatzeko algoritmo baten adibide bat da 5 00:00:11,730 --> 00:00:14,460 hau da, elementu multzo bat ordenatzeko prozedura 6 00:00:14,460 --> 00:00:15,840 goranzko edo beheranzko ordenan. 7 00:00:15,840 --> 00:00:18,710 Esate baterako, nahi duzun array bat ordenatzeko zenbakiak osatutako 8 00:00:18,710 --> 00:00:23,060 [3, 5, 2, 9], Bubble Ordena inplementazio zuzena itzuliko litzateke 9 00:00:23,060 --> 00:00:26,260 ordenatuko array [2, 3, 5, 9] ordena gorakorrean. 10 00:00:26,260 --> 00:00:28,850 Orain, pseudocode algoritmoa nola funtzionatzen duen azaldu noa. 11 00:00:28,850 --> 00:00:34,000 >> Demagun 5 osoko zenbakien zerrenda ari gara ordenatzeko - 3, 2, 9, 6, eta 5. 12 00:00:34,000 --> 00:00:37,650 Algoritmoa lehen bi elementu, 3 eta 2 begira hasten da, 13 00:00:37,650 --> 00:00:40,850 Oraindik dute eta ordena elkarren artean erlatiboa egiaztapena. 14 00:00:40,850 --> 00:00:43,150 Dira - 3 2 baino handiagoa. 15 00:00:43,150 --> 00:00:45,190 Goranzko ordena izango da, beste modu inguruan izan behar dute. 16 00:00:45,190 --> 00:00:46,610 Beraz, trukatu dugu. 17 00:00:46,610 --> 00:00:49,760 [2, 3, 9, 6, 5]: orain, zerrenda honen itxura. 18 00:00:49,760 --> 00:00:52,450 >> Ondoren, begiratu dugu elementu bigarren eta hirugarren, 3 eta 9. 19 00:00:52,450 --> 00:00:55,770 Oraindik beste bakoitzean erlatiboa ordena zuzena dute. 20 00:00:55,770 --> 00:00:58,800 Hau da, 3 9 baino gutxiago, beraz algoritmoa ez swap horiek. 21 00:00:58,800 --> 00:01:01,900 Ondoren, 9 eta 6. Oraindik dute ordena. 22 00:01:01,900 --> 00:01:04,260 >> Beraz, swap 9 6 baino handiagoa delako behar dugu. 23 00:01:04,260 --> 00:01:08,840 Azkenik, begiratzen dugu azken bi zenbaki osoko, 9 eta 5. 24 00:01:08,840 --> 00:01:10,850 Oraindik dute ordena, beraz, truka behar da. 25 00:01:10,850 --> 00:01:13,360 Zerrendan zehar lehen pass osoa ondoren, 26 00:01:13,360 --> 00:01:17,140 itxura hau atsegin du: [2, 3, 6, 5, 9]. 27 00:01:17,140 --> 00:01:19,690 Ez dago gaizki. Ia ordenatuko. 28 00:01:19,690 --> 00:01:22,450 Baina zerrenda bidez exekutatu berriro ordenatuko guztiz lortzeko behar dugu. 29 00:01:22,450 --> 00:01:29,250 Bi 3 baino txikiagoa da, beraz, ez ditugu trukatzeko. 30 00:01:29,250 --> 00:01:31,700 >> Hiru 6 baino gutxiago, beraz, ez ditugu trukatzeko. 31 00:01:31,700 --> 00:01:35,500 Sei 5 baino handiagoa da. Dugu trukatuko. 32 00:01:35,500 --> 00:01:38,460 Sei 9 baino gutxiago. Ez dugu trukatu. 33 00:01:38,460 --> 00:01:42,170 Bigarren mendatea eta gero, itxura hau atsegin du: [2, 3, 5, 6, 9]. Perfect. 34 00:01:42,170 --> 00:01:44,680 Orain, idazteko pseudocode en. 35 00:01:44,680 --> 00:01:48,450 Funtsean, zerrendako elementu bakoitza, begiratu behar dugu 36 00:01:48,450 --> 00:01:50,060 eta zuzenean haren eskuinaldean elementu. 37 00:01:50,060 --> 00:01:53,420 Dira bada beste bakoitzean erlatiboa, hau da, ezker aldean elementu bada 38 00:01:53,420 --> 00:01:56,810 eskubidea baino handiagoa da, bi elementu swap behar dugu. 39 00:01:56,810 --> 00:02:01,270 >> Horretarako dugu zerrendan elementu guztietan, eta bat egin dugu pass bidez. 40 00:02:01,270 --> 00:02:05,160 Orain pass-bidez behar adina aldiz egin besterik ez dugu zerrenda bermatzeko 41 00:02:05,160 --> 00:02:06,480 guztiz, behar bezala ordenatuko da. 42 00:02:06,480 --> 00:02:08,889 Baina zenbat aldiz ez zerrenda pasatzen dugu 43 00:02:08,889 --> 00:02:10,400 bermatzen dugu Bukatutakoan? 44 00:02:10,400 --> 00:02:14,730 Beno, kasurik txarrenean ditugu erabat atzera zerrendan. 45 00:02:14,730 --> 00:02:17,840 Ondoren, gainditu-throughs kopurua kopurua berdina hartzen du 46 00:02:17,840 --> 00:02:19,730 elementu n-1. 47 00:02:19,730 --> 00:02:24,720 Honek ez badu zentzurik intuizioz, kasu sinple bat uste zerrenda [2, 1]. 48 00:02:24,720 --> 00:02:28,430 >> Pass bat-hartu behar bezala ordenatzeko. 49 00:02:28,430 --> 00:02:33,060 [3, 2, 1] - txarrena kasua da, 3 elementu hauek ordenatuko atzeraka, 50 00:02:33,060 --> 00:02:34,830 2 iterazio sort eraman dute. 51 00:02:34,830 --> 00:02:37,980 Iterazio ondoren, [2, 1, 3] da. 52 00:02:37,980 --> 00:02:39,550 Bigarren errendimendu ordenatzen array [1, 2, 3]. 53 00:02:39,550 --> 00:02:43,350 Array bidez inoiz ez duzu, oro har, badakizu, 54 00:02:43,350 --> 00:02:46,790 n-1 aldiz, non n array elementu kopurua baino gehiago. 55 00:02:47,090 --> 00:02:50,470 Deitzen Bubble Sort handiena elementu 'burbuila-up' ohi delako 56 00:02:50,470 --> 00:02:51,950 eskubidea nahiko azkar. 57 00:02:51,950 --> 00:02:53,980 Izan ere, algoritmo hau oso interesgarria portaera du. 58 00:02:53,980 --> 00:02:57,410 >> Array bitartez osoa m iterazio ondoren, 59 00:02:57,410 --> 00:02:59,000 eskuinekoa m elementu bermatuta 60 00:02:59,000 --> 00:03:01,000 leku zuzena izan behar ordenatuko da. 61 00:03:01,000 --> 00:03:02,280 Nahi duzun hau ikusteko zeure burua bada, 62 00:03:02,280 --> 00:03:05,500 dastatu ahal izango dugu zerrenda bat erabat atzeraka [9, 6, 5, 3, 2]. 63 00:03:05,500 --> 00:03:08,220 Zerrenda osoa bitartez pass bat egin ondoren, 64 00:03:08,220 --> 00:03:09,220 [Idatziz soinua] 65 00:03:09,220 --> 00:03:18,790 [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] 66 00:03:18,790 --> 00:03:21,250 eskuinekoa elementu 9 bere leku egokia da. 67 00:03:21,250 --> 00:03:24,760 Bigarren pass-bidez ondoren, 6 izango ditu 'bubbled-up' 68 00:03:24,760 --> 00:03:26,220 leku bigarren eskuinekoa. 69 00:03:26,220 --> 00:03:28,840 6 eta 9 - eskuineko bi elementu bere leku zuzena 70 00:03:28,840 --> 00:03:30,580 lehen bi pass-throughs ondoren. 71 00:03:30,580 --> 00:03:32,590 >> Beraz, nola egin dezaket hau erabili dugu algoritmoa optimizatzeko? 72 00:03:32,590 --> 00:03:34,850 Beno, array bidez iterazio ondoren 73 00:03:34,850 --> 00:03:37,690 Egia esan, ez dugu eskuineko elementu egiaztatu beharko 74 00:03:37,690 --> 00:03:39,200 ezagutzen dugulako ordenatuko da. 75 00:03:39,200 --> 00:03:43,050 Bi iterazio ondoren, ziur eskuinekoa bi elementu dira ezagutzen dugu. 76 00:03:43,050 --> 00:03:48,260 Beraz, oro har,, k osoa array bidez iterazio ondoren, 77 00:03:48,260 --> 00:03:51,550 k azken elementu egiaztapena erredundante ezagutzen da geroztik dugu 78 00:03:51,550 --> 00:03:52,360 Oraindik kokaleku zuzena dute dagoeneko. 79 00:03:52,360 --> 00:03:54,870 >> Beraz, bada, n elementu multzo bat ari zaren ordenatzeko, 80 00:03:54,870 --> 00:03:57,870 lehen iterazio - you'll elementu guztiak ordenatzeko lehen n-0. 81 00:03:57,870 --> 00:04:04,170 Bigarren iterazio On, elementu guztiak, baina azken begiratu duzu 82 00:04:04,170 --> 00:04:07,090 lehen n-1. 83 00:04:07,090 --> 00:04:10,520 Optimizazioa Another zerrenda ordenatuko dagoeneko egiaztatu ahal 84 00:04:10,520 --> 00:04:11,710 iterazio bakoitzaren ondoren. 85 00:04:11,710 --> 00:04:13,900 Badago ordenatuta, ez dugu gehiago iterazioak egin behar 86 00:04:13,900 --> 00:04:15,310 zerrendan zehar. 87 00:04:15,310 --> 00:04:16,220 Nola egin dezakegu hori? 88 00:04:16,220 --> 00:04:19,360 Beno, egin ez badugu trukeak edozein zerrendaren pass-bidez, 89 00:04:19,360 --> 00:04:22,350 argia da zerrenda dagoeneko horrela antolatu genuen trukatzeko ezer ez delako. 90 00:04:22,350 --> 00:04:24,160 Beraz, behin betiko, ez dugu berriro ordenatzeko. 91 00:04:24,160 --> 00:04:27,960 >> Agian izeneko 'ez da horrela antolatu' Ez aldagai bat hasieratzean ahal izango duzu 92 00:04:27,960 --> 00:04:30,990 ezezkoan eta aldatzeko benetako elementuak edozein swap nahi izanez gero 93 00:04:30,990 --> 00:04:32,290 array bidez iterazio. 94 00:04:32,290 --> 00:04:35,350 Edo, era berean, zenbat trukeak egiten duzun counter bat zenbatzen 95 00:04:35,350 --> 00:04:37,040 edozein iterazio. 96 00:04:37,040 --> 00:04:40,040 Iterazio baten amaieran, ez baduzu swap edozein elementu, 97 00:04:40,040 --> 00:04:41,780 Zerrenda dagoeneko horrela antolatu, eta Bukatutakoan badakizu. 98 00:04:41,780 --> 00:04:44,090 Bubble Sort, Ordenatzeko beste algoritmoak bezala, izan daiteke 99 00:04:44,090 --> 00:04:46,960 tweaked ordena metodo bat duen edozein elementu. 100 00:04:46,960 --> 00:04:50,610 >> Hau da, bi elementu modu bat esan behar duzu lehenengo bada 101 00:04:50,610 --> 00:04:53,770 handiagoa, baino berdina edo segundo baino gutxiago. 102 00:04:53,770 --> 00:04:56,870 Esate baterako, alfabetoaren letra ordenatzeko diozu 103 00:04:56,870 --> 00:05:00,520 00:05:03,830 Edo asteko egun ordenatzeko non igandea astelehena baino gutxiago 105 00:05:03,830 --> 00:05:05,110 asteartea baino gutxiago esan nahi du horrek. 106 00:05:05,110 --> 00:05:09,630 >> Bubble Ordena ez da oso eraginkorrak edo azkar ordenatzea algoritmoa esan nahi du. 107 00:05:09,630 --> 00:05:12,370 Bere kasurik txarrenaren exekuzio Big n O ² 108 00:05:12,370 --> 00:05:14,810 n iterazioak egin zerrenda baten bidez delako 109 00:05:14,810 --> 00:05:18,430 bakoitzean pass-bidez egiaztatuko n elementu guztiak, nxn = n ². 110 00:05:18,430 --> 00:05:22,730 Exekutatu denbora Horrek esan nahi du elementu kopurua handitzen ari zaren ordenatzeko, 111 00:05:22,730 --> 00:05:24,330 exekuzio-denbora handitzen du quadratically. 112 00:05:24,330 --> 00:05:27,330 >> Baina eraginkortasuna ez da zure programa kezka nagusia 113 00:05:27,330 --> 00:05:29,550 ari zaren edo elementu kopuru txiki bat besterik ez bada ordenatzeko, 114 00:05:29,550 --> 00:05:31,660 Bubble Ordena erabilgarria duelako 115 00:05:31,660 --> 00:05:33,360 ordenatzeko errazena algoritmo bat da ulertzeko 116 00:05:33,360 --> 00:05:34,250 eta kodea. 117 00:05:34,250 --> 00:05:37,270 Teoriko bat itzultzen esperientzia lortzeko modu handi bat da 118 00:05:37,270 --> 00:05:40,220 benetako funtzionamendua kodea sartu algoritmoa. 119 00:05:40,220 --> 00:05:43,000 Beno, hori Bubble Ordena zuretzat. Eskerrik asko ikusteko. 120 00:05:43,000 --> 00:05:44,000 CS50.TV