1 00:00:00,000 --> 00:00:05,760 2 00:00:05,760 --> 00:00:08,900 >> Doug Lloyd: Se konsa, nan CS50 nou te aprann enfòmasyon sou yon varyete de klasman ak chèche 3 00:00:08,900 --> 00:00:09,442 algoritm. 4 00:00:09,442 --> 00:00:11,400 Epi pafwa li kapab yon ti kras difisil kenbe 5 00:00:11,400 --> 00:00:14,161 tras nan sa ki algorithm fè sa. 6 00:00:14,161 --> 00:00:15,910 Nou te reyèlman sèlman ekreme sifas la tou, 7 00:00:15,910 --> 00:00:18,740 gen anpil lòt chache ak klasman algoritm. 8 00:00:18,740 --> 00:00:21,780 Se konsa, nan videyo sa a se pou yo jis pran yon kèk minit 9 00:00:21,780 --> 00:00:24,980 eseye ak distile chak algorithm desann nan eleman nwayo li 10 00:00:24,980 --> 00:00:27,810 se konsa ou ka sonje pi plis nan enfòmasyon enpòtan sou yo 11 00:00:27,810 --> 00:00:31,970 epi yo dwe kapab articuler a diferans ki genyen, si sa nesesè. 12 00:00:31,970 --> 00:00:34,220 >> Premye a se sòt seleksyon. 13 00:00:34,220 --> 00:00:38,210 Lide a debaz dèyè sòt seleksyon se jwenn pi piti eleman ki klase 14 00:00:38,210 --> 00:00:42,890 nan yon etalaj ak swap l 'ak nan premye eleman triye nan ki etalaj. 15 00:00:42,890 --> 00:00:46,620 Nou te di ke pi move-ka a te kouri lè nan ki n okib. 16 00:00:46,620 --> 00:00:50,060 Men, si ou vle sonje poukisa, pran yon gade nan videyo a sòt seleksyon. 17 00:00:50,060 --> 00:00:54,560 Pi bon-ka nan kouri tan se tou n okib. 18 00:00:54,560 --> 00:00:58,910 >> Sòt jarèt, lide a dèyè ki se yon sèl swap pè adjasan. 19 00:00:58,910 --> 00:01:01,730 Se konsa, sa a, se kle a ki ede ou sonje diferans ki genyen isit la. 20 00:01:01,730 --> 00:01:04,920 Seleksyon sòt se, se twò lwen, jwenn ti wonn nan smallest-- 21 00:01:04,920 --> 00:01:06,790 sòt se swap pè adjasan. 22 00:01:06,790 --> 00:01:08,710 Nou swap pè adjasan nan eleman si yo 23 00:01:08,710 --> 00:01:12,530 yo soti nan lòd, ki efektivman bul pi gwo eleman a dwat la, 24 00:01:12,530 --> 00:01:17,060 ak nan menm tan an li tou kòmanse pou avanse pou pi pi piti eleman sou bò goch la. 25 00:01:17,060 --> 00:01:20,180 Pi move-ka Lè a ka kouri nan sòt jarèt se n okib. 26 00:01:20,180 --> 00:01:23,476 Pi bon-ka nan kouri tan nan jarèt sòt se n. 27 00:01:23,476 --> 00:01:25,350 Paske nan ke sitiyasyon nou pa aktyèlman 28 00:01:25,350 --> 00:01:27,141 nou pa ta ka bezwen fè okenn echanj nan tout. 29 00:01:27,141 --> 00:01:31,026 Nou sèlman gen fè yon sèl pase atravè tout eleman n. 30 00:01:31,026 --> 00:01:34,600 >> Nan sòt ensèsyon, nan lide debaz isit la se déplacement. 31 00:01:34,600 --> 00:01:36,630 Sa a mo kle a pou ensèsyon sòt. 32 00:01:36,630 --> 00:01:39,630 Nou pral etap yon fwa a etalaj la de gòch a dwat. 33 00:01:39,630 --> 00:01:41,670 E kòm nou fè sa, nou ap ale nan chanjman eleman 34 00:01:41,670 --> 00:01:46,260 nou te deja wè pou fè plas pou ki pi piti ki bezwen anfòm yon kote 35 00:01:46,260 --> 00:01:48,080 tounen nan ki pòsyon Ranje. 36 00:01:48,080 --> 00:01:51,600 Se konsa, nou bati etalaj la Ranje youn eleman nan yon moman, gòch a dwat, 37 00:01:51,600 --> 00:01:54,740 epi nou chanjman bagay sa yo fè plas. 38 00:01:54,740 --> 00:01:58,650 Pi move-ka Lè a kouri nan se sòt ensèsyon n okib. 39 00:01:58,650 --> 00:02:02,380 Pi bon-ka kouri tan an se n. 40 00:02:02,380 --> 00:02:05,380 >> Rantre sort-- mo kle a isit la se fann ak plonje. 41 00:02:05,380 --> 00:02:08,949 Nou fann etalaj la plen, si wi ou non li nan sis eleman, uit eleman, 42 00:02:08,949 --> 00:02:13,790 10,000 elements-- nou fann li desann nan mwatye, pa mwatye, pa mwatye, 43 00:02:13,790 --> 00:02:17,720 jiskaske nou gen anba etalaj nan n yon sèl ranje eleman. 44 00:02:17,720 --> 00:02:19,470 Yon seri n youn ranje eleman. 45 00:02:19,470 --> 00:02:22,640 Se konsa, nou te kòmanse ak yon sèl Etalaj 1,000-eleman, 46 00:02:22,640 --> 00:02:26,550 e nou jwenn nan pwen kote nou gen 1,000 ranje yon sèl-eleman. 47 00:02:26,550 --> 00:02:30,990 Lè sa a, nou kòmanse rantre moun ranje sub tounen ansanm yo nan lòd ki kòrèk la. 48 00:02:30,990 --> 00:02:34,860 Se konsa, nou pran de ranje yon sèl-eleman ak kreye yon etalaj de-eleman. 49 00:02:34,860 --> 00:02:38,180 Nou pran de ranje de-eleman ak kreye yon etalaj kat-eleman 50 00:02:38,180 --> 00:02:43,900 ak sou sa ak sou sa jiskaske nou te ankò rebati yon sèl etalaj eleman n. 51 00:02:43,900 --> 00:02:48,410 >> Pi move-ka Lè a kouri nan rantre sòt se n fwa boutèy demi lit n. 52 00:02:48,410 --> 00:02:52,390 Nou gen eleman n, men pwosesis sa a rekombinezon 53 00:02:52,390 --> 00:02:56,960 pran boutèy demi lit n etap sa yo jwenn tounen nan yon etalaj plen. 54 00:02:56,960 --> 00:03:01,160 Ka a pi bon kouri tan se tou boutèy demi lit n N paske pwosesis sa a pa fè sa vrèman 55 00:03:01,160 --> 00:03:04,090 swen si wi ou non etalaj la te Ranje oswa ou pa yo kòmanse avèk yo. 56 00:03:04,090 --> 00:03:07,590 Pwosesis sa a se menm bagay la tou, gen nan okenn fason yo bagay sikwi kout. 57 00:03:07,590 --> 00:03:11,610 Se konsa, n boutèy demi lit n nan ka ki pi mal la, N boutèy demi lit n nan ka a pi byen. 58 00:03:11,610 --> 00:03:13,960 >> Nou te pale de de chèche algoritm. 59 00:03:13,960 --> 00:03:16,230 Se konsa, rechèch lineyè se sou iteration. 60 00:03:16,230 --> 00:03:19,500 Nou kontinye atravè etalaj la yon fwa, de gòch a dwat, 61 00:03:19,500 --> 00:03:21,950 ap eseye jwenn nimewo a ke nou ap chèche pou. 62 00:03:21,950 --> 00:03:24,550 Lè a pi move-ka kouri se gwo O nan n. 63 00:03:24,550 --> 00:03:27,610 Li ta ka pran nou iteration atravè chak eleman yon sèl 64 00:03:27,610 --> 00:03:30,660 jwenn eleman nan nou ap chèche pou, swa nan yon pozisyon nan dènye a, 65 00:03:30,660 --> 00:03:31,630 oswa ou pa nan tout. 66 00:03:31,630 --> 00:03:34,720 Men, nou pa ka konfime ke jiskaske nou te gade tout bagay. 67 00:03:34,720 --> 00:03:36,730 m pi byen ki ka a, nou jwenn imedyatman. 68 00:03:36,730 --> 00:03:41,060 Pi bon-ka Lè a kouri nan rechèch lineyè se Omega nan 1. 69 00:03:41,060 --> 00:03:43,689 >> Anfen, te gen binè rechèch, ki mande pou asòti etalaj. 70 00:03:43,689 --> 00:03:45,605 Sonje sa a, se yon trè konsiderasyon enpòtan 71 00:03:45,605 --> 00:03:47,155 lè w ap travay ak rechèch binè. 72 00:03:47,155 --> 00:03:50,180 Li se yon avantou lè l sèvi avèk l-- etalaj la ke ou ap chèche a 73 00:03:50,180 --> 00:03:52,160 dwe Ranje. 74 00:03:52,160 --> 00:03:54,500 Sinon, mo kle a se separe ak konkeri. 75 00:03:54,500 --> 00:03:58,310 Pataje etalaj la nan mwatye ak elimine mwatye nan eleman yo 76 00:03:58,310 --> 00:04:00,780 chak fwa jan ou kontinye nan. 77 00:04:00,780 --> 00:04:04,330 Paske nan sa a epi divize konkeri ak bagay sa yo divize an mwatye apwòch, 78 00:04:04,330 --> 00:04:07,450 tan an kouri pi move-ka nan binè rechèch la se 79 00:04:07,450 --> 00:04:11,730 boutèy demi lit n, ki se anpil pi bon pase n rechèch lineyè a. 80 00:04:11,730 --> 00:04:13,570 Pi bon-ka kouri Lè a se toujou yon sèl. 81 00:04:13,570 --> 00:04:17,010 >> Nou ta ka jwenn li imedyatman nan premye fwa nou fè yon divizyon, men, 82 00:04:17,010 --> 00:04:19,339 ankò, sonje ke byenke rechèch binè se 83 00:04:19,339 --> 00:04:24,030 anpil pi bon pase rechèch lineyè pa vèti nan yo te louvri sesyon n kont n, 84 00:04:24,030 --> 00:04:27,110 ou ta ka gen yo ale nan travay nan a klasman etalaj ou premye, ki 85 00:04:27,110 --> 00:04:32,010 ta ka fè li mwens efikas depann sou gwosè a nan iteration nan Ranje. 86 00:04:32,010 --> 00:04:35,250 >> Mwen se Doug Lloyd, sa a se CS50. 87 00:04:35,250 --> 00:04:36,757