[TÓNLIST spila] DOUG LLOYD: Val tegund er reiknirit sem, eins og þú might búast við, skiptir að setja af þáttum. Og reiknirit muna er skref-fyrir-skref sett leiðbeiningar um að ljúka verkefni. 

Í vali raða Grunnhugmyndin er þetta, finna minnstu óflokkuðu frumefni og bæta því við lok raðaða listanum. Í raun hvað þetta gerir er að byggja raðað lista, einn þáttur í einu. Brjóta hann niður sauðakóðanum við gætum ríkisins þetta reiknirit eins og hér segir, endurtaka þetta þar til engar óflokkaðar þættir áfram. Leita gegnum Óflokkaður gögn til að finna minnstu gildi, þá skipta minnstu gildi með Fyrsti þátturinn af óflokkaðs hluta. 

Það getur hjálpað að sjón þessa, þannig að við skulum taka a líta á þetta. Svo, ég contend, er þetta Óflokkaður array og ég hef kynna það með því að tilgreina að allir af þeim þáttum eru lituð rauð, þeir eru ekki enn flokkaður. Þetta er allt Óflokkaður hluti fylkisins. 

Svo skulum við fara í gegnum skrefin val Raða til að raða þessu fylki. Svo aftur, við erum ađ endurtaka uns engar óflokkaðar þættir áfram. Við ætlum að leita í gegnum gögn til að finna minnstu gildi, og þá skipta þessi gildi með Fyrsti þátturinn af óflokkaðs hluta. 

Núna, aftur, allt array er Óflokkaður hluti. Alla rauða þættir eru Óflokkaður. Þannig að við leitað og finnum lægsta gildi. Við byrjum á byrjun, við förum til enda, finnum minnstu gildi er einn. Svo er það hluti einn. Og þá hluti tveir, skipta þessi gildi með fyrsti þátturinn í óflokkaðs hluta, eða fyrsta rauða þáttur. 

Í þessu tilfelli sem væri fimm, þannig að við skipta eitt og fimm. Þegar við gerum þetta, við getum sjónrænt sjá að við höfum flutti minnstu metin þáttur fylkisins, að upphafi. Í raun flokka sem þáttur. 

Og svo við getum örugglega staðfesta og ástand sem einn, er flokkað. Og svo við munum kynna raðaða hluta af array okkar, með því að lita það blátt. 

Nú erum við að endurtaka bara ferlið aftur. Við leit í gegnum óflokkuðu hluta array til að finna minnstu frumefni. Í þessu tilfelli, er það tveir. 

Við skipta að með fyrsta þáttur í óflokkaðs hluta. Í þessu tilfelli eru tveir gerist líka að vera fyrsti þátturinn í óflokkaðs hluta. Þannig að við skipta tvö með sér, sem í raun bara skilur tvö þar sem það er, og það er flokkað. Endurmenntun á, við leit í að finna minnstu frumefni. Það er þrjú. Við skipta um það með fyrsta þáttur, sem er fimm. Og nú þrjú er flokkaður. 

Við leit í gegnum aftur, og við finna minnstu þáttur er fjórir. Við skipta um það með fyrsta þáttur af Óflokkaður hluti, og nú fjögur er flokkaður. 

Við finnum að fimm er minnsti þáttur. Við skipta um það með fyrsta þáttur í óflokkaðs hluta. Og nú fimm er flokkaður. 

Og þá loks, okkar Óflokkaður hluti samanstendur af réttlátur a einn þáttur, svo við leitað í og við finnum að sex er minnsta, og í raun aðeins þáttur. Og þá getum við fram að það er flokkað. Og nú höfum við kveikt array okkar frá því að vera alveg óflokkuðu í rauðu, alveg flokkaður í bláum, með val konar. 

Svo er það versta falli hér? Jæja í alger versta ræða, verðum við að líta yfir alla þá þætti fylkisins til finna minnstu óflokkuðu frumefni, og við verðum að endurtaka Þetta ferli n sinnum. Einu sinni fyrir hvern hluta fylkisins vegna þess að við bara, í þessum reiknirit, tegund einn þáttur í einu. 

Hvað er besta falli? Jæja það er nákvæmlega það sama, ekki satt? Við höfum í raun að enn stíga í gegnum hvert einasta þáttur í fylkinu í því skyni að staðfesta að það er, í raun minnstu þáttur. 

Svo versta afturkreistingur, við að endurtaka ferli n sinnum, eina fyrir hvern N þætti. Og í besta falli, við verðum að gera það sama. 

Svo hugsa til baka til okkar computational flókið Verkfæri, hvað finnst þér er það versta Málið afturkreistingur fyrir vali tagi? Hvað finnst þér best Málið afturkreistingur fyrir vali tagi? 

Vissir þú giska Big O n veldi, og Big Omega n veldi? Þú vilt vera rétt. Þeir eru, í raun, versta og besta tilfelli hlaupa sinnum, fyrir val tagi. 

Ég er Doug Lloyd. Þetta er CS50.