[Powered by Google Translate] [Triye ensèrsyon] [Tommy MacWilliam] [Inivèsite Harvard] [Sa a se CS50.TV] Se pou nou pran yon gade nan sòt ensèsyon, yon algorithm pou pran yon lis nimewo ak Fouye yo. Yon algorithm, sonje, se senpleman yon pwosedi etap-pa-etap pou reyalize yon travay. Lide a debaz dèyè sòt ensèsyon, se divize lis nou an nan de pòsyon, yon pòsyon klase epi yon pòsyon klase. 

Nan chak etap nan algorithm la, se yon nimewo te deplase soti nan pòsyon ki klase pòsyon nan Ranje jiskaske evantyèlman se lis la tout antye Ranje. Isit la se lis la nan sis chif klase - 23, 42, 4, 16, 8, ak 15. Depi nimewo sa yo se pa tout nan Ascending lòd yo, yo ap klase. Kòm nou pa te kòmanse Fouye ankò, nou pral konsidere tout eleman sis pòsyon klase nou an. 

Yon fwa nou kòmanse Fouye, nou pral mete nimewo sa yo Ranje a gòch la nan sa yo. Se konsa, kite la kòmanse avèk 23, eleman an premye nan lis nou an. Nou pa gen okenn eleman nan Ranje pòsyon nou an ankò, kidonk kite la tou senpleman konsidere 23 yo dwe nan kòmansman an ak nan fen Ranje pòsyon nou an. Koulye a, pòsyon Ranje nou an ki gen yon sèl nimewo, 23, ansanm ak pòsyon klase nou an ki gen nimewo sa yo senk. Se pou nou kounye a insert pwochen nonb nan pòsyon klase nou an, 42, nan pòsyon nan Klase. 

Pou fè sa, nou pral bezwen konpare salè 42 a 23 an - eleman nan sèlman nan Ranje pòsyon nou byen lwen tèlman. Karant-de se pi gwo pase 23, pou nou ka tou senpleman ajoute 42 nan fen a nan pòsyon an Ranje nan lis la. Gwo! Koulye a, pòsyon Ranje nou an ki gen de eleman, ansanm ak pòsyon klase nou an ki gen kat eleman. Se konsa, kite a kounye a deplase a 4 an, eleman nan pwochen nan pòsyon klase. Se konsa, kote yo ta dwe sa a dwe mete nan pòsyon Ranje? 

Sonje byen, nou vle mete nan nimewo sa a nan Ranje lòd Se konsa pòsyon Ranje nou rete kòrèkteman Klase nan tout fwa. Si nou mete 4 an a dwat a 42 an, Lè sa a, lis nou an pral soti nan lòd. Se konsa, kite a kontinye deplase dwa-a-gòch nan pòsyon sòt nou an. Kòm nou deplase, kite la chanje chak nimewo desann yon kote ki pou fè plas pou nimewo a nouvo. Okay, 4 se tou pi piti pase 23, se konsa nou pa ka mete l 'isit la swa. Kite yo deplase 23 dwa yon sèl kote a. 

Sa vle di nou ta renmen yo mete 4 an nan plas an premye nan pòsyon Ranje. Avi sou jan espas sa a nan lis la te deja vid, paske nou ve yo te deplase Ranje eleman desann kòm nou te rankontre yo. Tout dwa. Se konsa, nou ap mwatye a. Se pou nou kontinye algorithm nou yo lè nou mete 16 a nan pòsyon nan Klase. Sèz se mwens pase 42, kidonk kite nan chanjman 42 la a dwat la. Sèz tou se mwens pase 23, kidonk kite a tou chanjman ki eleman. 

Koulye a, 16 se pi gran pase 4. Se konsa, li sanble nou ta renmen insert 16 ki genyen ant 4 an ak 23 an. Pandan ke mouvman atravè pòsyon nan Ranje nan lis la de dwat a gòch, 4 se nimewo a premye nou te wè ki se pi piti pase kantite nou ap eseye insert. Se konsa, kounye a nou ka insert 16 la nan sa a plas vid, ki, sonje, nou te kreye pa eleman deplase nan pòsyon sòt sou kòm nou te rankontre yo. 

Tout dwa. Koulye a, nou gen kat Ranje eleman ak de eleman klase. Se konsa, kite yo deplase 8 la nan pòsyon nan Klase. Uit se mwens pase 42. Uit se mwens pase 23. Ak 8 gen mwens pase 16. Men, 8 se pi gran pase 4. Se konsa, nou ta renmen insert 8 ki genyen ant 4 an ak 16 an. Epi, koulye a nou jis gen yon sèl plis eleman goch a sòt - 15 la. Kenz se mwens pase 42, Kenz se mwens pase 23. Ak 15 gen mwens pase 16. Men, 15 se pi plis pase 8. 

