[MIZIK jwe] 

Doug Lloyd: OK, se konsa yon unifye sòt se ankò yon lòt algorithm ke nou ka itilize yo sòt deyò eleman ki nan yon etalaj. Men, jan nou pral wè, li nan te resevwa yon diferans trè fondamantal soti nan sòt seleksyon, ti wonn sòt, ak sòt ensèsyon ki fè li vrèman bèl entelijan. 

Lide a debaz dèyè unifye sòt se sòt pi piti ranje ak Lè sa a konbine sa yo ranje ansanm, oswa rantre them-- kon sa name-- a nan Ranje lòd. Fason ki ki rantre sòt fè sa a se pa swe yon zouti rele rkursyon, ki se sa nou ap ale nan dwe ap pale de byento, men nou pa te reyèlman te pale osijè de ankò. 

Isit la nan lide a debaz dèyè sòt unifye. Triye mwatye nan gòch nan etalaj la, an konsideran n se pi gran pase 1. Ak sa ki mwen vle di lè m 'di an konsideran n se pi gran pase 1 se, Mwen panse ke nou kapab dakò ke si yon etalaj sèlman konsiste de yon eleman sèl, li nan Ranje. Nou pa aktyèlman bezwen fè anyen nan li. Nou ka jis deklare li yo dwe klase. Li nan sèlman yon eleman sèl. 

Se konsa, pseudocode a, ankò, se sòt mwatye nan bò gòch nan etalaj la, Lè sa a, sòt mwatye nan dwa etalaj la, Lè sa a, rantre de mwatye yo ansanm. Koulye a, ou ka deja panse, li kalite jis son tankou w ap mete nan the-- w ap pa aktyèlman fè anyen. W ap di sòt bò gòch la mwatye, sòt mwatye nan dwa, men ou pa ap di m 'ki jan ou ap fè li. 

Men, sonje ke osi lontan ke yon etalaj se yon eleman sèl, nou ka deklare li Ranje. Lè sa a, nou ka jis konbine yo ansanm. Epi sa a, aktyèlman an lide fondamantal dèyè unifye sòt, se kraze li desann pou ke ranje ou yo nan gwosè yon sèl. Lè sa a, ou rebati soti nan la. 

Rantre sòt se definitivman yon algorithm konplike. Apre sa, li la tou yon ti kras konplike yo visualized. Se konsa, èspere ke, vizyalizasyon a ke mwen gen isit la pral ede w swiv ansanm. Apre sa, mwen pral eseye pi byen m 'rakonte bagay epi kontinye nan sa a yon ti kras plis tou dousman pase sa yo lòt jis yo èspere ke jwenn tèt ou alantou lide yo dèyè sòt unifye. 

Se konsa, nou gen etalaj la menm jan ak nan lòt klasman videyo algorithm si ou te wè them-- yon etalaj sis eleman. Ak kòd pseudocode nou yo isit la se sòt mwatye nan bò gòch, sòt mwatye nan dwa, rantre de mwatye yo ansanm. Se konsa nou pran sa a trè nwa wouj brik etalaj ak sòt mwatye nan bò gòch nan li. 

Se konsa, pou kounye a, nou ap ale ki inyore bagay la sou bò dwat la. Li nan gen, men nou ap pa nan ki etap ankò. Nou pa nan sòt nan dwat mwatye nan etalaj la. Nou ap nan sòt bò gòch la mwatye nan etalaj la. Epi jis pou dedomajman pou la pou yo te yon ti kras pi plis klè, pou m ka al gade nan sa etap nou ap sou li a, Mwen pral chanje a koulè nan sa a mete nan zoranj. Koulye a, nou ap toujou ap pale de la menm mwatye gòch nan etalaj la orijinal la. Men, Mwen espere ke pa ke yo te kapab al gade nan koulè yo nan atik divès kalite, li pral fè l 'yon ti kras pi plis klè sa k ap pase isit la. 

OK, se konsa kounye a nou gen yon twa etalaj eleman. Ki jan nou sòt mwatye nan bò gòch nan sa a etalaj, ki se toujou etap sa a? Nou ap eseye sòt bò gòch la mwatye nan brik wouj la array-- mwatye nan bò gòch nan yo ki Mwen te kounye a ki gen koulè pal zoranj. 

