[Powered by Google Translate] [Pagsamahin ang uri-uriin] [Rob Bowden - Harvard University] [Ito ay CS50. - CS50.TV] Natin makipag-usap tungkol sa pagsasama-uuri. Sa ngayon nakita mo ang bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri. Kahit na bibigyan ko uri ng wave ang aking kamay sa kung ano ang ibig sabihin ko sa pamamagitan ng mas mahusay na, sumanib-uuri sa pangkalahatan ay mas mahusay na gumaganap kaysa sa anumang ng mga 3 uri. 

Ngunit bago ang pakikipag-usap tungkol sa pagsasama-uuri, sabihin makipag-usap tungkol sa pinagsasama ng 2 pinagsunod-sunod listahan. Susubukan naming tawagan ang proseso ng pagkuha ng 2 pinagsunod-sunod listahan, tulad ng mga ito, at gumagawa ng isang pinagsunod-sunod na listahan sa kanila - pinagsasama ang mga listahan. Paano namin gawin ito? Well, isang ideya lang dumikit ang isang listahan papunta sa dulo ng iba pang listahan at pagkatapos ay ayusin ang listahan na nagreresulta. 

Habang ito gumagana, ng maraming ng hindi kinakailangang trabaho. Maaari naming gawin ito mas mabilis pa sa pag-uuri-uri. Pansinin na ang isang maling ideya ay lamang tumagal ng alternating tasa mula sa bawat listahan. Habang na maaaring tila na gumagana sa unang, ginagawa na namin magtapos sa 4, 8, 15, 23, 16 - paunawa na 16 at 23 ay wala sa lugar. Ito ay dahil ang 2 elemento na dapat lumitaw magkakasunod sa merged na listahan sa parehong unang listahan. Parehong 15 at 16 sa listahan sa kaliwa. Nanlilinlang ay upang samantalahin ng katotohanan na ang parehong mga listahan ay pinagsunod-sunod. Nangangahulugan ito na kung lamang namin tumingin sa unang elemento ng parehong mga listahan - dito, 4 at 8 - isa sa mga ito ay dapat ding maging ang unang elemento ng naka-merge na listahan. Well, kung bakit ay na? Parehong ng mga listahan ay pinagsunod-sunod, at kaya alinman sa 4 o 8 dapat ang pinakamaliit na elemento kapag pagsamahin namin ang 2 listahan. Sa kasong ito, ang pinakamaliit ay 4, upang maaari naming kumuha ng 4 at gawin itong ang unang elemento ng aming mga naka-merge na listahan. Ngayon ay ipagpapatuloy namin ang pinagsasama ang natitirang 3 elemento ng ang unang listahan at 4 na elemento ng pangalawang listahan. 

Muli, kailangan lamang namin upang tumingin sa unang elemento ng parehong mga listahan. Ang mas maliit sa 2 ay dapat na ang pangalawang elemento ng aming mga naka-merge na listahan. Oras na ito, sa pagitan ng 8 at 15 ang pinakamaliit ay 8, at kaya namin isingit na bilang ang pangalawang elemento ng aming mga listahan ng pinagsunod-sunod. Maaari naming patuloy na naghahambing ng mga unang elemento ng parehong mga listahan at pag-alis ng mas maliit sa 2. Paghahambing ng 15 at 23, 15 ay mas maliit at sa gayon ay ang aming ikatlong elemento. Ngayon naghahambing ng 16 at 23, 16 ay mas maliit. Kaya, na ang ika-apat na elemento. 

Pansinin na ang 2 elemento ay nagmula mula sa parehong listahan sa isang hilera. Ito ay kung bakit ang naka-merge na listahan ay hindi lamang kahaliling elemento mula sa 2 listahan. Paghahambing ng 50 at 23, 23 ay mas maliit, kaya pinili namin na. Sa pagitan ng 50 at 42, 42 ay mas maliit. Sa pagitan ng 50 at 108, 50 ay mas maliit. At, sa wakas, kami na lang ay 108, kaya dapat itong pumunta sa dulo ng aming listahan. Pansinin na mayroon kaming gandang, pinagsunod-sunod listahan. Bawat oras na namin kumpara sa unang 2 elemento ng 2 listahan namin upang matukoy ang susunod na elemento ng naka-merge na listahan. Nangangahulugan ito na kung ang panghuling listahan ay naglalaman ng mga n numero, kung saan n dito ay 8, kailangan namin sa karamihan ng mga n paghahambing upang makuha ang lahat ng mga numero sa tamang lugar. Tulad ng isang algorithm ay sinabi upang tumakbo sa linear oras, ngunit huwag mag-alala tungkol na dito. 