Se konsa, isit la se kote nou vle fè ensèsyon final nou an. Ak nou ap fè. Nou pa gen okenn eleman plis nan pòsyon klase, ansanm ak pòsyon Ranje nou an se yo nan lòd ki kòrèk la. Nimewo sa yo yo te bay lòd soti nan pi piti pi gwo. Se konsa, kite a pran yon gade nan kèk pseudocode ki dekri etap sa yo nou jis fèt. 

Sou liy 1, nou ka wè ke nou pral bezwen repekte sou chak eleman nan lis la eksepte premye a, depi nan premye eleman nan pòsyon klase pwal tou senpleman vin eleman nan premye nan pòsyon nan Klase. Sou liy 2 ak 3, n ap kenbe tras de kote nou an ki ajou nan pòsyon klase. Eleman reprezante kantite a nou yo kounye a paralize nan pòsyon nan Ranje, ak j reprezante endèks nou an, nan pòsyon ki klase. 

Sou liy 4, nou ap iteration nan pòsyon nan Ranje soti nan dwa a goch. Nou vle sispann iteration yon fwa eleman ki nan kite nan pozisyon nou an ki ajou se mwens pase eleman nan nou ap eseye insert. Sou liy 5, nou ap déplacement chak eleman nou kontre yon sèl espas a dwat la. Nan fason sa a, nou pral gen yon espas klè insert nan lè nou jwenn eleman nan premye mwens pase eleman an ke nou ap deplase. Sou liy, 6, nou ap mete ajou kontwa nou kontinye pou avanse pou pi kite nan pòsyon nan Klase. Finalman, sou liy 7, n ap mete eleman an nan pòsyon nan Ranje nan lis la. 

Nou konnen ke li oke insert nan j pozisyon, paske nou te deja te deplase eleman a ki itilize yo dwe gen yon espas a dwat la. Sonje byen, nou ap mouvman atravè pòsyon nan Ranje soti nan dwa a goch, men nou ap mouvman atravè pòsyon nan klase de gòch a dwat. Tout dwa. Se pou nou kounye a pran yon gade nan konbyen tan kouri ki algorithm te pran. Nou pral premye mande kesyon an konbyen tan li pran pou sa a algorithm nan kouri nan ka ki pi mal la. Sonje ke nou reprezante tan sa a ap kouri avèk notasyon Big O. Yo nan lòd yo klase lis nou an, nou te repekte sou eleman yo nan pòsyon ki klase, epi pou chak moun sa yo eleman, potansyèlman sou tout eleman nan pòsyon nan Klase. Intuitivement, sa a son tankou yon operasyon O (n ^ 2). 

Gade nan pseudocode nou an, nou gen yon riban pare solèy andedan yon lòt bouk, ki, tout bon, son tankou yon operasyon O (n ^ 2). Sepandan, pòsyon nan Ranje nan lis pa t 'gen ladan lis la tout antye jouk nan fen an trè. Toujou, nou te kapab potansyèlman insert yon eleman nouvo nan kòmansman la anpil nan pòsyon nan Ranje sou chak iterasyon nan algorithm a, ki vle di ke nou ta gen fè yon gade nan chak eleman kounye a nan pòsyon Ranje. Se konsa, sa vle di nou te kapab potansyèlman fè yon sèl konparezon pou eleman, dezyèm lan, de konparezon pou eleman nan twazyèm, ak sou sa. Se konsa, kantite total etap a se sòm total nonm antye relatif yo nan 1 rive nan longè nan lis la mwens 1. Nou ka reprezante sa a ak yon somasyon. 

Nou pa pral antre summations isit la, men li sanble ke sa a somasyon ki egal a n (n - 1) plis pase 2, ki se ekivalan n ^ 2/2 - n / 2. Lè w ap pale sou ègzekutabl asenptotik, sa a n ^ 2 tèm ki pral domine tèm sa a n. Se konsa, sòt ensèsyon se Big O (n ^ 2). E si nou kouri sòt ensèsyon sou yon lis deja klase. Nan ka sa a, nou ta tou senpleman bati pòsyon nan Ranje soti nan gòch a dwat. Se konsa,, nou pral bezwen sèlman sou lòd la n etap. 

Sa vle di ke sòt ensèsyon an gen yon pèfòmans pi bon-ka nan n, ki nou reprezante ak Ω (n). Epi sa a, li pou sòt ensèsyon, jis youn nan algoritm yo anpil nou ka itilize yo sòt yon lis. Non mwen se Tommy, e sa se CS50. [CS50.TV] Oh, ou jis pa ka sispann ke yon fwa li kòmanse. Oh, nou te fè sa - Boom >>!