[Daqq tal-mużika] Doug LLOYD: tip Għażla huwa algoritmu li, kif inti tista 'tistenna, xorta sett ta 'elementi. U recall algoritmu huwa sett pass-pass ta 'struzzjonijiet għal kompletar ta' dmir. 

Fl-għażla isolvi l- idea bażika hi din, isibu l-iżgħar element mhux magħżul u iżżidhiex mal-aħħar tal-lista Issortjat. Effettivament dak li dan ma huwa build lista magħżula, element wieħed kull darba. Breaking l-isfel għal pseudocode nistgħu jiddikjaraw dan algoritmu kif ġej, irrepeti dan sakemm ebda elementi mhux magħżula jibqgħu. Fittex permezz tal-mhux magħżul data biex isibu l-iżgħar valur, imbagħad tpartit l-iżgħar valur ma 'l- ewwel element tal-parti mhux magħżul. 

Hija tista 'tgħin biex Ħares dan, Mela ejja tagħti ħarsa lejn din. Allura dan, I jsostnu, huwa firxa magħżulin u stajt indika li billi jindika li l mill-elementi huma kkuluriti aħmar, dawn għadhom ma jintgħażlux. Dan huwa l-kollu parti mhux magħżul mill-firxa. 

Mela ejja jmorru permezz tal-passi ta ' sort għażla biex issolvi din array. Għalhekk għal darb'oħra, aħna qed irrepeti gonna sakemm ebda elementi mhux magħżula jibqgħu. Aħna tfittxija gonna permezz tal- data biex isibu l-iżgħar valur, u mbagħad tpartit dak il-valur ma 'l- ewwel element tal-parti mhux magħżul. 

Dritt issa, għal darb'oħra, l kollu firxa hija l-parti mhux magħżul. L-elementi kollha aħmar huma mhux magħżul. Allura aħna tfittxija permezz ta 'u insibu l-iżgħar valur. Nibdew fil-bidu, immorru l-għan, insibu l-iżgħar valur huwa, wieħed. Allura li l-parti waħda. U mbagħad parti tnejn, tpartit dak il-valur ma ' l-ewwel element tal-parti mhux magħżul, jew l-ewwel element aħmar. 

F'dan il-każ li jkun ħames, hekk aħna tpartit wieħed u ħamsa. Meta nagħmlu dan, nistgħu viżwalment tara li konna għamel il-iżgħar element vvalutati mill-firxa, il-bidu nett. Effettivament issortjar dak l-element. 

U hekk nistgħu tabilħaqq jikkonferma u jiddikjaraw li wieħed, huwa magħżul. U hekk aħna ser jindika l-porzjon magħżula tal array tagħna, billi kulur huwa ikħal. 

Issa aħna biss irrepeti l-proċess mill-ġdid. Aħna tfittxija permezz tal-parti mhux magħżul ta ' l-array biex isibu l-element iżgħar. F'dan il-każ, huwa tnejn. 

Aħna tpartit li l-ewwel element tad-naħa mhux magħżul. F'dan il-każ żewġ wkoll jiġri li jkun l-ewwel element tal-parti mhux magħżul. Allura aħna tpartit tnejn bil innifsu, li verament ftit tħalli tnejn fejn hi, u huwa magħżula. Kontinwa fuq, aħna tfittxija permezz biex isibu l-element iżgħar. Huwa tlieta. Aħna tpartit ma 'l-ewwel element, li huwa ħamsa. U issa tlieta huwa magħżul. 

Aħna tfittxija permezz-ġdid, u aħna isibu l-iżgħar element huwa erbgħa. Aħna tpartit ma 'l-ewwel element tal- parti mhux magħżul, u issa erbgħa huwa magħżul. 

Insibu li ħamsa l-iżgħar element. Aħna tpartit ma 'l-ewwel element tad-naħa mhux magħżul. U issa ħamsa huwa magħżul. 

U mbagħad fl-aħħar, tagħna parti mhux magħżul jikkonsisti ta 'ftit element wieħed, hekk aħna tfittex permezz u insibu li sitt huwa l- iżgħar, u fil-fatt, biss element. U allura nistgħu istat li huwa magħżul. U issa konna mixgħula firxa tagħna milli tkun kompletament mhux magħżul bl-aħmar, li mifthiema kompletament bil-blu, bl-użu sort għażla. 

Allura x'inhu l-agħar każ hawnhekk? Ukoll fl-agħar assoluta każ, irridu nħarsu fuq l-elementi kollha tal-firxa għal isibu l-iżgħar element mhux magħżul, u għandna jirrepetu dan il-proċess n darbiet. Darba għal kull element ta 'l-array għaliex aħna biss, f'dan algoritmu, sort element wieħed fi żmien. 

X'inhu l-aħjar xenarju? Ukoll huwa eżattament l-istess, id-dritt? Aħna attwalment ikollhom xorta pass permezz kull element wieħed ta 'l-array sabiex jikkonfermaw illi huwa, fil-fatt, l-iżgħar element. 

Allura l-runtime agħar każ, aħna għandhom jirrepetu proċess n drabi, darba għal kull wieħed mill-elementi n. U fil-aħjar xenarju, għandna nagħmlu l-istess. 

Allura taħseb lura għall tagħna toolbox kumplessità komputazzjoni, dak li inti taħseb hija l-agħar każ runtime għall tip ta 'għażla? What do you think huwa l-aħjar każ runtime għall tip ta 'għażla? 

Ridt raden Big O ta 'n kwadrat, u Big Omega ta n kwadrat? Youd tkun id-dritt. Dawk huma, fil-fatt, il- agħar każ u l-aħjar każ jibqa 'jiddekorri drabi, għal tip ta 'għażla. 

Jien Doug Lloyd. Dan huwa CS50.