1 00:00:00,000 --> 00:00:03,360 >> [TÓNLIST spila] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 DOUG LLOYD: Allt í lagi, svo kúla tegund er reiknirit 4 00:00:06,730 --> 00:00:08,730 þú getur notað til að raða safn af þáttum. 5 00:00:08,730 --> 00:00:10,850 Við skulum taka a líta á hvernig það virkar. 6 00:00:10,850 --> 00:00:13,240 >> Meginhugmyndin að baki kúla tegund er þetta. 7 00:00:13,240 --> 00:00:17,340 Við viljum almennt að færa hærra metin þættir yfirleitt til hægri, 8 00:00:17,340 --> 00:00:20,340 og lækka metin þætti almennt til vinstri, eins og við búast. 9 00:00:20,340 --> 00:00:23,256 Við viljum lægri hlutir að vera á upphaf og hærri hluti 10 00:00:23,256 --> 00:00:24,970 að vera í lokin. 11 00:00:24,970 --> 00:00:26,130 >> Hvernig gerum við þetta? 12 00:00:26,130 --> 00:00:28,040 Jæja í sauðakóða kóða, við gætum sagt, við skulum 13 00:00:28,040 --> 00:00:30,320 setja skiptasamning borðið til a non-núll gildi. 14 00:00:30,320 --> 00:00:32,570 Við munum sjá hvers vegna við gerum það í annað. 15 00:00:32,570 --> 00:00:36,090 Og þá erum við að endurtaka eftirfarandi ferli þar til skipti borðið er 0, 16 00:00:36,090 --> 00:00:39,910 eða þar til við tökum enga skiptasamninga yfirleitt. 17 00:00:39,910 --> 00:00:43,170 >> Endurstilla skipti í bága við 0 ef það er ekki nú þegar 0. 18 00:00:43,170 --> 00:00:46,420 Þá líta á hvert par af samliggjandi þáttum. 19 00:00:46,420 --> 00:00:49,550 Ef þessir tveir þættir eru ekki í röð, skipta þeim, 20 00:00:49,550 --> 00:00:51,620 og bæta 1 til skiptasamnings borðið. 21 00:00:51,620 --> 00:00:53,870 Ef þú ert að hugsa um þetta áður en þú sjón það, 22 00:00:53,870 --> 00:00:57,471 eftir því að þetta mun færa lægri metin þættir vinstra 23 00:00:57,471 --> 00:01:00,720 og hærra metin þætti til hægri, í raun að gera það sem við viljum gera, 24 00:01:00,720 --> 00:01:03,940 sem er að fara að þeim hópum staka í þannig. 25 00:01:03,940 --> 00:01:07,035 Við skulum sjón hvernig þetta getur litið með array okkar 26 00:01:07,035 --> 00:01:10,504 sem við notuðum til að prófa út þessum reiknirit. 27 00:01:10,504 --> 00:01:13,420 Við höfum óflokkuðu array hér aftur, gefið til kynna með alla þá þætti 28 00:01:13,420 --> 00:01:14,840 vera í rauðu. 29 00:01:14,840 --> 00:01:17,970 Og ég setti minn swap gegn til frábrugðnar núlli gildi. 30 00:01:17,970 --> 00:01:20,610 Ég valdi geðþótta neikvæð 1-- það er ekki 0. 31 00:01:20,610 --> 00:01:23,840 Við viljum að endurtaka þetta ferli þar til skipti borðið er 0. 32 00:01:23,840 --> 00:01:26,540 Þetta er ástæða þess að ég setti skipti mitt gegn að sumir non-núll gildi, 33 00:01:26,540 --> 00:01:29,400 því annars skipti gegn væri 0. 34 00:01:29,400 --> 00:01:31,610 Við viljum ekki einu sinni að byrja að ferli reiknirit. 35 00:01:31,610 --> 00:01:33,610 Svo aftur, are-- skrefin núllstilla skipti gegn 36 00:01:33,610 --> 00:01:37,900 0, þá líta á hvert við hliðina par, og ef þeir eru út af röð, 37 00:01:37,900 --> 00:01:40,514 skipta á þeim og bæta 1 að skipti borðið. 38 00:01:40,514 --> 00:01:41,680 Svo skulum byrja þetta ferli. 39 00:01:41,680 --> 00:01:44,430 Svo er það fyrsta sem við gerum við setjum skipti gegn 0, 40 00:01:44,430 --> 00:01:46,660 og þá erum við að byrja að leita á hvers aðlægs pars. 41 00:01:46,660 --> 00:01:49,140 >> Svo við byrjum fyrst að horfa á 5 og 2. 42 00:01:49,140 --> 00:01:52,410 Sjáum við að þeir eru út af panta og svo við skipta þeim. 43 00:01:52,410 --> 00:01:53,830 Og við bætum 1 við skipti borðið. 44 00:01:53,830 --> 00:01:57,860 Svo nú er að skipta gegn okkar 1, og 2 og 5 hefur verið skipt. 45 00:01:57,860 --> 00:01:59,370 Nú erum við að endurtaka ferlið aftur. 46 00:01:59,370 --> 00:02:03,540 >> Við lítum á næsta aðliggjandi par, 5 og 1-- þeir eru líka út af röð, 47 00:02:03,540 --> 00:02:06,960 svo við skipta á þeim og bæta 1 við skipti borðið. 48 00:02:06,960 --> 00:02:08,900 Þá við skoðum 5 og 3. 49 00:02:08,900 --> 00:02:13,830 Þeir eru í ólagi, svo við skipta þá og við bætum 1 við skipti borðið. 50 00:02:13,830 --> 00:02:15,550 Þá við skoðum 5 og 6. 51 00:02:15,550 --> 00:02:18,630 Þeir eru til, svo við gerum ekki raunverulega þarf að skipta neitt að þessu sinni. 52 00:02:18,630 --> 00:02:20,250 Þá við skoðum 6 og 4. 53 00:02:20,250 --> 00:02:24,920 Þeir eru einnig í ólagi, svo við skipta þá og við bætum 1 við skipti borðið. 54 00:02:24,920 --> 00:02:26,230 >> Nú eftir hvað gerðist. 55 00:02:26,230 --> 00:02:29,514 Við höfum flutt 6 alla leið til enda. 56 00:02:29,514 --> 00:02:32,180 Svo í val tagi, ef þú hefur séð að video, það sem við gerðum var 57 00:02:32,180 --> 00:02:35,290 við enduðum hreyfa Minnsta þættir í húsinu 58 00:02:35,290 --> 00:02:39,640 raðaða array meginatriðum frá vinstri til hægri, smæstu til stærstu. 59 00:02:39,640 --> 00:02:43,200 Í tilviki kúla tagi, ef við erum Eftirfarandi þessari tilteknu reiknirit, 60 00:02:43,200 --> 00:02:46,720 við erum í raun að fara að vera að byggja raðaða array frá hægri 61 00:02:46,720 --> 00:02:49,100 til vinstri, stærsta til minnsta. 62 00:02:49,100 --> 00:02:53,840 Við höfum í raun fara í loftbólum í 6, sem eru Stærsta gildi, alla leið til enda. 63 00:02:53,840 --> 00:02:56,165 >> Og svo við getum nú lýsa að það er raðað, 64 00:02:56,165 --> 00:02:59,130 og í framtíðinni iterations-- fara í gegnum array again-- 65 00:02:59,130 --> 00:03:01,280 við þurfum ekki að huga 6 lengur. 66 00:03:01,280 --> 00:03:03,850 Við þurfum aðeins að íhuga að óflokkaðar þættir 67 00:03:03,850 --> 00:03:06,299 þegar við erum að horfa á aðliggjandi pör. 68 00:03:06,299 --> 00:03:08,340 Þannig að við höfum lokið einu fara í gegnum kúla tagi. 69 00:03:08,340 --> 00:03:11,941 Svo nú erum við að fara aftur að spurningunni, Endurtakið þar til skipti teljarinn er 0. 70 00:03:11,941 --> 00:03:13,690 Jæja skipti gegn er 4, þannig að við erum að fara 71 00:03:13,690 --> 00:03:15,410 að halda að endurtaka þetta ferli aftur. 72 00:03:15,410 --> 00:03:19,180 >> Við erum að fara að núllstilla skipti gegn 0, og líta á hvern aðliggjandi par. 73 00:03:19,180 --> 00:03:21,890 Svo við byrjum með 2 og 1-- þeir eru út af röð, þannig að við skipta þeim 74 00:03:21,890 --> 00:03:23,620 og við bætum 1 við skipti borðið. 75 00:03:23,620 --> 00:03:25,490 2 og 3, þá eru þeir í röð. 76 00:03:25,490 --> 00:03:27,060 Við þurfum ekki að gera neitt. 77 00:03:27,060 --> 00:03:28,420 3 og 5 eru í röð. 78 00:03:28,420 --> 00:03:30,150 Við þurfum ekki að gera neitt þar. 79 00:03:30,150 --> 00:03:32,515 >> 5 og 4, eru þeir út þess, og svo við 80 00:03:32,515 --> 00:03:35,130 þarf að skipta á þeim og bæta 1 við skipti borðið. 81 00:03:35,130 --> 00:03:38,880 Og nú höfum við flutt 5, Næst stærsti þáttur, 82 00:03:38,880 --> 00:03:40,920 til loka óflokkaðs hluta. 83 00:03:40,920 --> 00:03:44,360 Svo við getum nú kalla það hluti af röðuðu hluta. 84 00:03:44,360 --> 00:03:47,180 >> Nú þú ert að horfa á skjár og sennilega getur sagt, 85 00:03:47,180 --> 00:03:50,130 eins get ég, að í fylkinu er raðað núna. 86 00:03:50,130 --> 00:03:51,820 En við getum ekki sannað það enn. 87 00:03:51,820 --> 00:03:54,359 Við höfum ekki trygging að það er flokkað. 88 00:03:54,359 --> 00:03:56,900 En þetta er þar sem skipti gegn er að fara að koma inn í leik. 89 00:03:56,900 --> 00:03:59,060 >> Þannig að við höfum lokið framhjá. 90 00:03:59,060 --> 00:04:00,357 Skiptigengi Teljarinn er 2. 91 00:04:00,357 --> 00:04:02,190 Þannig að við erum að fara að endurtaka þetta ferli aftur, 92 00:04:02,190 --> 00:04:04,290 Endurtakið þar til skipti teljarinn er 0. 93 00:04:04,290 --> 00:04:05,550 Núllstilla skipti gegn 0. 94 00:04:05,550 --> 00:04:06,820 Þannig að við munum endurstilla það. 95 00:04:06,820 --> 00:04:09,810 >> Nú líta á hvern aðliggjandi par. 96 00:04:09,810 --> 00:04:11,880 Það er til, 1 og 2. 97 00:04:11,880 --> 00:04:13,590 2 og 3 eru í röð. 98 00:04:13,590 --> 00:04:15,010 3 og 4 eru í röð. 99 00:04:15,010 --> 00:04:19,250 Svo á þessum tímapunkti, eftir að við höfum lokið leita á öllum aðliggjandi par, 100 00:04:19,250 --> 00:04:22,530 en skipti borðið er enn 0. 101 00:04:22,530 --> 00:04:25,520 >> Ef við þurfum ekki að skipta allir þættir, þá 102 00:04:25,520 --> 00:04:28,340 verður að vera í röð, eftir samkvæmt þessari aðferð. 103 00:04:28,340 --> 00:04:32,000 Og svo að skilvirkni konar, að við tölvunarfræðingar elska, 104 00:04:32,000 --> 00:04:35,560 er að við getum nú lýsa Fylkið verður 105 00:04:35,560 --> 00:04:38,160 vera flokkaður, vegna þess að við gerðum ekki að skipta þá hluta. 106 00:04:38,160 --> 00:04:40,380 Það er nokkuð gott. 107 00:04:40,380 --> 00:04:43,260 >> Svo er það versta dæmi með kúla tegund? 108 00:04:43,260 --> 00:04:46,240 Í versta tilfelli fylki er í alveg öfugri röð, 109 00:04:46,240 --> 00:04:49,870 og svo við verðum að kúla hver af stórum þáttum allt 110 00:04:49,870 --> 00:04:51,780 leið yfir fylkisins. 111 00:04:51,780 --> 00:04:55,350 Og við í raun einnig að kúla alla þá litlum þætti til baka 112 00:04:55,350 --> 00:04:57,050 alla leið yfir í fylkinu, líka. 113 00:04:57,050 --> 00:05:01,950 Svo hvert N þætti þarf að færa yfir alla aðra þætti n. 114 00:05:01,950 --> 00:05:04,102 Svo er það versta falli. 115 00:05:04,102 --> 00:05:05,810 Í besta tilfelli dæmi þó, þetta er 116 00:05:05,810 --> 00:05:07,880 örlítið frábrugðið vali tagi. 117 00:05:07,880 --> 00:05:10,040 The array er þegar flokkaður þegar við förum í. 118 00:05:10,040 --> 00:05:12,550 Við þurfum ekki að gera eitthvað skiptasamninga á fyrstu umferð. 119 00:05:12,550 --> 00:05:14,940 Þannig að við gætum þurft að líta á færri þætti, ekki satt? 120 00:05:14,940 --> 00:05:18,580 Við þurfum ekki að endurtaka þetta vinna nokkrum sinnum yfir. 121 00:05:18,580 --> 00:05:19,540 >> Svo hvað þýðir það? 122 00:05:19,540 --> 00:05:22,390 Svo er það versta falli fyrir kúla tagi, og hvað er 123 00:05:22,390 --> 00:05:25,330 Best Case atburðarás fyrir kúla tegund? 124 00:05:25,330 --> 00:05:27,770 Vissir þú giska þetta? 125 00:05:27,770 --> 00:05:32,420 Í versta tilfelli sem þú þarft að árétta yfir allar n þáttum n sinnum. 126 00:05:32,420 --> 00:05:34,220 Svo versta er n veldi. 127 00:05:34,220 --> 00:05:36,550 >> Ef array er fullkomlega Raðað þó aðeins þú 128 00:05:36,550 --> 00:05:38,580 að líta á hvert af þeim þáttum einu sinni. 129 00:05:38,580 --> 00:05:42,670 Og ef skipti borðið er enn 0, þú getur sagt þetta array er raðað. 130 00:05:42,670 --> 00:05:45,780 Og svo í besta tilfelli, þetta er í raun betri en val 131 00:05:45,780 --> 00:05:49,230 sort-- það er ómega n. 132 00:05:49,230 --> 00:05:50,270 >> Ég er Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Þetta er CS50. 134 00:05:52,140 --> 00:05:54,382