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