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