>> [TÓNLIST spila]
DOUG LLOYD: Allt í lagi, svo kúla tegund er reiknirit
þú getur notað til að raða safn af þáttum.
Við skulum taka a líta á hvernig það virkar.
>> Meginhugmyndin að baki kúla tegund er þetta.
Við viljum almennt að færa hærra metin þættir yfirleitt til hægri,
og lækka metin þætti almennt til vinstri, eins og við búast.
Við viljum lægri hlutir að vera á upphaf og hærri hluti
að vera í lokin.
>> Hvernig gerum við þetta?
Jæja í sauðakóða kóða, við gætum sagt, við skulum
setja skiptasamning borðið til a non-núll gildi.
Við munum sjá hvers vegna við gerum það í annað.
Og þá erum við að endurtaka eftirfarandi ferli þar til skipti borðið er 0,
eða þar til við tökum enga skiptasamninga yfirleitt.
>> Endurstilla skipti í bága við 0 ef það er ekki nú þegar 0.
Þá líta á hvert par af samliggjandi þáttum.
Ef þessir tveir þættir eru ekki í röð, skipta þeim,
og bæta 1 til skiptasamnings borðið.
Ef þú ert að hugsa um þetta áður en þú sjón það,
eftir því að þetta mun færa lægri metin þættir vinstra
og hærra metin þætti til hægri, í raun að gera það sem við viljum gera,
sem er að fara að þeim hópum staka í þannig.
Við skulum sjón hvernig þetta getur litið með array okkar
sem við notuðum til að prófa út þessum reiknirit.
Við höfum óflokkuðu array hér aftur, gefið til kynna með alla þá þætti
vera í rauðu.
Og ég setti minn swap gegn til frábrugðnar núlli gildi.
Ég valdi geðþótta neikvæð 1-- það er ekki 0.
Við viljum að endurtaka þetta ferli þar til skipti borðið er 0.
Þetta er ástæða þess að ég setti skipti mitt gegn að sumir non-núll gildi,
því annars skipti gegn væri 0.
Við viljum ekki einu sinni að byrja að ferli reiknirit.
Svo aftur, are-- skrefin núllstilla skipti gegn
0, þá líta á hvert við hliðina par, og ef þeir eru út af röð,
skipta á þeim og bæta 1 að skipti borðið.
Svo skulum byrja þetta ferli.
Svo er það fyrsta sem við gerum við setjum skipti gegn 0,
og þá erum við að byrja að leita á hvers aðlægs pars.
>> Svo við byrjum fyrst að horfa á 5 og 2.
Sjáum við að þeir eru út af panta og svo við skipta þeim.
Og við bætum 1 við skipti borðið.
Svo nú er að skipta gegn okkar 1, og 2 og 5 hefur verið skipt.
Nú erum við að endurtaka ferlið aftur.
>> Við lítum á næsta aðliggjandi par, 5 og 1-- þeir eru líka út af röð,
svo við skipta á þeim og bæta 1 við skipti borðið.
Þá við skoðum 5 og 3.
Þeir eru í ólagi, svo við skipta þá og við bætum 1 við skipti borðið.
Þá við skoðum 5 og 6.
Þeir eru til, svo við gerum ekki raunverulega þarf að skipta neitt að þessu sinni.
Þá við skoðum 6 og 4.
Þeir eru einnig í ólagi, svo við skipta þá og við bætum 1 við skipti borðið.
>> Nú eftir hvað gerðist.
Við höfum flutt 6 alla leið til enda.
Svo í val tagi, ef þú hefur séð að video, það sem við gerðum var
við enduðum hreyfa Minnsta þættir í húsinu
raðaða array meginatriðum frá vinstri til hægri, smæstu til stærstu.
Í tilviki kúla tagi, ef við erum Eftirfarandi þessari tilteknu reiknirit,
við erum í raun að fara að vera að byggja raðaða array frá hægri
til vinstri, stærsta til minnsta.
Við höfum í raun fara í loftbólum í 6, sem eru Stærsta gildi, alla leið til enda.
>> Og svo við getum nú lýsa að það er raðað,
og í framtíðinni iterations-- fara í gegnum array again--
við þurfum ekki að huga 6 lengur.
Við þurfum aðeins að íhuga að óflokkaðar þættir
þegar við erum að horfa á aðliggjandi pör.
Þannig að við höfum lokið einu fara í gegnum kúla tagi.
Svo nú erum við að fara aftur að spurningunni, Endurtakið þar til skipti teljarinn er 0.
Jæja skipti gegn er 4, þannig að við erum að fara
að halda að endurtaka þetta ferli aftur.
>> Við erum að fara að núllstilla skipti gegn 0, og líta á hvern aðliggjandi par.
Svo við byrjum með 2 og 1-- þeir eru út af röð, þannig að við skipta þeim
og við bætum 1 við skipti borðið.
2 og 3, þá eru þeir í röð.
Við þurfum ekki að gera neitt.
3 og 5 eru í röð.
Við þurfum ekki að gera neitt þar.
>> 5 og 4, eru þeir út þess, og svo við
þarf að skipta á þeim og bæta 1 við skipti borðið.
Og nú höfum við flutt 5, Næst stærsti þáttur,
til loka óflokkaðs hluta.
Svo við getum nú kalla það hluti af röðuðu hluta.
>> Nú þú ert að horfa á skjár og sennilega getur sagt,
eins get ég, að í fylkinu er raðað núna.
En við getum ekki sannað það enn.
Við höfum ekki trygging að það er flokkað.
En þetta er þar sem skipti gegn er að fara að koma inn í leik.
>> Þannig að við höfum lokið framhjá.
Skiptigengi Teljarinn er 2.
Þannig að við erum að fara að endurtaka þetta ferli aftur,
Endurtakið þar til skipti teljarinn er 0.
Núllstilla skipti gegn 0.
Þannig að við munum endurstilla það.
>> Nú líta á hvern aðliggjandi par.
Það er til, 1 og 2.
2 og 3 eru í röð.
3 og 4 eru í röð.
Svo á þessum tímapunkti, eftir að við höfum lokið leita á öllum aðliggjandi par,
en skipti borðið er enn 0.
>> Ef við þurfum ekki að skipta allir þættir, þá
verður að vera í röð, eftir samkvæmt þessari aðferð.
Og svo að skilvirkni konar, að við tölvunarfræðingar elska,
er að við getum nú lýsa Fylkið verður
vera flokkaður, vegna þess að við gerðum ekki að skipta þá hluta.
Það er nokkuð gott.
>> Svo er það versta dæmi með kúla tegund?
Í versta tilfelli fylki er í alveg öfugri röð,
og svo við verðum að kúla hver af stórum þáttum allt
leið yfir fylkisins.
Og við í raun einnig að kúla alla þá litlum þætti til baka
alla leið yfir í fylkinu, líka.
Svo hvert N þætti þarf að færa yfir alla aðra þætti n.
Svo er það versta falli.
Í besta tilfelli dæmi þó, þetta er
örlítið frábrugðið vali tagi.
The array er þegar flokkaður þegar við förum í.
Við þurfum ekki að gera eitthvað skiptasamninga á fyrstu umferð.
Þannig að við gætum þurft að líta á færri þætti, ekki satt?
Við þurfum ekki að endurtaka þetta vinna nokkrum sinnum yfir.
>> Svo hvað þýðir það?
Svo er það versta falli fyrir kúla tagi, og hvað er
Best Case atburðarás fyrir kúla tegund?
Vissir þú giska þetta?
Í versta tilfelli sem þú þarft að árétta yfir allar n þáttum n sinnum.
Svo versta er n veldi.
>> Ef array er fullkomlega Raðað þó aðeins þú
að líta á hvert af þeim þáttum einu sinni.
Og ef skipti borðið er enn 0, þú getur sagt þetta array er raðað.
Og svo í besta tilfelli, þetta er í raun betri en val
sort-- það er ómega n.
>> Ég er Doug Lloyd.
Þetta er CS50.