Oke, nou te ka eseye ak repete pwosesis sa a ankò. Se konsa, nou ap toujou nan la presegondè nan ap eseye sòt mwatye nan gòch nan etalaj la plen. Mwatye nan bò gòch de la etalaj, mwen jis ale abitrèman deside ke mwatye nan bò gòch yo pral pi piti pase mwatye nan dwa, paske sa a k ap pase nan konpoze de twa eleman. 

Se konsa, mwen pral di la ki gòch mwatye nan mwatye a gòch etalaj la se jis eleman nan senk. Senk, yo te yon eleman sèl etalaj, nou konnen ki jan yo sòt li. Se konsa, senk se Klase. Nou ap jis ale nan deklare ke. Li se yon etalaj eleman sèl. 

Se konsa, nou te kounye a Ranje a gòch mwatye nan half-- gòch la ou pito, nou te Ranje a gòch mwatye nan zoranj la. Se konsa, kounye a, yo nan lòd yo toujou konplè gòch mwatye etalaj la an jeneral la, nou bezwen sòt mwatye nan dwa nan zoranj la, oswa bagay sa a. Ki jan nou fè sa? Oke, nou gen yon etalaj de eleman. Se konsa, nou kapab Trier mwatye nan bò gòch nan etalaj la, ki se de. De se yon eleman sèl. Se konsa, li nan Ranje pa default. Lè sa a, nou ka sòt mwatye nan dwa nan ki pòsyon nan etalaj la, yon sèl la. Sa a sòt de pa defo. 

Sa a se kounye a premye fwa a nou te rive jwenn yon etap unifye. Nou fin fè, byenke nou ap kounye a kalite pare solèy down-- e ke sa a sòt de difisil nan bagay ak rkursyon se, ou bezwen kenbe ou tèt sou kote nou ye. Se konsa, nou te sòt de bò gòch la mwatye nan pòsyon nan zoranj. 

Epi, koulye a, nou ap nan mitan an nan klasman mwatye nan dwa nan pòsyon nan zoranj. Ak nan pwosesis sa a, nou se kounye a sou yo dwe sou etap la, rantre de mwatye yo ansanm. Lè nou gade nan de mwatye yo nan etalaj la, nou wè de ak yon sèl. Ki eleman se pi piti? Yon. 

Lè sa a, ki eleman se pi piti? Oke, li nan de oswa pa gen anyen. Se konsa, li de. Se konsa, kounye, jis ankò ankadreman kote nou ye nan yon kontèks, nou te Ranje a gòch mwatye nan zoranj la ak mwatye nan dwa ki gen orijin nan. Mwen konnen mwen te chanje koulè yo ankò, men sa a kote nou te ye. Ak rezon an m 'te fè sa a se paske pwosesis sa a se ale nan kenbe prale a, iteration desann. Nou te Ranje bò gòch la mwatye nan ansyen zoranj la ak mwatye nan dwa nan ansyen zoranj la. 

Koulye a, nou bezwen rantre moun de mwatye ansanm tou. Sa a etap la nou ap sou. Se konsa, nou konsidere tout de la eleman ki yo kounye a se vèt, mwatye nan gòch nan etalaj la orijinal la. Apre sa, nou rantre sa yo lè l sèvi avèk pwosesis la menm nou te fè pou fusion de ak youn jis yon ti moman de sa. 

Mwatye nan bò gòch, pi piti a eleman sou mwatye nan bò gòch se senk. Eleman ki pi piti a sou mwatye nan dwa se youn. Ki nan tout sa yo se pi piti? Yon. 

Eleman ki pi piti a sou mwatye nan bò gòch se senk. Eleman ki pi piti a sou mwatye nan dwa se de. Ki sa ki nan pi piti a? De. Lè sa a, anfen senk ak pa gen anyen, nou ka di senk. 

OK, se konsa gwo foto, se pou yo pran yon ti repo pou yon dezyèm ak figi konnen kote nou ye. Si nou kòmanse soti nan kòmansman la anpil, nou gen kounye a ranpli pou etalaj la an jeneral jis yon sèl etap nan kòd la pseudocode isit la. Nou te Ranje a gòch mwatye nan etalaj la. 