Gamit ang aming algorithm para sa pinagsasama, maaari kaming magsagawa ng isang mabilis na pagsasama-uuri algorithm. Kaya, sabihin i-reset ang aming mga listahan. May 2 malaking hakbang sa proseso ng pagsasama-uuri. Una, patuloy na hatiin ang listahan ng mga tasa sa halves hanggang kami ay may isang bungkos ng mga listahan na may 1 tasa sa kanila. Huwag mag-alala kung ang isang listahan ay naglalaman ng isang kakaibang numero at hindi ka maaaring gumawa ng isang perpektong malinis na hiwa sa pagitan ng mga ito. Lang mang pick kung aling listahan upang isama ang dagdag na tasa. Kaya, sabihin hatiin ang mga listahang ito. Ngayon ay mayroon kaming 2 listahan. Ngayon ay mayroon kaming 4 na listahan. 

At ngayon kami ay may 8 mga listahan na may isang tasa sa bawat listahan. Kaya na ito para sa hakbang 1. Para sa hakbang 2, paulit-ulit kaming magsama ng mga pares ng mga listahan gamit ang sumanib algorithm na namin natutunan bago. Pagsasama sa 108 at 15, magtapos namin sa listahan sa 15, 108. Pinagsasama ang 50 at 4, magtapos namin na may 4, 50. Pagsasama sa 8 at 42, magtapos namin na may 8, 42. At pinagsasama ng 23 at 16, kami magtapos na may 16, 23. Ngayon ang lahat ng aming mga listahan ng laki 2. Pansinin na ang bawat isa sa 4 na listahan ay pinagsunod-sunod. 

Upang maaari naming simulan ang pinagsasama ng mga pares ng mga listahan muli. Pagsasama sa 15 at 108 at 4 at 50 - tumagal muna ang 4, pagkatapos ang 15, pagkatapos ay ang 50, pagkatapos ang 108. Pagsasama sa 8, 42 at 16, 23, muna namin ang 8, pagkatapos ang 16, pagkatapos ay ang 23, pagkatapos ay ang 42. Kaya ngayon mayroon kaming may 2 listahan ng mga laki 4, ang bawat isa ay pinagsunod-sunod. Kaya ngayon bumaybay namin mga 2 listahan. Una namin ang 4. Pagkatapos naming gawin ang 8. Pagkatapos namin tumagal ng 15 at 16, pagkatapos 23, pagkatapos 42, pagkatapos 50, pagkatapos 108. At tapos na kami. Namin ngayon ay may pinagsunod-sunod listahan. Kaya kung gaano kabilis ang ito, eksakto? Sa teknikal na termino, pagsasama-uuri ay O (n log n), kung saan ang lahat ng bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri ay O (n ²). Sa katunayan, tulad ng makikita mo malaman sa lalong madaling panahon, hindi mo upang makabuo ng isang uri na mas mahusay na gumaganap kaysa sa O (n log n) sa pangkalahatang kaso. Muli, huwag mag-alala tungkol sa malaking O pagtatanda kung hindi mo pa nakikita ko pa ito. 

Lamang malaman na ang ibig sabihin nito ay kung gusto namin upang pag-uri-uriin ang isang talagang malaking listahan bubble-uri-uriin, pagpapasok ng uri, at pagpili-uuri ay maaaring potensyal na tumagal makabuluhang mas mahaba kaysa sa sumanib-uuri. Hindi ito nangangahulugan na ang pagsasama-uuri ay mas mabilis na para sa lahat ng mga listahan o kahit na para sa anumang solong listahan sa ilalim ng isang tiyak na laki. Halimbawa, ang pagpapasok ng-uuri ay maaaring ang pinakamabilis na uri para sa lahat ng mga listahan na mas maliit sa 5 elemento. Sa pagsasagawa, ang pagsasama-uuri ay karaniwang mas mabilis para sa listahan bilang maliit na bilang 50 mga elemento. 

Ngunit ang dagdag na bilis na ito ay hindi ay walang presyo. Hindi tulad ng aming iba pang mga uri, na gumawa ng isang listahan at baguhin ang listahan sa lugar hanggang sa makuha namin pinagsunod-sunod listahan, pagsasama-uuri ay nangangailangan ng ilang dagdag na espasyo upang sumanib 2 listahan. Hindi agad namin maaaring gamitin ang mga listahan na ay Pinagsama upang mag-imbak ang mga naka-merge na listahan dahil maaari naming i-override ang mga elemento na kailangan pa rin na Pinagsama. Espasyo na ito ay isang bit ng isang presyo, ngunit karaniwang ay hindi walang katwiran. At na ito para sa pagsasama-uuri. 

Ang pangalan ko ay Rob Bowden, at ito ay CS50. [CS50.TV] - At pagpili-uuri. [Laughs] Oh, nakuha ko na kumuha na ang masyadong dahil lumipat ako kung paano ko ay nagtatanghal ito. Listahan sa kaliwa. Na ay isang typo. [Misspoke] ko screwed up - [Laughs] Hindi ko alam kung ano -