[Powered by Google Translate] Tommy: Sabihin isang pagtingin sa pagpili-uuri, isang algorithm para sa paglalaan ng isang listahan ng mga numero at pag-uuri-uri ang mga ito. Isang algorithm, tandaan, ay lamang ng isang hakbang-hakbang na pamamaraan para sa accomplishing isang gawain. Ang pangunahing ideya sa likod ng pagpili-uuri ay upang hatiin aming listahan sa dalawang bahagi - isang pinagsunod-sunod na bahagi at unsorted bahagi. Sa bawat hakbang ng algorithm, ang bilang ay inilipat mula sa unsorted bahagi sa pinagsunod-sunod bahagi hanggang sa kalaunan ang ang buong listahan pinagsunod-sunod. Kaya narito ang isang listahan ng mga anim na numero - 23, 42, 4, 16, 8, at 15. Sa ngayon ang buong listahan ay itinuturing unsorted. Kahit na ang isang numero tulad ng 16 ay maaaring mayroon na sa tamang lokasyon, ang aming mga algorithm ay walang paraan ng alam na hanggang sa ang buong listahan pinagsunod-sunod. Kaya naming isaalang-alang ang bawat numero sa unsorted hanggang namin-uri-uriin ito ating sarili. Alam namin na gusto namin ang listahan sa pataas na pagkakasunod-sunod. Kaya makikita namin nais na bumuo ng ang pinagsunod-sunod na bahagi ng aming listahan mula kaliwa papuntang kanan, pinakamaliit na sa pinakamalaking. Upang gawin iyon, kailangan naming hanapin ang minimum unsorted elemento at ilagay ang mga ito sa dulo ng ang pinagsunod-sunod na bahagi. Dahil ang listahan na ito ay hindi pinagsunod-sunod, ang tanging paraan upang gawin iyon ay sa tumingin sa bawat elemento sa unsorted bahagi, pagtanda kung aling mga elemento ang pinakamababang at paghahambing sa bawat elemento na iyon. Kaya ipapakita muna namin tumingin sa 23. Ito ay ang unang elemento na nakakita kami, kaya namin tandaan ito bilang ang minimum. Susunod titingnan namin sa 42. 42 ay mas malaki kaysa sa 23, kaya 23 pa rin ang minimum. Susunod na 4 na mas mababa kaysa sa 23, kaya namin tandaan 4 bilang ang bagong minimum. Susunod ay 16 na mas malaki kaysa sa 4, kaya 4 ay pa rin ang minimum. 8 ay mas malaki kaysa sa 4, at 15 ay mas malaki kaysa sa 4, kaya 4 ay dapat na ang pinakamaliit na unsorted elemento. Kaya kahit na bilang tao agad naming makita na 4 ay ang minimum na elemento, ang aming mga algorithm ay kailangan upang tumingin sa bawat unsorted elemento, kahit pagkatapos namin natagpuan ang 4 - ang minimum na elemento. Kaya ngayon na nalaman namin na ang minimum na elemento, 4, makikita namin gusto upang ilipat ang mga ito sa ang pinagsunod-sunod na bahagi ng listahan. Dahil ito ay ang unang hakbang, ang ibig sabihin nito ay gusto naming ilagay ang 4 sa simula ng listahan. Sa ngayon 23 ay sa simula ng listahan, kaya sabihin magpalitan ng 4 at ang 23. Kaya ngayon ang aming listahan ay ganito ang hitsura. Alam namin na 4 ay dapat na sa huling lokasyon, sapagkat ito ay parehong pinakamaliit na elemento at ang mga elemento sa simula ng listahan. Kaya ay nangangahulugan ito na hindi namin kailanman kailangan upang ilipat ito muli. Kaya sabihin ulitin ang prosesong ito upang magdagdag ng isa pang elemento sa pinagsunod-sunod bahagi ng listahan. Alam namin na hindi namin kailangan upang tumingin sa 4, dahil ito ay na pinagsunod-sunod. Upang maaari naming magsimula sa 42, na makikita namin tandaan na rin ang minimum na elemento. Kaya susunod na titingnan namin sa 23 na mas mababa kaysa sa 42, kaya namin tandaan 23 ang bagong minimum. Susunod nakita namin ang 16 na mas mababa sa 23, kaya 16 ang bagong minimum. Ngayon namin tumingin sa 8 na mas mababa sa 16, kaya 8 ang bagong minimum. At sa wakas ay 8 ay mas mababa sa 15, kaya alam namin na 8 ay isang minimum unsorted elemento. Kaya na nangangahulugan na dapat naming ikabit ang 8 sa pinagsunod-sunod bahagi ng listahan. Sa ngayon 4 ay ang tanging na pinagsunod-sunod elemento, kaya gusto naming upang ilagay ang 8 susunod sa 4. Dahil 42 ang unang elemento sa unsorted bahagi ng listahan, makikita namin gusto swap sa 42 at ang 8. Kaya ngayon ang aming listahan ay ganito ang hitsura. 4 at 8 kumakatawan ang pinagsunod-sunod na bahagi ng listahan, at ang natitirang numero ay kumakatawan sa unsorted bahagi ng listahan. Kaya sabihin magpatuloy sa isa pang ulit. Magsisimula kami sa 23 oras na ito, dahil hindi namin kailangan upang tumingin sa ang 4 at ang 8 ito dahil na sila na ang pinagsunod-sunod. 16 ay mas mababa sa 23, kaya ipapakita namin tandaan 16 bilang bagong minimum. 16 ay mas mababa sa 42, ngunit 15 ay mas mababa sa 16, kaya 15 ay dapat na ang minimum unsorted elemento. Kaya ngayon gusto naming swap sa 15 at ang 23 sa bigyan kami ng listahang ito. Ang pinagsunod-sunod na bahagi ng listahan ay binubuo ng 4, 8 at 15, at pa rin ang mga elementong ito ay unsorted. Ngunit ito lang kaya ang mangyayari na ang susunod na unsorted elemento, 16, na pinagsunod-sunod. Gayunpaman, walang paraan para sa aming algorithm upang malaman na 16 ay nasa tamang lokasyon nito, kaya kailangan pa rin namin upang ulitin eksakto ang parehong proseso. Kaya naming makita na 16 ay mas mababa sa 42, at 16 ay mas mababa sa 23, kaya 16 dapat ang minimum na elemento. Imposibleng magpalitan elemento na ito na may mismo, kaya kaya namin iwan lamang ito sa lokasyon na ito. Kaya kailangan namin ng isa pang pass ng aming algorithm. 42 ay mas malaki kaysa sa 23, kaya 23 ay dapat na ang minimum unsorted elemento. Sandaling namin swap sa 23 at ang 42, magtapos namin sa aming panghuling pinagsunod-sunod listahan - 4, 8, 15, 16, 23, 42. Alam namin na 42 ay dapat na sa tamang lugar dahil ito ang lamang elemento umalis, at na seleksyon-uuri. Natin ngayon gawing pormal ang aming algorithm na may ilang pseudocode. Sa linya ng isa, maaari naming makita na kailangan namin na isama ang sa paglipas ng bawat elemento ng listahan. Maliban sa huling elemento, dahil ang 1 elemento listahan pinagsunod-sunod. Sa ika-dalawang linya, namin isaalang-alang ang unang elemento ng unsorted bahagi ng listahan na ang minimum, tulad ng ginawa namin sa aming Halimbawa, kaya kami ay may isang bagay upang ihambing. Line tatlong nagsisimula ng pangalawang loop kung saan kami umulit sa paglipas ng bawat unsorted elemento. Alam namin na pagkatapos i iterations, ang pinagsunod-sunod na bahagi ng aming mga listahan ay dapat i elemento sa ito dahil sa bawat hakbang uri isang elemento. Kaya ang unang unsorted elemento ay dapat na sa posisyon i plus 1. Sa ika-apat na linya, ihambing namin ang kasalukuyang elemento sa minimum elemento na nasaksihan namin sa ngayon. Kung ang kasalukuyang elemento ay mas maliit kaysa sa minimum elemento, pagkatapos tandaan namin ang kasalukuyang elemento bilang bagong minimum sa linya limang. Sa wakas, sa linya anim at pitong, swap namin ang minimum elemento sa unang unsorted elemento, at dahil doon pagdagdag nito sa pinagsunod-sunod na bahagi ng listahan. Sa sandaling mayroon kami ng isang algorithm, isang mahalagang tanong sa magtanong ating sarili bilang programmer kung gaano katagal na? Ipapakita muna namin tanungin ang tanong kung gaano katagal aabutin para sa algorithm upang tumakbo sa ang pinakamasama kaso? Manariwa sa diwa kumakatawan namin ito tumatakbo oras na may malaking O pagtatanda. Upang matukoy ang minimum unsorted elemento, namin mahalagang ay upang ihambing ang bawat elemento sa listahan upang bawat iba pang mga elemento sa listahan. Intuitively, ito tunog tulad ng isang O ng n squared operasyon. Naghahanap sa aming pseudocode, kami ay mayroon ding isang loop na nested sa loob isa pang loop, na sa katunayan Mukhang isang O ng n squared operasyon. Gayunpaman, tandaan na hindi namin kailangan upang tumingin sa ibabaw ng buong listahan kapag tinutukoy ang minimum unsorted elemento? Sa sandaling alam namin na 4 ay pinagsunod-sunod, halimbawa, hindi namin ginawa kailangang tingnan itong muli. Kaya ito mas mababa ang oras? Para sa aming listahan ng haba 6, kailangan naming gumawa ng limang paghahambing para sa unang elemento, apat na mga paghahambing para sa ang pangalawang elemento, at iba pa. Iyon ay nangangahulugan na ang kabuuang bilang ng mga hakbang ay ang kabuuan ng ang mga integer mula sa 1 sa haba ng listahan minus 1. Maaari naming kumatawan ang mga ito gamit ang isang kabuuan. Hindi namin pumunta sa summations dito. Ngunit ito lumiliko ang kabuuan na ito ay katumbas sa n beses n minus 1 sa 2. O equivalently, n nakalapat sa 2 minus n paglipas ng 2. Kapag pakikipag-usap tungkol sa asymptotic runtime, ito n squared termino ay upang dominahin ito n termino. Kaya pagpili-uuri O n squared. Manariwa sa diwa na sa aming halimbawa, pagpili-uuri pa rin na kinakailangan upang suriin kung ang isang numero na ay na pinagsunod-sunod kinakailangan upang ililipat. Sa gayon ay nangangahulugan na kung tumakbo kami ng pagpili ng uri sa isang na pinagsunod-sunod listahan, nangangailangan ang parehong bilang ng mga hakbang habang ito gagawin kapag tumatakbo sa loob ng isang ganap na unsorted listahan. Kaya pagpili-uuri ay may pinakamahusay na pagganap ng kaso ng n squared, kung saan ay kumakatawan namin may wakas n squared. At na ito para sa pagpili-uuri. Isa lamang ng maraming mga algorithm ng aming makakaya gamitin upang pag-uri-uriin ang isang listahan. Ang pangalan ko ay Tommy, at ito ay cs50.