1 00:00:00,000 --> 00:00:03,360 >> [MUSIC nagpe-play] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Lahat ng mga karapatan, kaya bubble sort ay isang algorithm 4 00:00:06,730 --> 00:00:08,730 maaari mong gamitin upang ayusin ang isang hanay ng mga elemento. 5 00:00:08,730 --> 00:00:10,850 Tingnan natin ang isang pagtingin sa kung paano ito gumagana. 6 00:00:10,850 --> 00:00:13,240 >> Kaya ang pangunahing ideya sa likod bubble sort ay na ito. 7 00:00:13,240 --> 00:00:17,340 Karaniwan naming nais na ilipat ang mas mataas minamahal na mga elemento sa pangkalahatan sa kanan, 8 00:00:17,340 --> 00:00:20,340 at mas mababa ang mga mahal na mga elemento sa pangkalahatan sa kaliwa, tulad ng gagawin namin inaasahan. 9 00:00:20,340 --> 00:00:23,256 Gusto naming ang mas mababang mga bagay-bagay na sa sa simula, at ang mas mataas na mga bagay-bagay 10 00:00:23,256 --> 00:00:24,970 na sa dulo. 11 00:00:24,970 --> 00:00:26,130 >> Paano namin gawin ito? 12 00:00:26,130 --> 00:00:28,040 Well sa pseudocode code, maaari naming sabihin, sabihin 13 00:00:28,040 --> 00:00:30,320 magtakda ng isang swap counter sa isang non-zero na halaga. 14 00:00:30,320 --> 00:00:32,570 Susubukan naming makita kung bakit ginagawa namin na sa isang segundo. 15 00:00:32,570 --> 00:00:36,090 At pagkatapos ay ulitin namin ang mga sumusunod na proseso hanggang sa swap counter ay 0, 16 00:00:36,090 --> 00:00:39,910 o hanggang hindi kami gumagawa nang swaps sa lahat. 17 00:00:39,910 --> 00:00:43,170 >> I-reset ang magpalitan ng kontra sa 0 kung wala pa ito 0. 18 00:00:43,170 --> 00:00:46,420 Pagkatapos ay tumingin sa bawat katabi pares ng mga elemento. 19 00:00:46,420 --> 00:00:49,550 Kung ang mga dalawang mga elemento ay wala sa pagkakasunod-sunod, magpalitan ng mga ito, 20 00:00:49,550 --> 00:00:51,620 at magdagdag ng 1 sa swap counter. 21 00:00:51,620 --> 00:00:53,870 Kung pinag-iisipan mo tungkol sa ito bago mo maisalarawan ito, 22 00:00:53,870 --> 00:00:57,471 mapapansin na ito ay malilipat sa mas mababang minamahal na mga elemento sa kaliwa 23 00:00:57,471 --> 00:01:00,720 at mas mataas na pinahahalagahan elemento sa kanan, epektibong paggawa ng kung ano ang gusto naming gawin, 24 00:01:00,720 --> 00:01:03,940 na kung saan ay ilipat ang mga grupo ng mga elemento sa paraang iyon. 25 00:01:03,940 --> 00:01:07,035 Ni mailarawan kung paano ito Hayaan maaaring tumingin sa paggamit ng aming array 26 00:01:07,035 --> 00:01:10,504 na ginamit namin upang subukan ang out ang mga algorithm. 27 00:01:10,504 --> 00:01:13,420 Kami ay may isang unsorted array dito muli, ipinapahiwatig ng lahat ng mga elemento 28 00:01:13,420 --> 00:01:14,840 pagiging sa pula. 29 00:01:14,840 --> 00:01:17,970 At inilagay ko ang aking swap counter sa isang nonzero halaga. 30 00:01:17,970 --> 00:01:20,610 Nagkataon pinili ko negatibong 1-- ito ay hindi 0. 31 00:01:20,610 --> 00:01:23,840 Gusto naming ulitin ang prosesong ito hanggang sa swap counter ay 0. 32 00:01:23,840 --> 00:01:26,540 Ito ang dahilan kung bakit ko itatakda ang aking swap kontra sa ilang mga di-zero na halaga, 33 00:01:26,540 --> 00:01:29,400 dahil kung hindi, ang swap counter ay 0. 34 00:01:29,400 --> 00:01:31,610 Hindi namin ay magsisimula sa proseso ng algorithm. 35 00:01:31,610 --> 00:01:33,610 Kaya muli, ang mga hakbang are-- i-reset ang swap counter 36 00:01:33,610 --> 00:01:37,900 sa 0, pagkatapos ay tumingin sa bawat kalapit pares, at kung ang mga ito sa labas ng order, 37 00:01:37,900 --> 00:01:40,514 magpalitan ng mga ito, at magdagdag ng 1 sa swap counter. 38 00:01:40,514 --> 00:01:41,680 Kaya simulan ni prosesong ito hayaan. 39 00:01:41,680 --> 00:01:44,430 Kaya ang unang bagay na namin ay namin-set ang magpalitan counter sa 0, 40 00:01:44,430 --> 00:01:46,660 at pagkatapos ay simulan namin ang pagtingin sa bawat katabing pares. 41 00:01:46,660 --> 00:01:49,140 >> Kaya una naming simulan ang pagtingin sa 5 at 2. 42 00:01:49,140 --> 00:01:52,410 Nakita namin na ang mga ito ay sa labas ng order at iba swap namin sa kanila. 43 00:01:52,410 --> 00:01:53,830 At idagdag namin ang 1 sa swap counter. 44 00:01:53,830 --> 00:01:57,860 Kaya ngayon ang aming swap counter ay 1, at 2 at 5 ay nakabukas. 45 00:01:57,860 --> 00:01:59,370 Ngayon kami ulitin ang proseso muli. 46 00:01:59,370 --> 00:02:03,540 >> Inaasahan naming sa mga susunod na katabi pair, 5 at 1-- ang mga ito ay din sa labas ng order, 47 00:02:03,540 --> 00:02:06,960 kaya swap namin ang mga ito at idagdag ang 1 sa swap counter. 48 00:02:06,960 --> 00:02:08,900 Pagkatapos namin tumingin sa 5 at 3. 49 00:02:08,900 --> 00:02:13,830 Ang mga ito ay sa labas ng order, kaya magpalit kami ang mga ito at kami ay magdagdag ng 1 sa swap counter. 50 00:02:13,830 --> 00:02:15,550 Pagkatapos namin tumingin sa 5 at 6. 51 00:02:15,550 --> 00:02:18,630 Ang mga ito sa pagkakasunud-sunod, para hindi namin talagang kailangang magpalit ng anumang bagay oras na ito. 52 00:02:18,630 --> 00:02:20,250 Pagkatapos namin tumingin sa 6 at 4. 53 00:02:20,250 --> 00:02:24,920 Ang mga ito ay din sa labas ng order, kaya magpalit kami ang mga ito at kami ay magdagdag ng 1 sa swap counter. 54 00:02:24,920 --> 00:02:26,230 >> Ngayon pansinin kung ano ang nangyari. 55 00:02:26,230 --> 00:02:29,514 Inilipat kami ng 6 na ang lahat ng mga paraan sa dulo. 56 00:02:29,514 --> 00:02:32,180 Kaya sa pagpili ng uri, kung na sa iyo nakita video na iyon, kung ano ang aming ginawa ay 57 00:02:32,180 --> 00:02:35,290 napunta kami ng paggalaw sa pinakamaliit na sangkap sa gusali 58 00:02:35,290 --> 00:02:39,640 ang pinagsunod-sunod array mahalagang mula kaliwa hanggang kanan, pinakamaliit sa pinakamalaking. 59 00:02:39,640 --> 00:02:43,200 Sa kaso ng bubble uri, kung hindi namin sumusunod sa partikular na algorithm, 60 00:02:43,200 --> 00:02:46,720 aktwal na kami ay pagpunta sa pagbuo ng ang pinagsunod-sunod array mula sa kanan 61 00:02:46,720 --> 00:02:49,100 sa kaliwa, pinakamalaking sa pinakamaliit. 62 00:02:49,100 --> 00:02:53,840 Mabisa namin bubbled 6, ang pinakamalaking halaga, ang lahat ng mga paraan sa dulo. 63 00:02:53,840 --> 00:02:56,165 >> At upang maaari naming ngayon idedeklara na iyon ay inayos, 64 00:02:56,165 --> 00:02:59,130 at sa hinaharap iterations-- pagpunta sa pamamagitan ng array again-- 65 00:02:59,130 --> 00:03:01,280 hindi namin ay may upang isaalang-alang 6 anymore. 66 00:03:01,280 --> 00:03:03,850 Kami lamang magkaroon ng upang isaalang-alang unsorted elemento 67 00:03:03,850 --> 00:03:06,299 kapag kami ay naghahanap sa katabing pares. 68 00:03:06,299 --> 00:03:08,340 Tapos Kaya kami isa pumasa sa pamamagitan ng bubble sort. 69 00:03:08,340 --> 00:03:11,941 Kaya ngayon kami bumalik sa mga tanong, ulitin hanggang sa swap counter ay 0. 70 00:03:11,941 --> 00:03:13,690 Well ang magpalitan counter ay 4, kaya kami ay pagpunta 71 00:03:13,690 --> 00:03:15,410 upang panatilihin ang paulit-ulit na muli ang proseso na ito. 72 00:03:15,410 --> 00:03:19,180 >> Kami ay pagpunta upang i-reset ang magpalitan counter sa 0, at tingnan ang bawat katabing pares. 73 00:03:19,180 --> 00:03:21,890 Kaya namin magsimula sa 2 at 1-- na ang mga ito sa labas ng order, kaya swap namin ang mga ito 74 00:03:21,890 --> 00:03:23,620 at idagdag namin 1 sa swap counter. 75 00:03:23,620 --> 00:03:25,490 2 at 3, ang mga ito sa pagkakasunud-sunod. 76 00:03:25,490 --> 00:03:27,060 Hindi natin kailangan na gawin ang anumang bagay. 77 00:03:27,060 --> 00:03:28,420 3 at 5 ay nasa ayos. 78 00:03:28,420 --> 00:03:30,150 Hindi natin kailangan gumawa ng kahit ano doon. 79 00:03:30,150 --> 00:03:32,515 >> 5 at 4, sila ay out ng order, at gayon din kami 80 00:03:32,515 --> 00:03:35,130 kailangan upang magpalitan ng mga ito at idagdag ang 1 sa swap counter. 81 00:03:35,130 --> 00:03:38,880 At ngayon kami ay inilipat 5, ang susunod na pinakamalaking sangkap, 82 00:03:38,880 --> 00:03:40,920 sa dulo ng unsorted bahagi. 83 00:03:40,920 --> 00:03:44,360 Kaya maaari na ngayong tumawag namin na bahagi ng pinagsunod-sunod na bahagi. 84 00:03:44,360 --> 00:03:47,180 >> Ngayon ikaw ay naghahanap sa screen at marahil ay maaaring sabihin, 85 00:03:47,180 --> 00:03:50,130 hangga't makakaya ko, na ang mga array ay inayos ngayon. 86 00:03:50,130 --> 00:03:51,820 Ngunit hindi pa namin maaaring patunayan na. 87 00:03:51,820 --> 00:03:54,359 Hindi namin magkaroon ng isang garantiya na ito ay pinagsunod-sunod. 88 00:03:54,359 --> 00:03:56,900 Ngunit ito ay kung saan ang swap counter ang pagpunta sa dumating sa play. 89 00:03:56,900 --> 00:03:59,060 >> Kaya naming makumpleto ang isang pass. 90 00:03:59,060 --> 00:04:00,357 Ang swap counter ay 2. 91 00:04:00,357 --> 00:04:02,190 Kaya kami ay pagpunta sa ulitin muli ang proseso na ito, 92 00:04:02,190 --> 00:04:04,290 ulitin hanggang sa swap counter ay 0. 93 00:04:04,290 --> 00:04:05,550 I-reset ang magpalitan counter sa 0. 94 00:04:05,550 --> 00:04:06,820 Kaya makikita reset namin ito. 95 00:04:06,820 --> 00:04:09,810 >> Ngayon ay tumingin sa bawat katabing pares. 96 00:04:09,810 --> 00:04:11,880 Iyan ay sa order, 1 at 2. 97 00:04:11,880 --> 00:04:13,590 2 at 3 ay sa order. 98 00:04:13,590 --> 00:04:15,010 3 at 4 ay nasa ayos. 99 00:04:15,010 --> 00:04:19,250 Kaya sa puntong ito, ang paunawa naming makumpleto ang pagtingin sa bawat kalapit na pares, 100 00:04:19,250 --> 00:04:22,530 ngunit ang swap counter ay 0 pa rin. 101 00:04:22,530 --> 00:04:25,520 >> Kung hindi namin ay may upang lumipat sa anumang mga sangkap, at pagkatapos na sila 102 00:04:25,520 --> 00:04:28,340 dapat na sa order, sa pamamagitan ng kabutihan ng prosesong ito. 103 00:04:28,340 --> 00:04:32,000 At kaya isang kahusayan ng mga uri, pag-ibig na ang mga siyentipiko namin computer, 104 00:04:32,000 --> 00:04:35,560 ay maaari na namin ngayon idedeklara ang buong array ay dapat 105 00:04:35,560 --> 00:04:38,160 pinagsunod-sunod, dahil kami ay hindi kung magpalit ng anumang elemento. 106 00:04:38,160 --> 00:04:40,380 Iyan ay medyo nice. 107 00:04:40,380 --> 00:04:43,260 >> Kaya kung ano ang pinakamasama kaso sitwasyon na may bubble sort? 108 00:04:43,260 --> 00:04:46,240 Sa pinakamasama kaso array ay sa ganap reverse order, 109 00:04:46,240 --> 00:04:49,870 at kaya kami ay may sa bubble bawat ng malaking elemento ang lahat 110 00:04:49,870 --> 00:04:51,780 mga paraan sa buong array. 111 00:04:51,780 --> 00:04:55,350 At kami rin epektibo kung bubble ang lahat ng maliit na mga elemento sa likod 112 00:04:55,350 --> 00:04:57,050 ang lahat ng mga paraan sa buong array, masyadong. 113 00:04:57,050 --> 00:05:01,950 Kaya bawat isa sa mga n elemento ay may upang ilipat sa lahat ng iba pang mga n elemento. 114 00:05:01,950 --> 00:05:04,102 Kaya na ang pinakamasama sitwasyon kaso. 115 00:05:04,102 --> 00:05:05,810 Sa pinakamahusay na kaso senaryo bagaman, ito ay 116 00:05:05,810 --> 00:05:07,880 bahagyang naiiba mula sa mga uri ng pagpili. 117 00:05:07,880 --> 00:05:10,040 Ang array ay nai Inayos kapag pumunta kami in. 118 00:05:10,040 --> 00:05:12,550 Hindi namin kailangang gumawa ng anumang swaps sa unang pass. 119 00:05:12,550 --> 00:05:14,940 Kaya maaari naming magkaroon upang tumingin sa mas kaunting mga elemento, tama? 120 00:05:14,940 --> 00:05:18,580 Hindi natin kailangang ulitin ito proseso ang isang bilang ng mga beses sa loob. 121 00:05:18,580 --> 00:05:19,540 >> Kaya kung ano ang ibig sabihin nito? 122 00:05:19,540 --> 00:05:22,390 Kaya kung ano ang pinakamasama kaso sitwasyon para sa bubble-uuri, at kung ano ang 123 00:05:22,390 --> 00:05:25,330 ang pinakamahusay na kaso sitwasyon para sa bubble sort? 124 00:05:25,330 --> 00:05:27,770 Hulaan mo ba ito? 125 00:05:27,770 --> 00:05:32,420 Sa pinakamasama kaso kailangan mong umulit sa lahat ng mga elemento n n ulit. 126 00:05:32,420 --> 00:05:34,220 Kaya ang pinakamasama kaso ay n nakalapat. 127 00:05:34,220 --> 00:05:36,550 >> Kung ang array ay ganap na ganap Pinagbukud-bukod bagaman, ikaw lamang 128 00:05:36,550 --> 00:05:38,580 kung tumingin sa bawat ng mga elemento ng isang beses. 129 00:05:38,580 --> 00:05:42,670 At kung ang swap counter ay 0 pa rin, maaari mong sabihin na ito array ay inayos. 130 00:05:42,670 --> 00:05:45,780 At kaya sa pinakamahusay na kaso, ito ay talagang mas mahusay kaysa sa pagpili 131 00:05:45,780 --> 00:05:49,230 sort-- ito ay katapusan ng n. 132 00:05:49,230 --> 00:05:50,270 >> Ako Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Ito ay CS50. 134 00:05:52,140 --> 00:05:54,382