[SKAN MŪZIKA]
DAGS LOIDS: atlases kārtošana ir algoritms, kas, kā jūs varētu
sagaidīt, sakārto elementu kopu.
Un algoritma atsaukšana ir norādījumu kopums uzdevuma izpildei soli
pa solim.
Atlases kārtošanas pamatideja ir šāda – atrodiet mazāko nesakārtotu
elementu un pievienojiet to sakārtota saraksta beigās.
Tas efektīvi veido sakārtotu sarakstu, pa vienam elementam.
Sadalot to līdz pseidokodam, mēs varētu norādīt šo algoritmu šādi –
atkārtojiet to, līdz vairs nav nesakārtotu elementu.
Meklējiet nesakārtotos datos, lai atrastu mazāko vērtību, pēc tam
samainiet mazāko vērtību ar nesakārtotas daļas pirmo elementu.
Tas var palīdzēt to iztēloties, tāpēc apskatīsim to.
Tātad, es uzskatu, ka tas ir nesakārtotsmasīvs, un es to norādīju,
norādot, ka visi elementi ir iekrāsoti sarkanā krāsā, tie vēl nav
sakārtoti.
Šī ir visa nesakārtotamasīva daļa.
Tātad, veiksim atlases kārtošanas darbības, lai sakārtotu šo masīvu.
Tad atkal, mēs atkārtosim, līdz nepaliks nesakārtoti elementi.
Mēs meklēsim datos, lai atrastu mazāko vērtību, un pēc tam apmainīsim
šo vērtību ar pirmo nesakārtotas daļas elementu.
Šobrīd atkal viss masīvs ir nesakārtots.
Visi sarkanie elementi ir nesakārtoti.
Tāpēc mēs meklējam un atrodam mazāko vērtību.
Mēs sākam no sākuma, ejam līdz beigām, atrodam, ka mazākā vērtība ir
viens.
Tātad tā ir pirmā daļa.
Un pēc tam otrā daļa, nomainiet šo vērtību ar pirmo nesakārtotas
daļas elementu vai pirmo sarkanu elementu.
Šajā gadījumā tie būtu pieci, tāpēc mēs samainām vienu ar pieci.
Kad mēs to darām, mēs varam redzēt, ka esam pārvietojuši vismazāko
masīva elementu uz pašu sākumu.
Efektīvi sakārtojam šo elementu.
Un tāpēc mēs patiešām varam apstiprināt un apgalvot, ka viens ir
sakārtots.
Un tāpēc mēs norādīsim mūsu masīva sakārtotu daļu, iekrāsojot to zilā
krāsā.
Tagad mēs vienkārši atkārtojam procesu vēlreiz.
Mēs meklējam masīva nesakārtotā daļā, lai atrastu mazāko elementu.
Šajā gadījumā tie ir divi.
Mēs to nomainām arnesakārtotas daļas pirmo elementu.
Šajā gadījumā divi arī ir pirmais nesakārtotas daļas elements.
Tāpēc mēs apmainām divi ar divi, kas faktiski tikai atstāj elementu
divi, kur tas ir, un tas tiek sakārtots.
Turpinot, mēs meklējam, lai atrastu mazāko elementu.
Tas ir trīs.
Mēs to apmainām ar pirmo elementu, kas ir pieci.
Un tagad elements trīs ir sakārtots.
Mēs pārmeklējam vēlreiz, un atklājam, ka mazākais elements ir četri.
Mēs to apmainām ar pirmo nesakārtotas daļas elementu, un tagad
elements četri ir sakārtots.
Mēs atklājam, ka pieci ir mazākais elements.
Mēs to samainām ar nešķirotās daļas pirmo elementu.
Un tagad pieci ir sakārtots.
Un visbeidzot, mūsu nesakārtota daļa sastāv tikai no viena elementa,
tāpēc mēs pārmeklējam un atklājam, ka seši ir mazākais un faktiski
vienīgais elements.
Un tad mēs varam paziņot, ka tas ir sakārtots.
Un tagad mēs esam pārveidojuši savu masīvu no pilnīgi nesakārtota
sarkanā krāsā uz pilnībā sakārtotu zilā krāsā, izmantojot atlases
kārtošanu.
Tātad, kāds šeit ir sliktākais scenārijs?
Absolūti sliktākajā gadījumā mums ir jāpārskata visi masīva elementi,
lai atrastu mazāko nesakārtotu elementu, un mums šis process ir
jāatkārto n reizes.
Vienu reizi katram masīva elementam, jo šajā algoritmā mēs vienlaikus
kārtojam tikai vienu elementu.
Kāds ir labākais scenārijs?
Nu, tas ir tieši tas pats, vai ne?
Mums faktiski joprojām ir jāiet cauri katram masīva elementam, lai
pārliecinātos, ka tas patiesībā ir mazākais elements.
Tātad vissliktākajā gadījumā mums ir jāatkārto process n reizes,
vienu reizi katram n elementam.
Un labākajā gadījumā mums ir jādara tas pats.
Tātad, atskatoties uz mūsu skaitļošanas sarežģītības rīklodziņu,
kāds, jūsuprāt, ir sliktākais atlases kārtošanas izpildlaiks?
Kāds, jūsuprāt, ir labākais atlases kārtošanas izpildlaiks?
Vai domājāt par lielo O no n kvadrātā un lielo Omega no n kvadrātā?
Tad Jums būtu taisnība.
Patiesībā tie ir atlases kārtošanas izpildlaiki sliktākajā un
labākajā gadījumos.
Es esmu Dags Loids.
Šis ir CS50.