[Predvaja glasba] Doug LLOYD: Izbor vrste je algoritem, ki, kot bi lahko pričakovali, sortira niz elementov. In algoritem odpoklic je korak-po-korak set navodil za dokončanje naloge. 

V izboru razvrstite Osnovna ideja je ta, našli najmanjši neurejen element in ga dodate na koncu urejenem seznamu. Učinkovito, kaj to počne je graditi razporejene seznam, en element naenkrat. Ga zrušijo, da psevdokoda smo lahko navede ta algoritem takole, ponovite dokler Ni nesortirane elementi ostajajo. Iskanje po nerazvrščenih Podatki najti najmanjšo vrednost, nato zamenjali najmanjšo vrednost s Prvi element nerazvrščene dela. 

To lahko pomaga vizualizirati to, tako da je lahko pogled na to. Torej to, da trdijo, je razvrščeni nizi in sem jo označi z navedbo, da so vsi elementov so rdeče barve, jih še ni urejeno. To je celotna razvrščeni del matrike. 

Torej, pojdimo skozi korake Izbor nekako rešiti to matriko. Torej še enkrat, bova ponovila dokler ne ostane nobena nesortirane elementi. Mi boš iskanje po Podatki najti najmanjšo vrednost, in nato zamenjali to vrednost z Prvi element nerazvrščene dela. 

Zdaj, še enkrat, celotna matrika je razvrščen del. Vse rdeče elementi so razvrščeni. Torej iščemo skozi in najdemo najmanjšo vrednost. Začnemo na začetku, gremo do konca, smo ugotovili, najmanjša vrednost, eden. Torej, to je prvi del. In potem drugi del, zamenjajte te vrednosti z Prvi element nesortiranih strani ali prvi rdeče element. 

V tem primeru, da bi bila pet, zato smo zamenjali eno in pet. Ko smo to naredili, smo lahko vizualno videli, da smo jih preselil najmanjšo cenjen element matrike, da se na samem začetku. Učinkovito razvrščanje ta element. 

In tako bomo lahko dejansko potrjuje in navajajo, da eden, je razvrščen. In tako bomo navesti razvrščeni del naše paleto, ki jo barvanje je modra. 

Zdaj moramo samo še enkrat ponoviti postopek. Iščemo preko navadne gospodinjske delu array najti najmanjši element. V tem primeru je dva. 

Smo zamenjali, da s prvim element nerazvrščene dela. V tem primeru sta se zgodi tudi, da je Prvi element nerazvrščene dela. Tako smo zamenjali dve sama s seboj, ki je res samo pušča dva kje je, in to je urejeno. Nadaljevanje, iščemo skozi najti najmanjši element. To je tri. Smo jo zamenjali s prvim Element, ki je pet. In zdaj tri je razvrščen. 

Iščemo skozi še enkrat, in mi našli najmanjši element je štiri. Smo jo zamenjali s prvim elementom nesortirani del, in zdaj je štiri razporejene. 

Ugotovili smo, da je pet najmanjši element. Smo jo zamenjali s prvim element nerazvrščene dela. In zdaj pet je razvrščen. 

In potem končno, naše razvrščeni del sestoji z enim samim elementom zato iščemo skozi in smo ugotovili, da je šest najmanjša, in dejansko edini element. In potem lahko trdimo, da je to urejeno. In zdaj smo prešli našo paleto ne bi popolnoma Nerazvrščene v rdeči barvi, v celoti razporejene v modri barvi, z uporabo izbora vrste. 

Torej, kaj je najslabši možni scenarij tukaj? No, v absolutno najslabša primera, moramo pogledati čez vseh elementih array našli najmanjši neurejen element, in moramo ponoviti Ta proces n-krat. Enkrat za vsak element matrike ker le v tem algoritmu nekako en element v času. 

Kaj je najboljši scenarij? No, to je povsem enaka, kajne? Dejansko moramo vedno korak skozi vsak element matrike da bi potrdili, da je, Dejansko najmanjši element. 

Torej v najslabšem primeru runtime smo morali ponoviti postopek n-krat, enkrat za vsak n elementov. In v najboljšem scenariju, moramo, da storijo enako. 

Tako razmišljanje nazaj na naše računska zahtevnost toolbox, kaj misliš, da je najslabša Primer runtime za izbirni vrste? Kaj misliš, da je najboljša Primer runtime za izbirni vrste? 

Ali uganete, Big O n kvadrat, in Big Omega n kvadrat? Ti bi bilo prav. To so, v resnici, najslabša in najboljša primera run čas, za izbiro vrste. 

Sem Doug Lloyd. To je CS50.