>> Doug Lloyd: Se konsa, nan CS50 nou te aprann enfòmasyon sou yon varyete de klasman ak chèche
algoritm.
Epi pafwa li kapab yon ti kras difisil kenbe
tras nan sa ki algorithm fè sa.
Nou te reyèlman sèlman ekreme sifas la tou,
gen anpil lòt chache ak klasman algoritm.
Se konsa, nan videyo sa a se pou yo jis pran yon kèk minit
eseye ak distile chak algorithm desann nan eleman nwayo li
se konsa ou ka sonje pi plis nan enfòmasyon enpòtan sou yo
epi yo dwe kapab articuler a diferans ki genyen, si sa nesesè.
>> Premye a se sòt seleksyon.
Lide a debaz dèyè sòt seleksyon se jwenn pi piti eleman ki klase
nan yon etalaj ak swap l 'ak nan premye eleman triye nan ki etalaj.
Nou te di ke pi move-ka a te kouri lè nan ki n okib.
Men, si ou vle sonje poukisa, pran yon gade nan videyo a sòt seleksyon.
Pi bon-ka nan kouri tan se tou n okib.
>> Sòt jarèt, lide a dèyè ki se yon sèl swap pè adjasan.
Se konsa, sa a, se kle a ki ede ou sonje diferans ki genyen isit la.
Seleksyon sòt se, se twò lwen, jwenn ti wonn nan smallest--
sòt se swap pè adjasan.
Nou swap pè adjasan nan eleman si yo
yo soti nan lòd, ki efektivman bul pi gwo eleman a dwat la,
ak nan menm tan an li tou kòmanse pou avanse pou pi pi piti eleman sou bò goch la.
Pi move-ka Lè a ka kouri nan sòt jarèt se n okib.
Pi bon-ka nan kouri tan nan jarèt sòt se n.
Paske nan ke sitiyasyon nou pa aktyèlman
nou pa ta ka bezwen fè okenn echanj nan tout.
Nou sèlman gen fè yon sèl pase atravè tout eleman n.
>> Nan sòt ensèsyon, nan lide debaz isit la se déplacement.
Sa a mo kle a pou ensèsyon sòt.
Nou pral etap yon fwa a etalaj la de gòch a dwat.
E kòm nou fè sa, nou ap ale nan chanjman eleman
nou te deja wè pou fè plas pou ki pi piti ki bezwen anfòm yon kote
tounen nan ki pòsyon Ranje.
Se konsa, nou bati etalaj la Ranje youn eleman nan yon moman, gòch a dwat,
epi nou chanjman bagay sa yo fè plas.
Pi move-ka Lè a kouri nan se sòt ensèsyon n okib.
Pi bon-ka kouri tan an se n.
>> Rantre sort-- mo kle a isit la se fann ak plonje.
Nou fann etalaj la plen, si wi ou non li nan sis eleman, uit eleman,
10,000 elements-- nou fann li desann nan mwatye, pa mwatye, pa mwatye,
jiskaske nou gen anba etalaj nan n yon sèl ranje eleman.
Yon seri n youn ranje eleman.
Se konsa, nou te kòmanse ak yon sèl Etalaj 1,000-eleman,
e nou jwenn nan pwen kote nou gen 1,000 ranje yon sèl-eleman.
Lè sa a, nou kòmanse rantre moun ranje sub tounen ansanm yo nan lòd ki kòrèk la.
Se konsa, nou pran de ranje yon sèl-eleman ak kreye yon etalaj de-eleman.
Nou pran de ranje de-eleman ak kreye yon etalaj kat-eleman
ak sou sa ak sou sa jiskaske nou te ankò rebati yon sèl etalaj eleman n.
>> Pi move-ka Lè a kouri nan rantre sòt se n fwa boutèy demi lit n.
Nou gen eleman n, men pwosesis sa a rekombinezon
pran boutèy demi lit n etap sa yo jwenn tounen nan yon etalaj plen.
Ka a pi bon kouri tan se tou boutèy demi lit n N paske pwosesis sa a pa fè sa vrèman
swen si wi ou non etalaj la te Ranje oswa ou pa yo kòmanse avèk yo.
Pwosesis sa a se menm bagay la tou, gen nan okenn fason yo bagay sikwi kout.
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.
>> Nou te pale de de chèche algoritm.
Se konsa, rechèch lineyè se sou iteration.
Nou kontinye atravè etalaj la yon fwa, de gòch a dwat,
ap eseye jwenn nimewo a ke nou ap chèche pou.
Lè a pi move-ka kouri se gwo O nan n.
Li ta ka pran nou iteration atravè chak eleman yon sèl
jwenn eleman nan nou ap chèche pou, swa nan yon pozisyon nan dènye a,
oswa ou pa nan tout.
Men, nou pa ka konfime ke jiskaske nou te gade tout bagay.
m pi byen ki ka a, nou jwenn imedyatman.
Pi bon-ka Lè a kouri nan rechèch lineyè se Omega nan 1.
>> Anfen, te gen binè rechèch, ki mande pou asòti etalaj.
Sonje sa a, se yon trè konsiderasyon enpòtan
lè w ap travay ak rechèch binè.
Li se yon avantou lè l sèvi avèk l-- etalaj la ke ou ap chèche a
dwe Ranje.
Sinon, mo kle a se separe ak konkeri.
Pataje etalaj la nan mwatye ak elimine mwatye nan eleman yo
chak fwa jan ou kontinye nan.
Paske nan sa a epi divize konkeri ak bagay sa yo divize an mwatye apwòch,
tan an kouri pi move-ka nan binè rechèch la se
boutèy demi lit n, ki se anpil pi bon pase n rechèch lineyè a.
Pi bon-ka kouri Lè a se toujou yon sèl.
>> Nou ta ka jwenn li imedyatman nan premye fwa nou fè yon divizyon, men,
ankò, sonje ke byenke rechèch binè se
anpil pi bon pase rechèch lineyè pa vèti nan yo te louvri sesyon n kont n,
ou ta ka gen yo ale nan travay nan a klasman etalaj ou premye, ki
ta ka fè li mwens efikas depann sou gwosè a nan iteration nan Ranje.
>> Mwen se Doug Lloyd, sa a se CS50.