Sonje byen, orijinal la lòd te senk, de, yon sèl. Pa ale atravè tout pwosesis sa a ak nidifikasyon desann ak repete, kontinye kraze pwoblèm nan desann nan pi piti ak pi piti pati, nou te kounye a ranpli etap youn nan pseudocode a pou etalaj la kòmanse tout antye. Nou te Ranje mwatye gòch li yo. 

Se konsa, kounye a kite a friz la. Epi, koulye a kite a sòt dwat a mwatye nan etalaj la orijinal la. Epi nou ap ale nan fè sa pa ale atravè tout menm repete nan pwosesis pou kraze bagay sa yo desann ak Lè sa a fusion yo ansanm. 

Se konsa, mwatye nan gòch nan la wouj, oswa mwatye nan bò gòch nan mwatye nan dwa nan orijinal la etalaj, mwen pral di se twa. Yon fwa ankò, mwen ke yo te konsistan isit la. Si ou gen yon enpè kantite eleman, li pa reyèlman gen pwoblèm si ou fè yon sèl nan kite pi piti oswa yon sèl nan dwa pi piti. 

Sa ki enpòtan se ke chak fwa ou rankontre pwoblèm sa a nan fè yon unifye, ou bezwen yo dwe ki konsistan. Ou swa toujou bezwen fè yon bò kite pi piti oswa toujou bezwen fè bò dwat ki pi piti. Isit la, mwen te chwazi yo toujou fè bò la kite pi piti lè etalaj mwen, oswa mwen sub-etalaj, se nan yon gwosè enpè. 

Twa se yon eleman sèl, e konsa li se Klase. Nou te exploitées ki sipozisyon nan tout tout pwosesis nou an byen lwen tèlman. Se konsa, kounye a kite a sòt dwat a mwatye nan mwatye a dwat, oswa mwatye nan dwa nan wouj la. 

Yon fwa ankò, nou bezwen fann sa a desann. Sa a se pa yon etalaj eleman sèl. Nou pa ka deklare li Ranje. Se konsa, premye, nou ap ale sòt mwatye gòch la. 

Mwatye nan bò gòch se yon eleman sèl, se konsa li a sòt de pa defo. Lè sa a, nou ap ale nan sòt dwat a mwatye, ki se yon eleman sèl. Li nan Ranje pa default. Epi, koulye a, nou ka rantre sa yo de yo ansanm. Kat se pi piti, ak Lè sa a, sis se pi piti. 

Yon fwa ankò, sa nou fè nan pwen sa a? Nou te Ranje bò gòch la mwatye nan mwatye a dwat. Ou pral tounen nan orijinal la koulè ki te la, nou te Ranje bò gòch la mwatye nan wouj la douser. Li te orijinèlman yon brik fè nwa wouj ak kounye a li nan yon wouj douser, oswa li te yon wouj douser. 

Lè sa a, nou te Ranje a dwat mwatye nan wouj la douser. Koulye a, byen, yo ap vèt ankò, jis paske nou ap ale atravè tout yon pwosesis. Epi nou gen repete sou sa a yo ak sou. 

Se konsa, kounye a nou ka rantre sa yo de mwatye yo ansanm. Epi sa a, sa nou fè isit la. Se konsa, liy la nwa jis divize mwatye nan bò gòch ak mwatye nan dwa nan pati sa a sòt. 

Nou konpare valè ki pi piti a ki sou bò gòch nan array-- nan oswa eskize m ', pi piti a valè de mwatye nan bò gòch nan valè ki pi piti a yo sou dwa yo mwatye ak jwenn ke twa se pi piti. Epi, koulye a yon ti jan nan yon optimize, dwa? Genyen aktyèlman pa gen anyen kite sou bò gòch la. 

Pa gen anyen ki rete ki sou bò gòch, se konsa nou kapab avèk efikasite jis move-- nou ka deklare rès la nan li se aktyèlman Ranje ak jis fofile li sou li a, paske pa gen anyen lòt yo konpare kont. E nou konnen ke bò dwat a bò dwat se Klase. 

