[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.