[Powered by Google Translate] [Triye jarèt] [JACKSON STEINKAMP Inivèsite Harvard] [SA A SE CS50. CS50TV] Triye jarèt ki se yon egzanp yon algorithm Fouye - ki se, yon pwosedi pou Fouye yon seri eleman nan yon moute desann oswa lòd. Pou egzanp, si ou te vle sòt yon etalaj ki gen ladan nimewo yo [3, 5, 2, 9], yon aplikasyon kòrèk la nan Triye Bubble ta retounen nan Ranje etalaj [2, 3, 5, 9] nan Ascending lòd. Koulye a, mwen pral eksplike nan pseudocode ki jan algorithm a travay. 

Se pou nou di nou ap Fouye yon lis 5 nonm antye relatif - 3, 2, 9, 6, ak 5. Algorithm la kòmanse pa gade nan de eleman yo an premye, 3 ak 2, epi tyeke si yo ap soti nan lòd relatif nan chak lòt. Yo se - 3 pi gran pase 2. Pou yo kapab nan lòd montangn yo, yo ta dwe nan lòt fason alantou. Se konsa, nou boukante yo. Koulye a, lis la sanble tankou sa a: [2, 3, 9, 6, 5]. 

Next, nou gade nan eleman yo, dezyèm ak twazyèm 3 ak 9. Yo ap nan lòd ki kòrèk relatif nan chak lòt. Sa se, 3 se mwens pase 9 Se konsa algorithm a pa boukante yo. Next, nou gade nan 9 ak 6. Yo ap parèt nan lòd. 

Se konsa,, nou bezwen swap yo paske 9 pi gran pase 6. Anfen, nou gade nan de nonb antye ki sot pase yo, 9 ak 5. Yo ap soti nan lòd, se konsa yo dwe échanges. Apre premye pas konplè a nan lis la, li sanble tankou sa a: [2, 3, 6, 5, 9]. Pa move. Li nan prèske Ranje. Men, nou bezwen kouri nan lis la ankò jwenn li konplètman Ranje. De se mwens pase 3, donk nou pa boukante yo. 

Twa gen mwens pase 6, donk nou pa boukante yo. Sis gen plis pouvwa pase 5. Nou échanges. Sis se mwens pase 9. Nou pa boukante. Apre pas nan dezyèm nan, li sanble tankou sa a: [2, 3, 5, 6, 9]. Pafè. Koulye a, kite nan ekri li nan pseudocode. Fondamantalman, pou chak eleman nan lis la, nou bezwen gade nan li ak eleman la dirèkteman a dwat li yo. Si yo soti nan lòd relatif nan chak lòt - ki se, si eleman nan sou bò gòch la se pi plis pase youn nan sou bò dwat la - nou ta dwe swap eleman yo de. 

Nou fè sa pou chak eleman nan lis la, epi nou te fè yon sèl pase nan. Koulye a, nou jis gen nan fè pass-through fwa yo ase yo asire lis la se okonplè, byen Ranje. Men, konbyen fwa nou gen la pase sou lis la garanti ke nou ap fè konsa? Oke, senaryo ki pi mal la-ka se si nou gen yon lis konplètman bak. Lè sa a, li pran yon kantite pase kuvèt-egal a nimewo a nan eleman n-1. Si sa a pa fè sans intuitivement, panse a yon ka senp - lis la [2, 1]. 

Sa a se pral pran yon sèl pass-through sòt kòrèkteman. [3, 2, 1] - ka ki pi mal se ke ak 3 eleman Ranje bak, li nan pral pran 2 itérations zèl. Apre yon sèl iterasyon, li la [2, 1, 3]. Pwodiksyon an nan dezyèm etalaj la Ranje [1, 2, 3]. Se konsa, ou konnen ou pa janm gen yo ale nan etalaj la, an jeneral, plis pase n-1 fwa, kote n se nimewo a eleman nan yon etalaj la. Yo rele li Triye Bubble paske eleman yo pi gwo yo gen tandans 'jarèt-up' sou bò dwat la yo byen vit. An reyalite, sa a algorithm gen konpòtman trè enteresan. 