OK, se konsa kounye a kite a friz ankò e konnen ki kote nou se nan istwa a. Nan etalaj la an jeneral, kisa m nou akonpli? Nou te aktyèlman akonpli kounye a etap yon sèl ak etap de. Nou Ranje mwatye nan bò gòch, ak nou Ranje mwatye nan dwa. 

Se konsa, kounye a, tout sa ki rete se pou nou rantre sa yo de mwatye yo ansanm. Se konsa, nou konpare pi ba valè a eleman nan chak mwatye nan etalaj la nan vire epi kontinye. Youn nan se mwens pase twa, se konsa yon sèl ale. 

De se mwens pase twa, se konsa de ale. Twa ki pi piti a pase 5, se konsa twa ale. Kat se mwens pase 5, se konsa kat ale. Lè sa a, senk se mwens pase sis, ak sis se tout sa ki rete. 

Koulye a, mwen konnen, sa ki te yon anpil nan etap. Apre sa, nou te kite yon anpil nan memwa nan reveye nou an. Epi sa a, sa ki sa yo kare gri ye. Apre sa, li pwobableman te santi tankou sa te pran yon anpil pi lontan pase sòt ensèsyon, ti wonn sòt, oswa sòt seleksyon. 

Men, aktyèlman, paske yon anpil nan pwosedi sa yo ap pase nan menm time-- nan ki se yon bagay nou pral, ankò, pale sou lè nou pale sou rkursyon nan yon avni video-- sa a algorithm aktyèlman klèman se fondamantalman diferan pase anyen nou te wè anvan men tou se siyifikativman pi efikas. 

Poukisa se sa? Oke, nan pi move a ka senaryo, nou gen a fann n eleman moute ak Lè sa a rkonbin yo. Men, lè nou rkonbin yo, sa n ap fè se fondamantalman double nan gwosè nan ranje yo pi piti. Nou gen yon pakèt moun sou yon sèl eleman ranje ke nou efektivman konbine nan de ranje eleman. Lè sa a, nou pran moun de ranje eleman ak konbine yo ansanm nan kat ranje eleman, ak sou sa, ak sou sou sa, e konsa, jiskaske nou gen yon etalaj eleman n sèl. 

Men, ki jan anpil doublings li pran pou li ale nan n? Panse tounen nan egzanp lan liv telefòn. Konbyen fwa fè nou dwe chire liv la telefòn nan mwatye, ki jan anpil plis fwa fè nou dwe chire liv telefòn nan mwatye, si gwosè a nan liv la telefòn double? Genyen sèlman yon sèl, dwa? 

Se konsa, gen nan kèk sòt de logaritmik eleman isit la. Men, nou menm tou nou toujou gen nan omwen gade nan tout nan eleman yo n. Se konsa, nan senaryo a ka pi mal la, rantre sòt kouri nan boutèy demi lit n n. Nou gen fè yon gade nan tout nan eleman yo n, e nou gen konbine yo ansanm nan boutèy demi lit n kouche nan etap. Nan senaryo a ka pi bon, etalaj la se parfe Ranje. Sa bon. Men, ki baze sou algorithm a nou gen isit la, nou toujou gen yo fann ak rkonbin. Malgre ke nan ka sa a, nan rekombinezon se kalite efikas. Li pa nesesè. Men, nou toujou ale nan pwosesis la tout antye de tout fason. 

Se konsa, nan ka ki pi bon ak nan ka ki pi mal, sa a algorithm kouri nan boutèy demi lit n N tan. Rantre sòt se definitivman yon ti jan Delice pase lòt algoritm yo klasman prensipal nou te pale osijè de CS50 men se anpil plis pouvwa anpil. 

Se konsa, si ou te janm jwenn okazyon bezwen li oswa yo sèvi ak li nan sòt yon gwo seri done, ap resevwa tèt ou otou lide nan rkursyon ki pral yo dwe reyèlman gen anpil pouvwa. Apre sa, li la pral fè ou pwogram reyèlman pi plis efikas lè l sèvi avèk rantre sòt kont nenpòt lòt bagay. Mwen se Doug Lloyd. Sa a se CS50.