1 00:00:00,000 --> 00:00:03,360 >> [Mūzikas atskaņošanai] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 Doug LLOYD: Labi, tāpēc burbulis šķirot ir algoritms 4 00:00:06,730 --> 00:00:08,730 Jūs varat izmantot, lai sakārtotu elementu kopumu. 5 00:00:08,730 --> 00:00:10,850 Pieņemsim to apskatīt, kā tā darbojas. 6 00:00:10,850 --> 00:00:13,240 >> Tātad Pamatideja burbulis šķirot tas ir. 7 00:00:13,240 --> 00:00:17,340 Mēs parasti gribam virzīties augstāka vērtē elementi parasti pa labi, 8 00:00:17,340 --> 00:00:20,340 un nolaidiet vērtē elementus parasti pa kreisi, kā mēs varētu gaidīt. 9 00:00:20,340 --> 00:00:23,256 Mēs vēlamies, zemākas lietas būt sākums, un augstākās lietas 10 00:00:23,256 --> 00:00:24,970 būt beigās. 11 00:00:24,970 --> 00:00:26,130 >> Kā mēs to darām? 12 00:00:26,130 --> 00:00:28,040 Nu pseudocode kodu, mēs varētu teikt, pieņemsim 13 00:00:28,040 --> 00:00:30,320 noteikt aizstāšanas counter kas nav saistīts ar nulles vērtību. 14 00:00:30,320 --> 00:00:32,570 Mēs redzēsim, kāpēc mēs to darām, ka sekundē. 15 00:00:32,570 --> 00:00:36,090 Un tad mēs atkārtot šādu process, līdz mijmaiņas skaitītājs ir 0, 16 00:00:36,090 --> 00:00:39,910 vai līdz brīdim, kad mēs nepieļaujam mijmaiņas darījumus vispār. 17 00:00:39,910 --> 00:00:43,170 >> Reset mijmaiņas counter līdz 0, ja tas nav jau 0. 18 00:00:43,170 --> 00:00:46,420 Tad apskatīt katru blakus pāri no elementiem. 19 00:00:46,420 --> 00:00:49,550 Ja šie divi elementi ir nav kārtībā, mijmaiņas tiem, 20 00:00:49,550 --> 00:00:51,620 un pievienot 1 līdz swap letes. 21 00:00:51,620 --> 00:00:53,870 Ja jūs domājat par tas pirms jūs vizualizēt to, 22 00:00:53,870 --> 00:00:57,471 ievērosiet, ka tas pāries zemāks vērtē elementi kreisi 23 00:00:57,471 --> 00:01:00,720 un augstāka vērtē elementus tiesībām, efektīvi darīt to, ko mēs vēlamies darīt, 24 00:01:00,720 --> 00:01:03,940 kas ir pārvietot šos grupas Elementu šādā veidā. 25 00:01:03,940 --> 00:01:07,035 Pieņemsim iztēloties, kā tas varētu izskatīties, izmantojot mūsu masīvs 26 00:01:07,035 --> 00:01:10,504 ka mēs izmantojām, lai pārbaudītu out šiem algoritmiem. 27 00:01:10,504 --> 00:01:13,420 Mums ir nešķirotas masīvs šeit atkal, norādīts ar visiem elementiem 28 00:01:13,420 --> 00:01:14,840 ir sarkanā krāsā. 29 00:01:14,840 --> 00:01:17,970 Un es noteikt manu mijmaiņas skaitītājs līdz nulle vērtības. 30 00:01:17,970 --> 00:01:20,610 Es patvaļīgi izvēlējās negatīvs 1-- tas nav 0. 31 00:01:20,610 --> 00:01:23,840 Mēs vēlamies, lai atkārtot šo procesu līdz mijmaiņas letes ir 0. 32 00:01:23,840 --> 00:01:26,540 Tas ir iemesls, kāpēc es noteikt manu swap pretrunā ar kādu ne-nulles vērtību, 33 00:01:26,540 --> 00:01:29,400 jo pretējā gadījumā swap skaitītājs būtu 0. 34 00:01:29,400 --> 00:01:31,610 Mēs nebūtu pat sākas process algoritms. 35 00:01:31,610 --> 00:01:33,610 Tātad vēlreiz, soļi are-- reset mijmaiņas skaitītāju 36 00:01:33,610 --> 00:01:37,900 0, tad apskatīt katru blakus pāris, un, ja viņi no rīkojuma, 37 00:01:37,900 --> 00:01:40,514 mijmaiņas tiem, un pievieno 1 uz swap letes. 38 00:01:40,514 --> 00:01:41,680 Tātad, pieņemsim sākt šo procesu. 39 00:01:41,680 --> 00:01:44,430 Tātad, pirmā lieta, kas mums jādara, ir mēs noteikti mijmaiņas skaitītāju uz 0, 40 00:01:44,430 --> 00:01:46,660 un tad mēs sākt meklēt katrā divām blakus esošajām. 41 00:01:46,660 --> 00:01:49,140 >> Tātad mēs vispirms sākt meklēt pie 5 un 2. 42 00:01:49,140 --> 00:01:52,410 Mēs redzam, ka tie ir no pasūtīt un tāpēc mēs mijmaiņas tiem. 43 00:01:52,410 --> 00:01:53,830 Un mēs pievienojam 1 līdz swap letes. 44 00:01:53,830 --> 00:01:57,860 Tātad tagad mūsu swap skaitītājs ir 1, un 2 un 5 ir ieslēgta. 45 00:01:57,860 --> 00:01:59,370 Tagad mēs atkal atkārtojiet procesu. 46 00:01:59,370 --> 00:02:03,540 >> Mēs apskatīt nākamajā divām blakus esošajām, 5 un 1-- viņi arī no rīkojuma, 47 00:02:03,540 --> 00:02:06,960 tāpēc mēs mijmaiņas tiem un pievienot 1 uz mijmaiņas letes. 48 00:02:06,960 --> 00:02:08,900 Tad mēs skatāmies 5 un 3. 49 00:02:08,900 --> 00:02:13,830 Tie ir iziet no ierindas, tāpēc mēs mijmaiņas viņiem un mēs pievienot 1 līdz swap letes. 50 00:02:13,830 --> 00:02:15,550 Tad mēs skatāmies uz 5 un 6. 51 00:02:15,550 --> 00:02:18,630 Viņi lai, tāpēc mums nav reāli nepieciešams apmainīt Jebkas šoreiz. 52 00:02:18,630 --> 00:02:20,250 Tad mēs skatāmies uz 6 un 4. 53 00:02:20,250 --> 00:02:24,920 Viņi arī iziet no ierindas, tāpēc mēs mijmaiņas viņiem un mēs pievienot 1 līdz swap letes. 54 00:02:24,920 --> 00:02:26,230 >> Tagad pamanīt to, kas ir noticis. 55 00:02:26,230 --> 00:02:29,514 Mēs esam pārvietots 6 visu ceļu līdz beigām. 56 00:02:29,514 --> 00:02:32,180 Tātad atlases veida, ja jūs esat redzams, ka video, ko mēs darījām, bija 57 00:02:32,180 --> 00:02:35,290 mēs beidzās pārvietojot mazākie elementi ēkā 58 00:02:35,290 --> 00:02:39,640 šķiroto masīvs būtībā no kreisās puses uz labo, mazākais uz lielāko. 59 00:02:39,640 --> 00:02:43,200 Attiecībā uz burbuļa veida, ja mēs pēc šo konkrēto algoritmu, 60 00:02:43,200 --> 00:02:46,720 mēs tiešām gribam būt ēkas šķiroto masīvs no labās 61 00:02:46,720 --> 00:02:49,100 pa kreisi, vislielākā uz vismazāko. 62 00:02:49,100 --> 00:02:53,840 Mums ir efektīvi burbuļojot 6, to lielākā vērtība, visu ceļu līdz beigām. 63 00:02:53,840 --> 00:02:56,165 >> Un tāpēc mēs tagad varam paziņot, ka tas ir sakārtots, 64 00:02:56,165 --> 00:02:59,130 un nākotnē iterations-- iet cauri masīva again-- 65 00:02:59,130 --> 00:03:01,280 mums nav jāapsver 6 vairs. 66 00:03:01,280 --> 00:03:03,850 Mums tikai ir jāapsver nešķirotajiem elementi 67 00:03:03,850 --> 00:03:06,299 kad mēs esam apskatot blakus esošiem pāriem. 68 00:03:06,299 --> 00:03:08,340 Tātad mēs esam pabeiguši vienu iet cauri burbuļu veida. 69 00:03:08,340 --> 00:03:11,941 Tāpēc tagad mēs ejam atpakaļ uz jautājumu, atkārto, līdz mijmaiņas skaitītājs ir 0. 70 00:03:11,941 --> 00:03:13,690 Nu mijmaiņas skaitītājs ir 4, tāpēc mēs ejam 71 00:03:13,690 --> 00:03:15,410 saglabāt vēlreiz atkārtojot šo procesu. 72 00:03:15,410 --> 00:03:19,180 >> Mēs ejam, lai atjaunotu mijmaiņas skaitītāju līdz 0, un apskatīt katru blakus pāri. 73 00:03:19,180 --> 00:03:21,890 Tātad sākam ar 2 un 1-- viņi iziet no ierindas, tāpēc mēs mijmaiņas tiem 74 00:03:21,890 --> 00:03:23,620 un mēs pievienot 1 līdz swap letes. 75 00:03:23,620 --> 00:03:25,490 2 un 3, viņi kārtībā. 76 00:03:25,490 --> 00:03:27,060 Mums nav nepieciešams neko darīt. 77 00:03:27,060 --> 00:03:28,420 3 un 5 ir kārtībā. 78 00:03:28,420 --> 00:03:30,150 Mums nav nepieciešams neko darīt tur. 79 00:03:30,150 --> 00:03:32,515 >> 5 un 4, tie ir ārā no ierindas, un tāpēc mēs 80 00:03:32,515 --> 00:03:35,130 nepieciešams, lai mijmaiņas tiem un pievienot 1 uz mijmaiņas letes. 81 00:03:35,130 --> 00:03:38,880 Un tagad mēs esam pārvietoti 5, nākamais lielākais elements, 82 00:03:38,880 --> 00:03:40,920 līdz beigām nešķirotu porciju. 83 00:03:40,920 --> 00:03:44,360 Tātad, mēs tagad var zvanīt, ka daļa sakārtoti porciju. 84 00:03:44,360 --> 00:03:47,180 >> Tagad jūs meklējat pie ekrāns un, iespējams, var pateikt, 85 00:03:47,180 --> 00:03:50,130 kā es varu, ka masīva ir sakārtots tieši tagad. 86 00:03:50,130 --> 00:03:51,820 Bet mēs nevaram pierādīt, ka vēl. 87 00:03:51,820 --> 00:03:54,359 Mums nav garantija ka tas ir sakārtoti. 88 00:03:54,359 --> 00:03:56,900 Bet tas ir, ja mijmaiņas counter gatavojas stāties spēlēt. 89 00:03:56,900 --> 00:03:59,060 >> Tāpēc mēs esam pabeiguši caurlaidi. 90 00:03:59,060 --> 00:04:00,357 Mijmaiņas skaitītājs ir 2. 91 00:04:00,357 --> 00:04:02,190 Tātad mēs ejam atkārtot šis process atkal, 92 00:04:02,190 --> 00:04:04,290 atkārto, līdz mijmaiņas skaitītājs ir 0. 93 00:04:04,290 --> 00:04:05,550 Reset mijmaiņas skaitītāju uz 0. 94 00:04:05,550 --> 00:04:06,820 Tātad mēs atjaunotu to. 95 00:04:06,820 --> 00:04:09,810 >> Tagad apskatīt katru blakus pāri. 96 00:04:09,810 --> 00:04:11,880 Tas ir kārtībā, 1. un 2.. 97 00:04:11,880 --> 00:04:13,590 2 un 3 ir kārtībā. 98 00:04:13,590 --> 00:04:15,010 3 un 4 ir kārtībā. 99 00:04:15,010 --> 00:04:19,250 Tātad šajā brīdī, paziņojums mēs esam pabeiguši Aplūkojot katru blakus pāri, 100 00:04:19,250 --> 00:04:22,530 bet mijmaiņas skaitītājs joprojām 0. 101 00:04:22,530 --> 00:04:25,520 >> Ja mums nav, lai pārslēgtos kādi elementi, tad tie 102 00:04:25,520 --> 00:04:28,340 ir jābūt kārtībā, ko pamatojoties uz šo procesu. 103 00:04:28,340 --> 00:04:32,000 Un tā Lietderības koeficients veidu, Ka mēs datorzinātnieku mīlam, 104 00:04:32,000 --> 00:04:35,560 ir, mēs tagad varam paziņot, visam blokam jābūt 105 00:04:35,560 --> 00:04:38,160 sakārtots, jo mēs neesam ir swap kādi elementi. 106 00:04:38,160 --> 00:04:40,380 Tas ir diezgan jauki. 107 00:04:40,380 --> 00:04:43,260 >> Tātad, kas ir sliktākais gadījums scenārijs ar burbuļu veida? 108 00:04:43,260 --> 00:04:46,240 Sliktākajā gadījumā masīvs ir pilnīgi apgrieztā secībā, 109 00:04:46,240 --> 00:04:49,870 un tāpēc mums ir burbulis katram no lielajiem elementiem visu 110 00:04:49,870 --> 00:04:51,780 ceļu pāri masīvs. 111 00:04:51,780 --> 00:04:55,350 Un mums faktiski ir arī burbulis visi no mazo elementu atpakaļ 112 00:04:55,350 --> 00:04:57,050 visu ceļu pāri masīvs, too. 113 00:04:57,050 --> 00:05:01,950 Tātad, katrs no n elementiem ir, lai pārvietotos pāri visiem citiem n elementiem. 114 00:05:01,950 --> 00:05:04,102 Tātad tas ir sliktākais scenārijs. 115 00:05:04,102 --> 00:05:05,810 Labākajā gadījumā scenārijs, lai gan, tas ir 116 00:05:05,810 --> 00:05:07,880 nedaudz atšķiras no atlases veida. 117 00:05:07,880 --> 00:05:10,040 Masīvs ir jau sakārtots, kad mēs iet. 118 00:05:10,040 --> 00:05:12,550 Mums nav nekādas mijmaiņas darījumi par pirmo caurlaide. 119 00:05:12,550 --> 00:05:14,940 Tātad mēs varētu būt jāmeklē pie mazāk elementiem, vai ne? 120 00:05:14,940 --> 00:05:18,580 Mums nav jāatkārto šis apstrādāt vairākas reizes. 121 00:05:18,580 --> 00:05:19,540 >> Tātad, ko tas nozīmē? 122 00:05:19,540 --> 00:05:22,390 Tātad, kas ir sliktākais scenārijs burbuļu veida, un to, kas ir 123 00:05:22,390 --> 00:05:25,330 Labākajā gadījumā burbulis kārtot? 124 00:05:25,330 --> 00:05:27,770 Vai jūs uzminēt šo? 125 00:05:27,770 --> 00:05:32,420 Sliktākajā gadījumā, jums ir atkārtot visās n elementiem n reizes. 126 00:05:32,420 --> 00:05:34,220 Tātad sliktākajā gadījumā ir n brusas. 127 00:05:34,220 --> 00:05:36,550 >> Ja masīvs ir pilnīgi šķiroto gan, jums ir tikai 128 00:05:36,550 --> 00:05:38,580 ir jāskatās uz katru no elementiem vienu reizi. 129 00:05:38,580 --> 00:05:42,670 Un, ja mijmaiņas skaitītājs joprojām ir 0, Jūs varat teikt, tas masīvs ir sakārtots. 130 00:05:42,670 --> 00:05:45,780 Un tā labākajā gadījumā, tas ir tiešām labāk nekā atlases 131 00:05:45,780 --> 00:05:49,230 sort-- tas ir omega n. 132 00:05:49,230 --> 00:05:50,270 >> Es esmu Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Tas ir CS50. 134 00:05:52,140 --> 00:05:54,382