Apre itérations m nan etalaj la an antye, rightmost eleman yo m yo garanti yo dwe klase nan plas ki kòrèk yo. Si ou vle wè sa a pou tèt ou, nou ka eseye li sou yon lis [9, 6, 5, 3, 2] konplètman bak. Apre yon sèl pase nan lis la an antye, [Son nan ekri] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] eleman nan rightmost 9 se nan plas apwopriye li yo. Apre dezyèm lan pass-through, 6 a ap gen 'bul-up' yo, vin nan dezyèm plas rightmost. Eleman yo de sou bò dwat la - 6 ak 9 - yo pral nan kote ki kòrèk yo apre de kuvèt yo pass-an premye. 

Se konsa, ki jan nou ka itilize sa-a optimize algorithm a? Oke, apre yon iterasyon nan etalaj la nou pa aktyèlman bezwen tcheke eleman nan rightmost paske nou konnen li la Ranje. Apre de itérations, nou konnen pou asire w rightmost de eleman yo ki nan plas li. Se konsa, an jeneral, apre yo fin itérations k nan etalaj la plen, tcheke eleman yo k pase a se redondants depi nou konnen yo ap nan kote ki kòrèk la deja. 

Se konsa, si w ap Fouye yon etalaj de n eleman, sou iterasyon nan premye - you'll gen sòt tout nan eleman yo - premye n-0 a. Sou iterasyon, dezyèm lan, ou pral gen fè yon gade nan tout nan eleman yo, men dènye a - premye a n-1. Yon lòt Optimization ta kapab ou tcheke si se lis la deja klase yo apre chak iterasyon. Si li la deja klase, nou pa bezwen fè nenpòt ki plis itérations nan lis la. Ki jan nou ka fè sa? Oke, si nou pa fè okenn echanj sou yon pase nan-nan lis la, li nan klè ki te lis la deja klase paske nou pa t 'swap anyen. Se konsa, nou definitivman pa bezwen sòt ankò. 

Petèt ou ta ka inisyalize yon varyab drapo rele 'pa Ranje' yo, vin fo ak chanje li nan vre si ou gen nenpòt eleman swap sou yon sèl iterasyon nan etalaj la. Oswa menm, fè yon kontwa nan konte konbyen echanj ou fè sou nenpòt ki iterasyon bay yo. Nan fen yon iterasyon, si ou pa t 'swap nenpòt nan eleman yo, ou konnen se lis la deja klase epi w ap fè. Triye jarèt, tankou algoritm klasman lòt, yo ka tweaked pou travay pou nenpòt eleman ki gen yon metòd kòmande. 

Sa se, bay de eleman ou gen yon fason yo di si yon sèl nan premye se pi gran pase, egal a oswa pi piti pase dezyèm lan. Pou egzanp, ou ta ka klase lèt nan alfabè a lè li di ke yon <b, b <c, elatriye Oswa ou ta ka sòt jou nan semèn lan kote Dimanch se mwens pase Lendi ki se mwens pase Madi. 

Triye jarèt se pa pa gen okenn vle di yon algorithm klasman trè efikas oswa vit. Ègzekutabl pi move-ka li se Big O nan n ² paske ou gen fè n itérations nan yon lis tcheke tout eleman n chak pass-through, nxn = n ². Fwa sa a, kouri vle di ke kòm nimewo a nan eleman ou ap Fouye ogmante, tan an kouri ogmante quadratically. 

Men, si efikasite se pa yon pi gwo enkyetid nan pwogram ou an oswa si w ap sèlman Fouye yon ti kantite eleman, ou ta ka jwenn Triye Bubble itil paske li nan youn nan pi senp algoritm yo Fouye yo konprann ak kòd. Li la tou yon bon fason jwenn eksperyans avèk tradui yon teyorik algorithm nan kòd fonksyone vrè. Oke, sa a, se Triye Bubble pou ou. Mèsi pou gade. CS50.TV