1 00:00:00,000 --> 00:00:03,360 >> [MIZIK jwe] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 Doug Lloyd: Tout dwa, se konsa sòt ti wonn se yon algorithm 4 00:00:06,730 --> 00:00:08,730 ou ka itilize yo sòt yon seri eleman. 5 00:00:08,730 --> 00:00:10,850 Se pou nou pran yon gade nan ki jan li fonksyone. 6 00:00:10,850 --> 00:00:13,240 >> Se konsa, lide a debaz dèyè sòt ti wonn se sa a. 7 00:00:13,240 --> 00:00:17,340 Nou jeneralman vle pou avanse pou pi wo valè eleman jeneralman a dwat la, 8 00:00:17,340 --> 00:00:20,340 ak pi ba valè eleman jeneralman sou bò goch la, menm jan nou ta atann. 9 00:00:20,340 --> 00:00:23,256 Nou vle bagay sa yo pi ba yo dwe nan nan konmansman an, ak bagay sa yo yo pi wo 10 00:00:23,256 --> 00:00:24,970 yo dwe nan fen an. 11 00:00:24,970 --> 00:00:26,130 >> Ki jan nou fè sa? 12 00:00:26,130 --> 00:00:28,040 Oke nan kòd pseudocode, nou te ka di, se pou yo 13 00:00:28,040 --> 00:00:30,320 mete yon vann san preskripsyon swap nan yon valè ki pa zewo. 14 00:00:30,320 --> 00:00:32,570 Nou pwal wè poukisa nou fè sa nan yon dezyèm fwa. 15 00:00:32,570 --> 00:00:36,090 Lè sa a, nou repete sa ki annapre yo pwosesis jouk kontwa an swap se 0, 16 00:00:36,090 --> 00:00:39,910 oswa jiskaske nou fè pa gen okenn echanj nan tout. 17 00:00:39,910 --> 00:00:43,170 >> Reyajiste kontwa an swap 0 si li pa deja 0. 18 00:00:43,170 --> 00:00:46,420 Lè sa a, gade nan chak pè adjasan nan eleman. 19 00:00:46,420 --> 00:00:49,550 Si sa yo de eleman yo pa nan lòd, swap yo, 20 00:00:49,550 --> 00:00:51,620 epi ajoute 1 a kontwa an swap. 21 00:00:51,620 --> 00:00:53,870 Si w ap panse sou sa a anvan ou visualized li, 22 00:00:53,870 --> 00:00:57,471 remake ke sa a ap deplase pi ba valè eleman sou bò goch la 23 00:00:57,471 --> 00:01:00,720 ak pi wo valè eleman a dwat la, efektivman fè sa nou vle fè, 24 00:01:00,720 --> 00:01:03,940 ki se deplase gwoup moun nan eleman nan fason sa a. 25 00:01:03,940 --> 00:01:07,035 Se pou nou visualized ki jan sa a ta ka gade lè l sèvi avèk etalaj nou an 26 00:01:07,035 --> 00:01:10,504 ke nou itilize li teste soti algoritm sa yo. 27 00:01:10,504 --> 00:01:13,420 Nou gen yon etalaj triye isit la ankò, endike nan tout nan eleman yo 28 00:01:13,420 --> 00:01:14,840 yo te nan wouj. 29 00:01:14,840 --> 00:01:17,970 Apre sa, mwen mete vann san preskripsyon mwen an swap nan yon valè zewo. 30 00:01:17,970 --> 00:01:20,610 Mwen te chwazi abitrèman negatif 1-- li pa 0. 31 00:01:20,610 --> 00:01:23,840 Nou vle repete pwosesis sa a jouk kontwa an swap se 0. 32 00:01:23,840 --> 00:01:26,540 Sa a se poukisa mwen mete m 'swap vann san preskripsyon nan kèk valè ki pa zewo, 33 00:01:26,540 --> 00:01:29,400 paske otreman nan swap vann san preskripsyon ta dwe 0. 34 00:01:29,400 --> 00:01:31,610 Nou pa ta ka menm kòmanse nan pwosesis pou algorithm nan. 35 00:01:31,610 --> 00:01:33,610 Se konsa, ankò, etap sa yo sont- Reyajiste kontwa an swap 36 00:01:33,610 --> 00:01:37,900 a 0, lè sa a gade nan chak adjasan pè, e si yo te ap soti nan lòd, 37 00:01:37,900 --> 00:01:40,514 swap yo, epi ajoute 1 nan kontwa an swap. 38 00:01:40,514 --> 00:01:41,680 Se konsa nou kòmanse pwosesis sa a. 39 00:01:41,680 --> 00:01:44,430 Se konsa, premye bagay la nou fè se nou mete kontwa an swap a 0, 40 00:01:44,430 --> 00:01:46,660 ak Lè sa a nou kòmanse kap nan chak pè adjasan. 41 00:01:46,660 --> 00:01:49,140 >> Se konsa, nou premye kòmanse gade nan 5 ak 2. 42 00:01:49,140 --> 00:01:52,410 Nou wè yo ke yo ap soti nan lòd ak se konsa nou boukante yo. 43 00:01:52,410 --> 00:01:53,830 Epi nou ajoute 1 nan kontwa an swap. 44 00:01:53,830 --> 00:01:57,860 Se konsa, kounye vann san preskripsyon swap nou an, se 1, ak 2 ak 5 yo te chanje. 45 00:01:57,860 --> 00:01:59,370 Koulye a, nou repete pwosesis la ankò. 46 00:01:59,370 --> 00:02:03,540 >> Nou gade nan pwochen pè a adjasan, 5 ak 1-- yo ap tou soti nan lòd, 47 00:02:03,540 --> 00:02:06,960 se konsa nou swap yo epi ajoute 1 a kontwa an swap. 48 00:02:06,960 --> 00:02:08,900 Lè sa a, nou gade nan 5 ak 3. 49 00:02:08,900 --> 00:02:13,830 Yo se soti nan lòd, se konsa nou boukante yo e yo nou ajoute 1 a kontwa an swap. 50 00:02:13,830 --> 00:02:15,550 Lè sa a, nou gade nan 5 ak 6. 51 00:02:15,550 --> 00:02:18,630 Yo ap nan lòd, se konsa nou pa fè sa aktyèlman bezwen swap anyen tan sa a. 52 00:02:18,630 --> 00:02:20,250 Lè sa a, nou gade nan 6 ak 4. 53 00:02:20,250 --> 00:02:24,920 Yo ap tou soti nan lòd, se konsa nou boukante yo e yo nou ajoute 1 a kontwa an swap. 54 00:02:24,920 --> 00:02:26,230 >> Koulye a, remake sa k te pase. 55 00:02:26,230 --> 00:02:29,514 Nou te demenaje ale rete 6 tout wout la nan fen an. 56 00:02:29,514 --> 00:02:32,180 Se konsa, nan sòt seleksyon, si ou te wè ke videyo, sa nou te fè te 57 00:02:32,180 --> 00:02:35,290 nou te fini k ap deplase nan pi piti eleman nan bilding 58 00:02:35,290 --> 00:02:39,640 etalaj la Ranje esansyèlman soti nan gòch a dwat, pi piti nan pi gwo. 59 00:02:39,640 --> 00:02:43,200 Nan ka a nan sòt jarèt, si nou ap apre sa a algorithm patikilye, 60 00:02:43,200 --> 00:02:46,720 nou ap aktyèlman pral yo dwe bati etalaj la Ranje de dwat 61 00:02:46,720 --> 00:02:49,100 sou bò goch, pi gwo pi piti. 62 00:02:49,100 --> 00:02:53,840 Nou te efektivman bul 6 an, pi gwo valè, tout wout la nan fen an. 63 00:02:53,840 --> 00:02:56,165 >> Se konsa, nou kapab kounye a deklare ki ki klase, 64 00:02:56,165 --> 00:02:59,130 ak nan fiti iterations-- ale atravè tout etalaj la again-- 65 00:02:59,130 --> 00:03:01,280 nou pa gen konsidere 6 ankò. 66 00:03:01,280 --> 00:03:03,850 Nou sèlman gen konsidere eleman ki klase 67 00:03:03,850 --> 00:03:06,299 lè nou ap chèche a pè adjasan. 68 00:03:06,299 --> 00:03:08,340 Se konsa, nou rive nan bout youn pase nan sòt jarèt. 69 00:03:08,340 --> 00:03:11,941 Se konsa, kounye a nou tounen nan kesyon an, repete jiskaske kontwa an swap se 0. 70 00:03:11,941 --> 00:03:13,690 Oke kontwa an swap se 4, se konsa nou ap ale 71 00:03:13,690 --> 00:03:15,410 kenbe repete pwosesis sa a ankò. 72 00:03:15,410 --> 00:03:19,180 >> Nou pral Reyajiste kontwa an swap a 0, ak gade nan chak pè adjasan. 73 00:03:19,180 --> 00:03:21,890 Se konsa, nou kòmanse ak 2 ak 1-- yo ap soti nan lòd, se konsa nou boukante yo 74 00:03:21,890 --> 00:03:23,620 epi nou ajoute 1 nan kontwa an swap. 75 00:03:23,620 --> 00:03:25,490 2 ak 3, yo ap nan lòd. 76 00:03:25,490 --> 00:03:27,060 Nou pa bezwen fè anyen. 77 00:03:27,060 --> 00:03:28,420 3 ak 5 se nan lòd. 78 00:03:28,420 --> 00:03:30,150 Nou pa bezwen fè anyen la. 79 00:03:30,150 --> 00:03:32,515 >> 5 ak 4 yo, yo se soti nan lòd, epi pou nou 80 00:03:32,515 --> 00:03:35,130 bezwen swap yo epi ajoute 1 a kontwa an swap. 81 00:03:35,130 --> 00:03:38,880 Epi, koulye a nou te demenaje ale rete 5, pwochen pi gwo eleman nan, 82 00:03:38,880 --> 00:03:40,920 nan fen a nan pòsyon ki klase. 83 00:03:40,920 --> 00:03:44,360 Se konsa, nou kapab kounye a rele ke yon pati nan pòsyon nan Klase. 84 00:03:44,360 --> 00:03:47,180 >> Koulye a, ou ap chèche a nan ekran ak pwobableman ka di, 85 00:03:47,180 --> 00:03:50,130 kòm kapab mwen, ki etalaj la se Klase kounye a. 86 00:03:50,130 --> 00:03:51,820 Men, nou pa ka pwouve ke ankò. 87 00:03:51,820 --> 00:03:54,359 Nou pa gen yon garanti ke li nan Ranje. 88 00:03:54,359 --> 00:03:56,900 Men, sa a se kote swap nan vann san preskripsyon k ap pase yo antre nan jwe. 89 00:03:56,900 --> 00:03:59,060 >> Se konsa, nou te ranpli yon pas. 90 00:03:59,060 --> 00:04:00,357 Kontwa an swap se 2. 91 00:04:00,357 --> 00:04:02,190 Se konsa, nou ap ale nan repete pwosesis sa a ankò, 92 00:04:02,190 --> 00:04:04,290 repete jiskaske kontwa an swap se 0. 93 00:04:04,290 --> 00:04:05,550 Reyajiste kontwa an swap a 0. 94 00:04:05,550 --> 00:04:06,820 Se konsa, nou pral Reyajiste li. 95 00:04:06,820 --> 00:04:09,810 >> Koulye a, gade nan chak pè adjasan. 96 00:04:09,810 --> 00:04:11,880 Sa a yo nan lòd, 1 ak 2. 97 00:04:11,880 --> 00:04:13,590 2 ak 3 yo se nan lòd. 98 00:04:13,590 --> 00:04:15,010 3 ak 4 yo se nan lòd. 99 00:04:15,010 --> 00:04:19,250 Se konsa, nan pwen sa a, remake nou te ranpli gade nan chak pè adjasan, 100 00:04:19,250 --> 00:04:22,530 men kontwa an swap se toujou 0. 101 00:04:22,530 --> 00:04:25,520 >> Si nou pa gen yo chanje nenpòt eleman, lè sa a yo 102 00:04:25,520 --> 00:04:28,340 dwe nan lòd, pa vèti nan pwosesis sa a. 103 00:04:28,340 --> 00:04:32,000 Se konsa, yon efikasite nan kalite, ke syantis nou òdinatè renmen, 104 00:04:32,000 --> 00:04:35,560 se nou kapab kounye a deklare etalaj la tout antye dwe 105 00:04:35,560 --> 00:04:38,160 dwe klase, paske nou pa t ' gen swap nenpòt eleman. 106 00:04:38,160 --> 00:04:40,380 Sa a trè bèl. 107 00:04:40,380 --> 00:04:43,260 >> Se konsa, sa ki nan ka ki pi mal senaryo ak sòt jarèt? 108 00:04:43,260 --> 00:04:46,240 Nan ka ki pi mal la etalaj la se nan konplètman ranvèse lòd, 109 00:04:46,240 --> 00:04:49,870 e konsa nou gen yo ti wonn chak nan eleman yo gwo tout 110 00:04:49,870 --> 00:04:51,780 wout la atravè etalaj la. 111 00:04:51,780 --> 00:04:55,350 E nou efektivman tou gen jarèt tout nan eleman yo ti tounen 112 00:04:55,350 --> 00:04:57,050 tout wout la atravè etalaj la, tou. 113 00:04:57,050 --> 00:05:01,950 Se konsa, chak nan eleman yo n gen pou avanse pou pi atravè tout nan eleman yo n lòt. 114 00:05:01,950 --> 00:05:04,102 Se konsa, sa a, se senaryo a ka pi mal la. 115 00:05:04,102 --> 00:05:05,810 Nan ka ki pi bon senaryo menm si, sa a se 116 00:05:05,810 --> 00:05:07,880 yon ti kras diferan de sòt seleksyon. 117 00:05:07,880 --> 00:05:10,040 Etalaj la se deja Ranje lè nou ale nan. 118 00:05:10,040 --> 00:05:12,550 Nou pa gen fè okenn echanj sou pas la an premye. 119 00:05:12,550 --> 00:05:14,940 Se konsa, nou ta ka gen gade a mwens eleman, dwa? 120 00:05:14,940 --> 00:05:18,580 Nou pa gen yo repete sa a travay sou yon kantite fwa sou. 121 00:05:18,580 --> 00:05:19,540 >> Se konsa, sa sa vle di? 122 00:05:19,540 --> 00:05:22,390 Se konsa, sa ki nan senaryo a ka pi move pou sòt jarèt, ak sa ki nan 123 00:05:22,390 --> 00:05:25,330 senaryo a ka pi bon pou sòt jarèt? 124 00:05:25,330 --> 00:05:27,770 Èske w te devine sa a? 125 00:05:27,770 --> 00:05:32,420 Nan ka ki pi mal la ou gen yo repekte atravè tout eleman ki n n fwa. 126 00:05:32,420 --> 00:05:34,220 Se konsa, se ka ki pi mal n okib. 127 00:05:34,220 --> 00:05:36,550 >> Si etalaj la se parfe Ranje menm si, ou sèlman 128 00:05:36,550 --> 00:05:38,580 gen fè yon gade nan chak nan eleman yo yon fwa. 129 00:05:38,580 --> 00:05:42,670 Men, si kontwa an swap se toujou 0, ou ka di se sa a etalaj Ranje. 130 00:05:42,670 --> 00:05:45,780 Se konsa, nan ka ki pi bon, sa a se aktyèlman pi bon pase seleksyon 131 00:05:45,780 --> 00:05:49,230 sort-- li nan Omega nan n. 132 00:05:49,230 --> 00:05:50,270 >> Mwen se Doug Lloyd. 133 00:05:50,270 --> 00:05:52,140 Sa a se CS50. 134 00:05:52,140 --> 00:05:54,382