[MUSIC nagpe-play] DOUG LLOYD: sort Selection ay isang algorithm na, bilang maaari mong asahan, masama ang isang hanay ng mga elemento. At algorithm recall ay isang step-by-step na set ng mga tagubilin para sa pagkumpleto ng isang gawain. 

Sa pagpili ayusin ang pangunahing ideya ay ito, hanapin ang pinakamaliit unsorted elemento at idagdag ito sa dulo ng pinagsunod-sunod na listahan. Mabisa kung ano ang nagagawa nito ay build isang pinagsunod-sunod na listahan, ang isang elemento sa isang pagkakataon. Paghiwa-hiwalayin ito down sa pseudocode maaari naming estado algorithm na ito ang mga sumusunod, ulitin ito hanggang mananatiling walang unsorted elemento. Maghanap sa pamamagitan ng unsorted data upang mahanap ang pinakamaliit na halaga, pagkatapos ay palitan ang pinakamaliit na halaga sa unang elemento ng unsorted bahagi. 

Ito ay maaaring makatulong upang maisalarawan ito, kaya tumagal ng isang pagtingin sa ito ipaalam. Kaya ito, iginigiit ko, ay isang unsorted array at na ako ipinahiwatig ito sa pamamagitan ng na nagpapahiwatig na ang lahat ng mga elemento ay kulay pula, ang mga ito ay hindi pa nakaayos. Ito ang buong unsorted bahagi ng array. 

Kaya sabihin pumunta sa pamamagitan ng mga hakbang ng pagpili-uuri-uri-uriin ang array. Kaya muli, hindi namin gonna ulitin hanggang mananatiling walang unsorted elemento. Humihingi kami ng gonna paghahanap sa pamamagitan ng data upang mahanap ang pinakamaliit na halaga, at pagkatapos ay magpalitan na halaga sa mga unang elemento ng unsorted bahagi. 

Sa ngayon, muli, ang buong array ay ang unsorted bahagi. Ang lahat ng mga pulang mga elemento ay unsorted. Kaya kami sa paghahanap sa pamamagitan ng at nakita namin na ang pinakamaliit na halaga. Simulan namin sa simula, pumunta kami sa dulo, nakita namin na ang pinakamaliit na halaga ay, isa. Kaya na ang bahagi ng isa. At pagkatapos ay ang dalawang bahagi, magpalit na halaga sa ang unang elemento ng unsorted bahagi, o ang unang red elemento. 

Sa kasong ito na magiging limang, para magpalit kami ng isa at lima. Kapag ginagawa namin ito, maaari naming biswal makita na hindi namin inilipat ang pinakamaliit na nagkakahalaga element ng array, sa napaka-simula. Epektibong pag-uuri na sangkap. 

At upang maaari naming katunayan magkaibigan at estado na ang isa, ay pinagsunod-sunod. At kaya makikita ipahiwatig namin ang pinagsunod-sunod na bahagi ng aming array, sa pamamagitan ng pangkulay ito asul. 

Ngayon kami ulitin lamang ang proseso muli. Kami ng paghahanap sa pamamagitan ng unsorted bahagi ng array upang mahanap ang pinakamaliit na elemento. Sa kasong ito, ito ay dalawa. 

Swap kami na sa unang elemento ng unsorted bahagi. Sa kasong ito dalawang din ang mangyayari sa ang unang elemento ng unsorted bahagi. So magpalit kami ng dalawang sa kanyang sarili, na kung saan ay talagang lamang dahon ng dalawang kung saan ito, at ito ay nakaayos. Ang pagpapatuloy sa, aming paghahanap sa pamamagitan ng upang mahanap ang pinakamaliit na elemento. Ito ay tatlong. Swap namin ito sa unang elemento, na kung saan ay limang. At ngayon tatlong ay pinagsunod-sunod. 

Kami ng paghahanap sa pamamagitan ng muli, at kami hanapin ang pinakamaliit na elemento ay apat. Swap namin ito sa unang elemento ng unsorted bahagi, at ngayon ay may apat na pinagsunod-sunod. 

Nakita namin na limang ay ang pinakamaliit na elemento. Swap namin ito sa unang elemento ng unsorted bahagi. At ngayon limang ay pinagsunod-sunod. 

At pagkatapos ay sa wakas, ang aming Binubuo unsorted bahagi na lamang ng isang solong elemento, kaya kami sa paghahanap sa pamamagitan ng at nakita namin na anim ay ang pinakamaliit, at sa katunayan, lamang ang element. At pagkatapos ay maaari naming estado na ito ay pinagsunod-sunod. At ngayon inililipat namin ang aming array mula sa pagiging lubos unsorted sa pula, sa ganap na pinagsunod-sunod sa asul, gamit pagpili-uuri. 

Kaya kung ano ang pinakamasama kaso sitwasyon dito? Well sa ganap na pinakamasama kaso, mayroon kaming upang tumingin sa paglipas ng ang lahat ng elemento ng array na hanapin ang pinakamaliit unsorted elemento, at kami ay may sa ulitin ang proseso na ito n ulit. Kapag para sa bawat elemento ng array dahil tayo lamang, sa algorithm na ito, sort ang isang elemento sa oras. 

Ano ang pinakamahusay na kaso sitwasyon? Well ito ay eksaktong pareho, di ba? Kami ay talagang may upang pa rin magbasa-basa sa bawat isang elemento ng array upang kumpirmahin na ito ay, sa katunayan, ang pinakamaliit na elemento. 

Kaya ang pinakamasama kaso runtime, namin kailangang ulitin ang isang proseso n beses, isang beses para sa bawat isa n elemento. At sa pinakamahusay na kaso sitwasyon, kami ay may sa gawin ang parehong. 

Kaya nag-iisip bumalik sa aming computational kumplikado toolbox, ano sa tingin mo ay ang pinakamasama kaso runtime para sa pagpili ng uri? Ano ang tingin mo ay ang pinakamahusay na kaso runtime para sa pagpili ng uri? 

Hulaan mo ba Big O ng n squared, at Big Omega ng n nakalapat? Gusto mong maging tama. Yaong mga, sa katunayan, ang pinakamasama kaso at pinakamahusay na run case beses, para sa pagpili-uuri. 

Ako Doug Lloyd. Ito ay CS50.