1 00:00:00,000 --> 00:00:03,360 >> [Predvaja glasba] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 Doug LLOYD: V redu, tako da bubble nekako je algoritem 4 00:00:06,730 --> 00:00:08,730 lahko uporabite za razvrščanje niz elementov. 5 00:00:08,730 --> 00:00:10,850 Oglejmo si, kako to deluje. 6 00:00:10,850 --> 00:00:13,240 >> Torej osnovna ideja bubble nekako gre. 7 00:00:13,240 --> 00:00:17,340 Smo na splošno želijo premakniti višje cenjene elementi običajno na desni, 8 00:00:17,340 --> 00:00:20,340 in nižje vrednotijo ​​elemente splošno na levi, kot bi pričakovali. 9 00:00:20,340 --> 00:00:23,256 Želimo nižje stvari, da se na začetek, in višje stvari 10 00:00:23,256 --> 00:00:24,970 da je na koncu. 11 00:00:24,970 --> 00:00:26,130 >> Kako to storiti? 12 00:00:26,130 --> 00:00:28,040 No, v psevdokoda kodo, lahko bi rekli, Dovolite 13 00:00:28,040 --> 00:00:30,320 nastaviti izmenjalno nasprotju z ne-ničelno vrednost. 14 00:00:30,320 --> 00:00:32,570 Bomo videli, zakaj delamo to, da je v sekundi. 15 00:00:32,570 --> 00:00:36,090 In potem smo ponovili naslednji Proces dokler swap števec 0, 16 00:00:36,090 --> 00:00:39,910 ali dokler ne naredimo nobene zamenjave sploh. 17 00:00:39,910 --> 00:00:43,170 >> Reset swap nasprotju z 0, če to ni že 0. 18 00:00:43,170 --> 00:00:46,420 Potem poglej vse sosednji par elementov. 19 00:00:46,420 --> 00:00:49,550 Če sta ta dva elementa ni v redu, jih zamenjajte, 20 00:00:49,550 --> 00:00:51,620 in dodamo 1 do zamenjave števca. 21 00:00:51,620 --> 00:00:53,870 Če razmišljate o tem to preden jo vizualizirati, 22 00:00:53,870 --> 00:00:57,471 opazili, da se bo to premakniti nižje vrednotene elementi na levi 23 00:00:57,471 --> 00:01:00,720 in višje vrednotijo ​​elemente v desno, dejansko to, kar želimo narediti, 24 00:01:00,720 --> 00:01:03,940 ki se premikajo tiste skupine elementov v ta način. 25 00:01:03,940 --> 00:01:07,035 Oglejmo vizualizirati, kako to lahko poiščete z uporabo našega niz 26 00:01:07,035 --> 00:01:10,504 ki smo ga uporabili za testiranje od teh algoritmov. 27 00:01:10,504 --> 00:01:13,420 Zopet smo imeli neurejen paleto tukaj, z vseh elementov navedeno 28 00:01:13,420 --> 00:01:14,840 da je v rdeči barvi. 29 00:01:14,840 --> 00:01:17,970 In jaz nastavim swap števec na neničelno vrednost. 30 00:01:17,970 --> 00:01:20,610 Sem samovoljno odločil, negativna 1-- to ni 0. 31 00:01:20,610 --> 00:01:23,840 Želimo, da ponovite ta postopek do zamenjave števca je 0. 32 00:01:23,840 --> 00:01:26,540 To je razlog, zakaj sem iz moje swap v nasprotju z nekaterimi ne-ničelno vrednost, 33 00:01:26,540 --> 00:01:29,400 ker v nasprotnem primeru swap Števec bi bilo 0. 34 00:01:29,400 --> 00:01:31,610 Mi ne bi niti zajadrati v Postopek algoritma. 35 00:01:31,610 --> 00:01:33,610 Torej še enkrat, koraki are-- reset swap števec 36 00:01:33,610 --> 00:01:37,900 0, potem poglej na vsak sosednji par, in če oni v okvari, 37 00:01:37,900 --> 00:01:40,514 swap njih, in dodamo 1 do zamenjave števca. 38 00:01:40,514 --> 00:01:41,680 Torej začnimo ta proces. 39 00:01:41,680 --> 00:01:44,430 Torej prva stvar, ki mi je smo postavili swap števec na 0, 40 00:01:44,430 --> 00:01:46,660 in potem smo začeli iskati pri vsakim sosednjim parom. 41 00:01:46,660 --> 00:01:49,140 >> Tako smo najprej začeli iskati na 5 in 2. 42 00:01:49,140 --> 00:01:52,410 Vidimo, da so iz naročite in tako smo jih zamenjali. 43 00:01:52,410 --> 00:01:53,830 In smo dodali 1 do zamenjave števca. 44 00:01:53,830 --> 00:01:57,860 Torej, zdaj je naša swap števec je 1, in 2 in 5 so bili zamenjan. 45 00:01:57,860 --> 00:01:59,370 Zdaj smo spet ponoviti postopek. 46 00:01:59,370 --> 00:02:03,540 >> Gledamo na naslednji sosednji par, 5 in 1-- oni tudi v okvari, 47 00:02:03,540 --> 00:02:06,960 zato smo jih zamenjali in dodajte 1 do zamenjave števca. 48 00:02:06,960 --> 00:02:08,900 Potem gledamo na 5 in 3. 49 00:02:08,900 --> 00:02:13,830 So v okvari, zato smo zamenjali jih in dodamo 1 do zamenjave števca. 50 00:02:13,830 --> 00:02:15,550 Potem gledamo na 5 in 6. 51 00:02:15,550 --> 00:02:18,630 Oni so v redu, tako da ne bomo dejansko morali zamenjati ničesar ta čas. 52 00:02:18,630 --> 00:02:20,250 Potem gledamo na 6 in 4. 53 00:02:20,250 --> 00:02:24,920 Oni so tudi v okvari, zato smo zamenjali jih in dodamo 1 do zamenjave števca. 54 00:02:24,920 --> 00:02:26,230 >> Zdaj opazili, kaj se je zgodilo. 55 00:02:26,230 --> 00:02:29,514 Mi smo se preselili 6 vse do konca. 56 00:02:29,514 --> 00:02:32,180 Torej, v izbirnem vrste, če ste razvidno, da je video, kar smo naredili je bilo 57 00:02:32,180 --> 00:02:35,290 smo končali premikanje najmanjši elementi v stavbi 58 00:02:35,290 --> 00:02:39,640 urejen matrika predvsem iz od leve proti desni, najmanjše do največje. 59 00:02:39,640 --> 00:02:43,200 Pri mehurčkov vrste, če smo po tem algoritmu, 60 00:02:43,200 --> 00:02:46,720 smo dejansko dogaja, da se gradi urejen matrika z desne 61 00:02:46,720 --> 00:02:49,100 levo, največjih do najmanjših. 62 00:02:49,100 --> 00:02:53,840 Smo uspešno mehurčkih 6, na Največja vrednost, vse do konca. 63 00:02:53,840 --> 00:02:56,165 >> In tako smo zdaj lahko razglasi da je ta razporejene, 64 00:02:56,165 --> 00:02:59,130 in v prihodnosti iterations-- gredo skozi paleto again-- 65 00:02:59,130 --> 00:03:01,280 nimamo razmisliti 6 anymore. 66 00:03:01,280 --> 00:03:03,850 Imamo le, da razmisli nerazvrščenih elementi 67 00:03:03,850 --> 00:03:06,299 ko smo iskali na sosednjih parov. 68 00:03:06,299 --> 00:03:08,340 Tako smo končali eno skozi mehurček vrste. 69 00:03:08,340 --> 00:03:11,941 Torej, zdaj gremo nazaj k vprašanju, ponovite, dokler swap števec je 0. 70 00:03:11,941 --> 00:03:13,690 No swap števec je 4, zato bomo 71 00:03:13,690 --> 00:03:15,410 da ponovno ponavljanjem postopka. 72 00:03:15,410 --> 00:03:19,180 >> Bomo ponastaviti swap števec 0 in poglej vsakim sosednjim parom. 73 00:03:19,180 --> 00:03:21,890 Tako smo začeli z 2 in 1-- oni v okvari, zato smo jih zamenjali 74 00:03:21,890 --> 00:03:23,620 in dodamo 1 do zamenjave števca. 75 00:03:23,620 --> 00:03:25,490 2 in 3, oni so v redu. 76 00:03:25,490 --> 00:03:27,060 Mi ni treba storiti ničesar. 77 00:03:27,060 --> 00:03:28,420 3 in 5 so v redu. 78 00:03:28,420 --> 00:03:30,150 Mi ni treba storiti ničesar tam. 79 00:03:30,150 --> 00:03:32,515 >> 5 in 4, so iz reda, in zato smo 80 00:03:32,515 --> 00:03:35,130 potrebujejo, da jih swap in dodajte 1 do zamenjave števca. 81 00:03:35,130 --> 00:03:38,880 In zdaj smo se preselili 5, Naslednji največji element, 82 00:03:38,880 --> 00:03:40,920 na koncu nesortiranih odseka. 83 00:03:40,920 --> 00:03:44,360 Tako bomo lahko zdaj pokličete, da del razvrščeni odseka. 84 00:03:44,360 --> 00:03:47,180 >> Zdaj si pogledamo Zaslon in verjetno lahko povem, 85 00:03:47,180 --> 00:03:50,130 kot lahko sem, da matriki je razvrščen zdaj. 86 00:03:50,130 --> 00:03:51,820 Vendar še ne moremo dokazati, da. 87 00:03:51,820 --> 00:03:54,359 Nimamo garancijo da je to urejeno. 88 00:03:54,359 --> 00:03:56,900 Toda to je, če swap Števec se dogaja, da pridejo v poštev. 89 00:03:56,900 --> 00:03:59,060 >> Tako smo zaključili sredino. 90 00:03:59,060 --> 00:04:00,357 Swap števec je 2. 91 00:04:00,357 --> 00:04:02,190 Torej bomo ponovili spet ta proces, 92 00:04:02,190 --> 00:04:04,290 ponovite, dokler swap števec je 0. 93 00:04:04,290 --> 00:04:05,550 Reset izmenjalno števec na 0. 94 00:04:05,550 --> 00:04:06,820 Torej ga bomo ponastaviti. 95 00:04:06,820 --> 00:04:09,810 >> Zdaj pa poglej vsakim sosednjim parom. 96 00:04:09,810 --> 00:04:11,880 To je v redu, 1 in 2. 97 00:04:11,880 --> 00:04:13,590 2 in 3 so v redu. 98 00:04:13,590 --> 00:04:15,010 3 in 4 so v redu. 99 00:04:15,010 --> 00:04:19,250 Torej, na tej točki, opazili smo zaključili gledaš vsak sosednji par, 100 00:04:19,250 --> 00:04:22,530 vendar swap števec je še vedno 0. 101 00:04:22,530 --> 00:04:25,520 >> Če ne bomo imeli, da preklopite vsak element, potem 102 00:04:25,520 --> 00:04:28,340 mora biti v vrstnem redu, ki ga odlika tega procesa. 103 00:04:28,340 --> 00:04:32,000 In tako izkoristek z menoj, da smo računalniški znanstveniki radi, 104 00:04:32,000 --> 00:04:35,560 se bomo sedaj lahko razglasi celotna matrika mošt 105 00:04:35,560 --> 00:04:38,160 treba sortirati, ker nismo storili morali zamenjati nobenih elementov. 106 00:04:38,160 --> 00:04:40,380 To je zelo lepo. 107 00:04:40,380 --> 00:04:43,260 >> Torej, kaj je v najslabšem primeru Scenarij z mehurček vrste? 108 00:04:43,260 --> 00:04:46,240 V najslabšem primeru je matrika je v popolnoma obratnem vrstnem redu, 109 00:04:46,240 --> 00:04:49,870 in zato moramo mehurček vsak velikih elementov vsi 110 00:04:49,870 --> 00:04:51,780 pot čez polja. 111 00:04:51,780 --> 00:04:55,350 In smo dejansko imeli tudi mehurček vse majhnih elementov nazaj 112 00:04:55,350 --> 00:04:57,050 vso pot čez polja, preveč. 113 00:04:57,050 --> 00:05:01,950 Torej je vsak izmed n elementov mora premakniti čez vse druge n elementov. 114 00:05:01,950 --> 00:05:04,102 Tako, da je najslabši možni scenarij. 115 00:05:04,102 --> 00:05:05,810 V najboljšem primeru scenarij, čeprav je to 116 00:05:05,810 --> 00:05:07,880 nekoliko razlikujejo od izbora vrste. 117 00:05:07,880 --> 00:05:10,040 Matrika je že razporejene, ko gremo v. 118 00:05:10,040 --> 00:05:12,550 Nimamo, da bi katerikoli Zamenjave na prvo priložnost. 119 00:05:12,550 --> 00:05:14,940 Tako bomo morda morali pogledati na manj elementov, kajne? 120 00:05:14,940 --> 00:05:18,580 Nimamo ponoviti to obdelati večkrat konec. 121 00:05:18,580 --> 00:05:19,540 >> Torej, kaj to pomeni? 122 00:05:19,540 --> 00:05:22,390 Torej, kaj je najslabši možni scenarij za mehurček vrste, in kaj je 123 00:05:22,390 --> 00:05:25,330 najboljši scenarij za bubble vrste? 124 00:05:25,330 --> 00:05:27,770 Ali ste ugibati to? 125 00:05:27,770 --> 00:05:32,420 V najslabšem primeru boste morali ponoviti vseh elementov N-krat. 126 00:05:32,420 --> 00:05:34,220 Torej je v najslabšem primeru n kvadrat. 127 00:05:34,220 --> 00:05:36,550 >> Če array je popolnoma sortirani, čeprav, samo vi 128 00:05:36,550 --> 00:05:38,580 morali gledati na vsak elementov enkrat. 129 00:05:38,580 --> 00:05:42,670 In če je swap števec je še vedno 0, lahko rečem je to matrika je razvrščen. 130 00:05:42,670 --> 00:05:45,780 In tako v najboljšem primeru pa je to dejansko boljši od izbora 131 00:05:45,780 --> 00:05:49,230 sort-- je omega n. 132 00:05:49,230 --> 00:05:50,270 >> Sem Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 To je CS50. 134 00:05:52,140 --> 00:05:54,382