1 00:00:00,000 --> 00:00:03,360 >> [Muzika] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG Lloyd: Të gjithë të drejtë, kështu që flluskë lloj është një algoritëm 4 00:00:06,730 --> 00:00:08,730 ju mund të përdorni për të zgjidhur një sërë elementesh. 5 00:00:08,730 --> 00:00:10,850 Le të marrin një sy se si funksionon. 6 00:00:10,850 --> 00:00:13,240 >> Pra, ideja themelore prapa flluskë lloj është kjo. 7 00:00:13,240 --> 00:00:17,340 Ne në përgjithësi duan të lëvizin të lartë elemente me vlerë në përgjithësi në të djathtë, 8 00:00:17,340 --> 00:00:20,340 dhe të ulët elemente me vlerë në përgjithësi në të majtë, ndërsa ne do të presim. 9 00:00:20,340 --> 00:00:23,256 Ne duam që gjërat më të ulëta të jenë në fillimi, dhe gjërat më të larta 10 00:00:23,256 --> 00:00:24,970 që të jetë në fund. 11 00:00:24,970 --> 00:00:26,130 >> Si e bëjmë këtë? 12 00:00:26,130 --> 00:00:28,040 Edhe në kodin e pseudokod, ne mund të themi, le të 13 00:00:28,040 --> 00:00:30,320 vendosur një kundër swap në një vlerë jo-zero. 14 00:00:30,320 --> 00:00:32,570 Ne do të shohim se pse ne bëjmë atë në një të dytë. 15 00:00:32,570 --> 00:00:36,090 Dhe pastaj ne të përsëritur në vijim Procesi deri swap counter është 0, 16 00:00:36,090 --> 00:00:39,910 ose derisa ne kemi bërë asnjë këmbime në të gjitha. 17 00:00:39,910 --> 00:00:43,170 >> Reset counter swap për 0 në qoftë se ajo nuk është tashmë 0. 18 00:00:43,170 --> 00:00:46,420 Pastaj të shohim në çdo palë ngjitur e elementeve. 19 00:00:46,420 --> 00:00:49,550 Nëse këto dy elemente janë jo në mënyrë, të bie në ujdi tyre, 20 00:00:49,550 --> 00:00:51,620 dhe shtoni 1 me swap banak. 21 00:00:51,620 --> 00:00:53,870 Nëse jeni duke menduar në lidhje me kjo para se ju kujtoj atë, 22 00:00:53,870 --> 00:00:57,471 vini re se kjo do të lëvizë më të ulët elemente me vlerë në të majtë 23 00:00:57,471 --> 00:01:00,720 dhe elementët në të djathtë vlerë të lartë, në mënyrë efektive duke bërë atë që ne duam të bëjmë, 24 00:01:00,720 --> 00:01:03,940 i cili është të lëvizë ato grupe e elementeve në këtë mënyrë. 25 00:01:03,940 --> 00:01:07,035 Le të parashikoj se si kjo mund të duket përdorur array tonë 26 00:01:07,035 --> 00:01:10,504 që kemi përdorur për të testuar nga këto algoritme. 27 00:01:10,504 --> 00:01:13,420 Ne kemi një rrjet Unsorted këtu përsëri, treguar nga të gjithë elementët 28 00:01:13,420 --> 00:01:14,840 duke qenë në të kuqe. 29 00:01:14,840 --> 00:01:17,970 Dhe kam vendosur counter time swap në një vlerë jozero. 30 00:01:17,970 --> 00:01:20,610 Unë zgjodha në mënyrë arbitrare negativ 1-- kjo nuk është 0. 31 00:01:20,610 --> 00:01:23,840 Ne duam të përsërisim këtë proces derisa shkëmbimit banak është 0. 32 00:01:23,840 --> 00:01:26,540 Kjo është arsyeja pse kam vendosur swap tim në kundërshtim me disa vlera jo-zero, 33 00:01:26,540 --> 00:01:29,400 sepse përndryshe shkëmbim counter do të jetë 0. 34 00:01:29,400 --> 00:01:31,610 Ne nuk do të fillojë edhe Procesi i algoritmi. 35 00:01:31,610 --> 00:01:33,610 Pra, përsëri, hapat are-- reset swap counter 36 00:01:33,610 --> 00:01:37,900 0, pastaj të shohim në çdo ngjitur palë, dhe nëse ata janë jashtë funksionit, 37 00:01:37,900 --> 00:01:40,514 bie në ujdi tyre, dhe të shtoni 1 të swap banak. 38 00:01:40,514 --> 00:01:41,680 Pra, le të fillojmë këtë proces. 39 00:01:41,680 --> 00:01:44,430 Pra, gjëja e parë që bëni është të ne kemi vendosur swap counter në 0, 40 00:01:44,430 --> 00:01:46,660 dhe pastaj ne fillojmë të shikojmë në çdo çift ngjitur. 41 00:01:46,660 --> 00:01:49,140 >> Pra, ne së pari të fillojmë të shikojmë në 5 dhe 2. 42 00:01:49,140 --> 00:01:52,410 Ne shohim se ata janë jashtë rendit dhe kështu që ne bie në ujdi tyre. 43 00:01:52,410 --> 00:01:53,830 Dhe ne shtoni 1 me swap banak. 44 00:01:53,830 --> 00:01:57,860 Kështu që tani shkëmbim counter tonë është 1, dhe 2 dhe 5 kanë qenë të ndezur. 45 00:01:57,860 --> 00:01:59,370 Tani ne përsëris procesin përsëri. 46 00:01:59,370 --> 00:02:03,540 >> Ne shikojmë në palë tjetër ngjitur, 5 dhe 1-- ata janë edhe jashtë funksionit, 47 00:02:03,540 --> 00:02:06,960 kështu që ne bie në ujdi tyre dhe shtoni 1 në swap banak. 48 00:02:06,960 --> 00:02:08,900 Atëherë ne shikojmë në 5 dhe 3. 49 00:02:08,900 --> 00:02:13,830 Ata janë jashtë funksionit, kështu që ne të bie në ujdi ata dhe ne shtoni 1 me swap banak. 50 00:02:13,830 --> 00:02:15,550 Atëherë ne shikojmë në 5 dhe 6. 51 00:02:15,550 --> 00:02:18,630 Ata janë në rregull, kështu që ne nuk mund të vërtetë duhet të bie në ujdi asgjë këtë herë. 52 00:02:18,630 --> 00:02:20,250 Atëherë ne shikojmë në 6 dhe 4. 53 00:02:20,250 --> 00:02:24,920 Ata janë gjithashtu jashtë funksionit, kështu që ne të bie në ujdi ata dhe ne shtoni 1 me swap banak. 54 00:02:24,920 --> 00:02:26,230 >> Tani vini re se çfarë ka ndodhur. 55 00:02:26,230 --> 00:02:29,514 Ne kemi lëvizur 6 gjithë rrugës deri në fund. 56 00:02:29,514 --> 00:02:32,180 Pra, në përzgjedhjes lloj, në qoftë se ju keni shihet se video, ajo që ne e bëmë ishte 57 00:02:32,180 --> 00:02:35,290 ne përfundoi duke lëvizur Elementet më të vogla në ndërtesë 58 00:02:35,290 --> 00:02:39,640 array renditura në thelb nga majta në të djathtë, më të vogël për të më e madhe. 59 00:02:39,640 --> 00:02:43,200 Në rastin e flluskë lloji, në qoftë se ne jemi pas këtij algoritmi të veçantë, 60 00:02:43,200 --> 00:02:46,720 ne jemi të vërtetë do të jetë ndërtimi array renditura nga e djathta 61 00:02:46,720 --> 00:02:49,100 në të majtë, më i madh për të vogël. 62 00:02:49,100 --> 00:02:53,840 Ne kemi bubbled efektive 6, vlera më e madhe, gjatë gjithë rrugës deri në fund. 63 00:02:53,840 --> 00:02:56,165 >> Dhe kështu që ne tani mund të deklarojë se kjo është e renditura, 64 00:02:56,165 --> 00:02:59,130 dhe në të ardhmen iterations-- shkuar nëpër rrjet again-- 65 00:02:59,130 --> 00:03:01,280 ne nuk duhet të marrin në konsideratë 6 më. 66 00:03:01,280 --> 00:03:03,850 Ne vetëm duhet të marrin në konsideratë elementet Unsorted 67 00:03:03,850 --> 00:03:06,299 kur ne jemi duke kërkuar në çifte ngjitur. 68 00:03:06,299 --> 00:03:08,340 Pra, ne kemi përfunduar një kalojnë nëpër flluskë lloj. 69 00:03:08,340 --> 00:03:11,941 Deri tani ne kthehemi në pyetjen: përsëris deri swap counter është 0. 70 00:03:11,941 --> 00:03:13,690 Well swap counter është 4, kështu që ne jemi duke shkuar 71 00:03:13,690 --> 00:03:15,410 për ta mbajtur përsëritur këtë proces përsëri. 72 00:03:15,410 --> 00:03:19,180 >> Ne jemi duke shkuar për të rivendosur swap counter në 0, dhe të kërkoni në çdo palë ngjitur. 73 00:03:19,180 --> 00:03:21,890 Pra, ne fillojmë me 2 dhe 1-- ata janë jashtë funksionit, kështu që ne të bie në ujdi tyre 74 00:03:21,890 --> 00:03:23,620 dhe ne shtoni 1 me swap banak. 75 00:03:23,620 --> 00:03:25,490 2 dhe 3, ata janë në rregull. 76 00:03:25,490 --> 00:03:27,060 Ne nuk kemi nevojë të bëni asgjë. 77 00:03:27,060 --> 00:03:28,420 3 dhe 5 janë në rregull. 78 00:03:28,420 --> 00:03:30,150 Ne nuk kemi nevojë të bëjë asgjë atje. 79 00:03:30,150 --> 00:03:32,515 >> 5 dhe 4, ata janë jashtë e rendit, dhe kështu që ne 80 00:03:32,515 --> 00:03:35,130 duhet të bie në ujdi tyre dhe shtoni 1 në swap banak. 81 00:03:35,130 --> 00:03:38,880 Dhe tani ne kemi lëvizur 5, elementi tjetër më i madh, 82 00:03:38,880 --> 00:03:40,920 në fund të pjesës pandara. 83 00:03:40,920 --> 00:03:44,360 Pra, ne tani mund të telefononi atë një pjesë e pjesës së renditura. 84 00:03:44,360 --> 00:03:47,180 >> Tani ju jeni duke kërkuar në ekran dhe ndoshta mund të them, 85 00:03:47,180 --> 00:03:50,130 si mund unë, se array është e renditura tani. 86 00:03:50,130 --> 00:03:51,820 Por ne nuk mund të provojë se ende. 87 00:03:51,820 --> 00:03:54,359 Ne nuk kemi një garanci se është e renditura. 88 00:03:54,359 --> 00:03:56,900 Por, ky është vendi ku swap counter do të hyjë në lojë. 89 00:03:56,900 --> 00:03:59,060 >> Pra, ne kemi përfunduar një abone. 90 00:03:59,060 --> 00:04:00,357 Swap counter është 2. 91 00:04:00,357 --> 00:04:02,190 Pra, ne jemi duke shkuar për të përsëritur ky proces përsëri, 92 00:04:02,190 --> 00:04:04,290 përsëris deri swap counter është 0. 93 00:04:04,290 --> 00:04:05,550 Reset swap counter në 0. 94 00:04:05,550 --> 00:04:06,820 Pra, ne do të rivendosur atë. 95 00:04:06,820 --> 00:04:09,810 >> Tani shikoni në çdo palë ngjitur. 96 00:04:09,810 --> 00:04:11,880 Kjo është në rregull, 1 dhe 2. 97 00:04:11,880 --> 00:04:13,590 2 dhe 3, janë në mënyrë të. 98 00:04:13,590 --> 00:04:15,010 3 dhe 4 janë në mënyrë të. 99 00:04:15,010 --> 00:04:19,250 Pra, në këtë pikë, vini re ne kemi përfunduar duke kërkuar në çdo palë ngjitur, 100 00:04:19,250 --> 00:04:22,530 por swap counter është ende 0. 101 00:04:22,530 --> 00:04:25,520 >> Në qoftë se ne nuk kemi për të kaluar Çdo elemente, atëherë ata 102 00:04:25,520 --> 00:04:28,340 duhet të jetë në rregull, nga virtyt i këtij procesi. 103 00:04:28,340 --> 00:04:32,000 Dhe kështu një efikasitet në terezi, se shkencëtarët kompjuterike ne dashuri, 104 00:04:32,000 --> 00:04:35,560 është ne tani mund të deklarojë të gjithë grup duhet 105 00:04:35,560 --> 00:04:38,160 të ndahen, sepse ne nuk e bëmë duhet të bie në ujdi asnjë element. 106 00:04:38,160 --> 00:04:40,380 Kjo është shumë e bukur. 107 00:04:40,380 --> 00:04:43,260 >> Pra, çfarë është rasti më i keq Skenari me flluskë lloj? 108 00:04:43,260 --> 00:04:46,240 Në rastin më të keq array është në mënyrë krejtësisht të kundërt, 109 00:04:46,240 --> 00:04:49,870 dhe kështu që ne duhet të flluskë çdo e elementeve të mëdha të gjithë 110 00:04:49,870 --> 00:04:51,780 rruga nëpër rrjet. 111 00:04:51,780 --> 00:04:55,350 Dhe ne në mënyrë efektive gjithashtu duhet të flluskë të gjitha elementet të vogla mbrapa 112 00:04:55,350 --> 00:04:57,050 të gjithë rrugën nëpër rrjet, too. 113 00:04:57,050 --> 00:05:01,950 Kështu që secili prej elementeve n ka për të lëvizur nëpër të gjitha elementet e tjera n. 114 00:05:01,950 --> 00:05:04,102 Pra, kjo është skenari më i keq. 115 00:05:04,102 --> 00:05:05,810 Në rastin më të mirë skenar edhe pse, kjo është 116 00:05:05,810 --> 00:05:07,880 paksa e ndryshme nga përzgjedhjes lloji. 117 00:05:07,880 --> 00:05:10,040 Array është tashmë renditura kur të shkojmë në. 118 00:05:10,040 --> 00:05:12,550 Ne nuk duhet të bëjë ndonjë këmbime në kalimin e parë. 119 00:05:12,550 --> 00:05:14,940 Pra, ne mund të duhet të shikojmë në më pak elemente, e drejtë? 120 00:05:14,940 --> 00:05:18,580 Ne nuk kemi për të përsëritur këtë procesin disa herë gjatë. 121 00:05:18,580 --> 00:05:19,540 >> Pra, çfarë do të thotë kjo? 122 00:05:19,540 --> 00:05:22,390 Pra, çfarë është skenari më i keq për flluskë lloj, dhe çfarë është 123 00:05:22,390 --> 00:05:25,330 skenari më i mirë për flluskë lloj? 124 00:05:25,330 --> 00:05:27,770 A ju me mend kjo? 125 00:05:27,770 --> 00:05:32,420 Në rastin më të keq se ju keni për të iterate në të gjitha elementet e n n herë. 126 00:05:32,420 --> 00:05:34,220 Pra, rasti më i keq është katror n. 127 00:05:34,220 --> 00:05:36,550 >> Nëse array është krejtësisht renditura edhe pse, ju vetëm 128 00:05:36,550 --> 00:05:38,580 duhet të shikoni në çdo e elementeve të njëjtën kohë. 129 00:05:38,580 --> 00:05:42,670 Dhe në qoftë se swap counter është ende 0, ju mund të them këtë grup është e renditura. 130 00:05:42,670 --> 00:05:45,780 Dhe kështu në rastin më të mirë, kjo është në fakt më mirë se përzgjedhja 131 00:05:45,780 --> 00:05:49,230 sort-- është omega e n. 132 00:05:49,230 --> 00:05:50,270 >> Unë jam Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Kjo është CS50. 134 00:05:52,140 --> 00:05:54,382