[Powered by Google Translate] Tommy: Ejja tagħti ħarsa lejn it-tip ta 'għażla, algoriżmu għat-teħid ta 'lista ta' numri u l-għażla tagħhom. Algoritmu, ftakar, huwa sempliċement pass-pass proċedura għall-kisba ta 'kompitu. L-idea bażika wara sort għażla huwa li jaqsam lista tagħna f'żewġ porzjonijiet - porzjon magħżula u porzjon mhux magħżul. F'kull pass ta 'l-algoritmu, numru jiġi mċaqlaq mill- porzjon mhux magħżul għall-porzjon magħżul sakemm eventwalment l- lista sħiħa qed magħżula. Allura hawnhekk lista ta 'sitt numri - 23, 42, 4, 16, 8, u 15. Dritt issa l-lista sħiħa hija kkunsidrata mhux magħżul. Anke jekk numru simili 16 tista 'tkun diġà fil korretta tagħha lokalità, algoritmu tagħna m'għandha l-ebda mod sabiex tkun taf li sakemm l- lista sħiħa qed magħżula. Allura aħna ser jikkunsidraw kull numru li għandu mhux magħżul sakemm aħna issolvi dan lilna nfusna. Aħna nafu li aħna rridu l-lista li tkun f'ordni axxendenti. Allura aħna ser jridu jibnu l-porzjon magħżula ta 'lista tagħna mix-xellug għal-lemin, iżgħar għall-akbar. Biex tagħmel dan, aħna ser bżonn issib l-element mhux magħżul minimu u poġġih fl-aħħar tal-porzjon magħżul. Peress li din il-lista ma jintgħażlux, l-uniku mod biex tagħmel dan huwa li tħares lejn kull element fil-porzjon mhux magħżul, ftakar li l-element huwa l-aktar baxx u t-tqabbil kull element għal dan. Allura aħna ser ewwel tħares lejn il-23. Dan huwa l-ewwel element Rajna, hekk aħna ser tiftakar bħala l-minimu. Li jmiss aħna ser tħares lejn 42. 42 hija akbar minn 23, hekk 23 għadha l-minimu. Li jmiss huwa l-4 li huwa inqas minn 23, hekk aħna ser tiftakar 4 bħala l-minimu l-ġdid. Li jmiss huwa 16 li hija akbar minn 4, hekk 4 għadu l-minimu. 8 hija akbar minn 4, u 15 hija akbar minn 4, hekk 4 għandhom ikunu l-element mhux magħżul iżgħar. Allura anke jekk bħala bnedmin nistgħu immedjatament tara li 4 huwa l-element minimu, algoritmu tagħna teħtieġ li tħares lejn kull element mhux magħżul, anki wara konna sabet 4 - l- minimu element. Allura issa li aħna ħadthom misjuba-element minimu, 4, aħna ser rridu li jġorrhom fil-porzjon magħżula tal-lista. Peress li dan huwa l-ewwel pass, dan ifisser li rridu li tqiegħed 4 fi il-bidu tal-lista. Dritt issa 23 huwa fil-bidu tal-lista, sabiex ejja tpartit l-4 u l-23. Allura issa lista tagħna tidher bħal dan. Aħna nafu li 4 għandu jkun fil-post finali tagħha, minħabba li hija kemm l-element iżgħar u l-element fil-bidu tal-lista. Allura dan ifisser li aħna ma qatt ħtieġa li jġorrhom mill-ġdid. Mela ejja irrepeti dan il-proċess biex iżżid element ieħor għall- porzjon magħżula tal-lista. Aħna nafu li aħna ma bżonn li nħarsu lejn il-4, għaliex dan huwa diġà magħżula. Allura nistgħu tibda fil-42, li aħna ser tiftakar bħala l- minimu element. Allura li jmiss aħna ser tħares lejn il-23 li hija inqas minn 42, hekk aħna tiftakar 23 huwa l-minimu ġdid. Li jmiss naraw il-16 li huwa anqas minn 23, hekk 16 huwa l-minimu ġdid. Issa aħna nħarsu lejn l-8 li hija inqas minn 16, hekk 8 hija l-minimu ġdid. U finalment 8 huwa anqas minn 15, hekk nafu li 8 huwa minimu mhux magħżul element. Allura dan ifisser li għandna jehmeż 8 għall-magħżula porzjon tal-lista. Dritt issa 4 huwa l-uniku element magħżula, hekk aħna tixtieq li ssir -li jmiss 8 għall-4. Peress 42 huwa l-ewwel element fil-porzjon mhux magħżul tal- lista, aħna ser tixtieq li tpartit l-42 u l-8. Allura issa lista tagħna tidher bħal dan. 4 u 8 jirrappreżentaw il-porzjon magħżula tal-lista, u l- numri li jifdal jirrappreżentaw l-mhux magħżul porzjon tal-lista. Mela ejja tkompli ma 'iterazzjoni. Nibdew bl 23 dan iż-żmien, peress li aħna ma bżonn li nħarsu lejn l-4 u l-8 jibqgħalu għaliex stajt diġà ġew magħżula. 16 huwa anqas minn 23, hekk aħna ser tiftakar 16, kif l-minimu ġdid. 16 huwa anqas minn 42, iżda 15 hija anqas minn 16, u għalhekk 15 għandu jkun l-element mhux magħżul minimu. Allura issa irridu li tpartit l-15 u l-23 sa agħtina din il-lista. Il-porzjon magħżula tal-lista tikkonsisti minn 4, 8 u 15, u dawn l-elementi għadhom mhux magħżula. Iżda huwa biss hekk jiġri li l-element mhux magħżul li jmiss, 16, huwa diġà magħżula. Madankollu, hemm ebda mod biex algoritmu tagħna jkunu jafu li 16 hija diġà fil-post korretta tagħha, hekk aħna għad iridu irrepeti eżattament l-istess proċess. Allura naraw li 16 hija inqas minn 42, u 16 huwa anqas minn 23, hekk 16 għandha tkun l-element minimu. Huwa impossibbli li tpartit dan l-element ma innifsu, sabiex inkunu nistgħu sempliċiment jitilqu minnu f'dan il-post. Għalhekk għandna bżonn pass wieħed aktar ta 'algoritmu tagħna. 42 huwa akbar minn 23, u għalhekk 23 għandu jkun il- element mhux magħżul minimu. Ladarba aħna tpartit l-23 u l-42, aħna jispiċċaw ma 'finali tagħna magħżula lista - 4, 8, 15, 16, 23, 42. Nafu 42 għandu jkun fil-post korretta peress li huwa l- uniku element xellug, u li sort għażla. Ejja issa jifformalizza algoritmu tagħna ma 'xi pseudocode. Fuq linja waħda, nistgħu naraw li għandna bżonn li jiġu integrati aktar kull element tal-lista. Ħlief l-aħħar element, peress li l-element 1 lista hija diġà magħżula. Fuq linja 2, inqisu li l-ewwel element tal-mhux magħżul porzjon tal-lista biex ikunu l-minimu, kif għamilna ma 'tagħna eżempju, hekk aħna ikollhom xi ħaġa li jqabblu. Linja 3 jibda loop 2 li aħna jtenni aktar kull element mhux magħżul. Aħna nafu li wara i iterazzjonijiet, l-magħżula porzjon tal-lista tagħna għandu jkollhom i elementi fiha mill f'kull pass xorta 1 elementi. Allura l-element mhux magħżul 1 għandhom ikunu f'pożizzjoni i plus 1. Fuq linja 4, inqabblu l-element attwali għall-minimu element li Rajna s'issa. Jekk l-element attwali hija iżgħar mill-minimu element, allura aħna niftakru l-element kurrenti bħala l-ġdid minimu fuq linja 5. Fl-aħħarnett, fuq il-linji 6 u 7, aħna tpartit l-minimu element bl-element mhux magħżul l-ewwel, biex b'hekk żżidu mal-porzjon magħżula tal-lista. Ladarba għandna algoritmu, kwistjoni importanti li titlob ruħna bħala programmaturi huwa kemm ma dan jieħu? Aħna ser ewwel titlob il-kwistjoni kemm żmien ma jieħdu għal dan algoritmu jiddekorri fl-agħar każ? Recall nirrappreżentaw dan tmexxija ħin ma 'O notazzjoni kbar. Sabiex jiġi ddeterminat l-element mhux magħżul minimu, aħna essenzjalment kellhom iqabblu kull element fil-lista biex kull element ieħor fil-lista. Intuwittivament, dan ħsejjes bħal O ta 'n-operazzjoni kwadru. Ħarsa lejn pseudocode tagħna, aħna għandna wkoll loop nested ġewwa ieħor loop, li tabilħaqq tinstema 'O ta 'operazzjoni n kwadru. Madankollu, ftakar li aħna ma bżonn li tħares fuq il- lista sħiħa meta jiġi ddeterminat l-element mhux magħżul minimu? Ladarba aħna kien jaf li l-4 kien magħżul, per eżempju, aħna ma bżonn li nħarsu lejn din darb'oħra. Allura ma dan jbaxxu l-running time? Għal-lista tagħna ta 'tul 6, aħna meħtieġa biex jagħmlu 5 paraguni għall-ewwel element, erba paraguni għall it-tieni element, u l-bqija. Dan ifisser li n-numru totali ta 'passi huwa s-somma ta' l-interi minn 1 sa t-tul tal-lista minus 1. Nistgħu jirrappreżentaw dan bil-kalkolu totali. Aħna mhux se tidħol fis ammonti totali hawnhekk. Iżda jirriżulta li din l-addizzjoni hija ugwali għal n darbiet n minus 1 minn 2. Jew ekwivalenti, n kwadrat aktar minn 2 minus n aktar minn 2. Meta wieħed jitkellem dwar runtime asintotiku, dan it-terminu kwadrat n se jiddominaw dan it-terminu n. Allura xorta għażla hija O ta 'n kwadru. Ifakkar li fl-eżempju tagħna, sort għażla għad hemm bżonn li jiċċekkjaw jekk numru li kien diġà mifthiema meħtieġa biex jiġu mċaqalqa. Allura dan ifisser li jekk aħna dam tip ta 'għażla matul diġà magħżula lista, ikun jeħtieġ l-istess numru ta 'passi kif kieku waqt il-ġiri fuq lista kompletament mhux magħżul. Allura xorta għażla għandu prestazzjoni aħjar każ ta 'n kwadrat, li nirrappreżentaw mal omega n kwadru. U li hija għal tip ta 'għażla. Just wieħed mill-algoritmi ħafna nistgħu tuża biex issolvi lista. Jisimni Tommy, u dan huwa cs50.