[TÓNLIST spila] 

DOUG LLOYD: Svo er innsetning konar annar algrím við getum notað til að raða fylki. Hugmyndin á bak við þetta reiknirit er að byggja flokkaður array þinn í stað, breytast þætti úr hvernig sem þú ferð, til að gera pláss. Þetta er aðeins öðruvísi frá vali tegund eða kúla tegund, til dæmis, þar við erum að stilla stöðum, þar sem við erum að gera skiptasamninga. 

Í þessu tilfelli sem við erum í raun og veru að gera er að renna þættir yfir, út af the vegur. Hvernig virkar þetta reiknirit vinna í sauðakóða? Jæja við skulum bara geðþótta segja að Fyrsti þátturinn í fylkinu er flokkaður. Við erum að byggja það í stað. 

Við ætlum að fara einn þáttur í einu og byggja það, og svo the fyrstur hlutur sem við sjáum er einn þáttur array. Og skilgreiningu, einn þáttur array er raðað. 

Þá munum við endurtaka þetta ferli until-- við munum endurtaka eftirfarandi ferli þar alla þá þætti eru flokkuð. Horfðu á næstu óflokkuðu frumefni og setja það inn í raðaða hluta, með því að færa þarf fjölda þætti út af the vegur. Vonandi þetta visualization mun hjálpa þér að sjá nákvæmlega hvað er fara á með innsetningu tagi. 

Svo aftur, hér er okkar allt Óflokkaður array, alla þá þætti fram í rauðu. Og við skulum fylgja skref sauðakóðanum. The fyrstur hlutur sem við gerum, er við köllum Fyrsti þátturinn í fylkinu, raðað. Þannig að við erum bara að segja fimm, þú ert nú flokkaður. 

Þá við skoðum næst Óflokkaður þáttur í fylkinu og við viljum að setja sem í raðaða hluta, með því að færa þætti yfir. Svo er tveir næsta Óflokkaður þáttur í fylkinu. Ljóst tilheyrir það áður en fimm, svo hvað við ætlum að gera er tegund af halda tvær hliðar fyrir annað, skipta fimm yfir, og þá setja tvo áður fimm, hvar á að ætti að fara. Og nú getum við sagt að tvö er raðað. 

Svo eins og þú geta sjá, höfum við bara svo langt horfði á tvo þætti fylkisins. Við höfum ekki litið á það hvíla á öllum, en við höfum fékk þessir tveir þættir raðað eftir Vegur breytast vélbúnaður. 

Þannig að við endurtaka ferlið aftur. Horfðu á næstu Óflokkaður þáttur, sem er eitt. Skulum halda að hliðar fyrir annað, skipta öllu yfir, og setja einn þar sem það ætti að fara. 

Aftur, enn, höfum við bara alltaf horfði á einn, tveir og fimm. Við vitum ekki hvað er að koma, en við höfum raðað þeim þremur þáttum. 

Næsta Óflokkaður þátturinn er þrír, þannig að við munum setja það til hliðar. Við munum skipta yfir það sem við þarf sem, í þetta sinn er ekki allt eins og í fyrri tvö tilvik, það er bara fimm. Og þá munum við standa þrjú í, milli tveggja og fimm. 

Six er næsta Óflokkaður þáttur til fylkisins. Og í raun sex er meiri en fimm, svo við gerum ekki einu sinni þurfa að gera allir swap. Við getum bara tittur sex rétt á að the endir af the flokkuð hluta. 

Loks, fjórir er Síðast Óflokkaður þáttur. Þannig að við munum setja það til hliðar, skipta yfir þætti sem við þurfum að skipta yfir, og þá setja fjögur þar sem það tilheyrir. Og nú líta, að við höfum svona af öllum þeim þáttum. Tilkynning með innsetningu raða, höfum vér ekki að fara fram og til baka yfir í fylkinu. Við fórum aðeins yfir fjölda einu sinni, og við færst hluti að við myndum nú þegar komið upp, í því skyni til að gera pláss fyrir nýja þætti. 

Svo er það versta dæmi með innsetningu tagi? Í versta tilfelli, array er í öfugri röð. Þú verður að skipta hvert N þætti upp á móti n stöðum, hvert einasta skipti sem við gera innsetningu. Það er mikið breytast. 

Í besta tilfelli, array er fullkomlega raðað. Og svoleiðis eins og það sem gerðist með fimm og sex í dæminu, þar sem við gátum bara tittur það á án þess að þurfa að gera allir breytast, við myndum í raun gert það. 

Ef þú ímynda sér að okkar array var einn til sex, við myndum byrja á því að lýsa einn er flokkaður. Two kemur eftir einn svo við getum bara segja, OK, vel einn og tveir eru flokkuð. Þrír kemur eftir tvö svo, OK, einn og tveir og þrír eru flokkuð. 

Við erum ekki að gera neinar skiptasamninga, við erum bara að færa þessa handahófskennt línu milli flokka og óflokkaðar sem við förum. Eins og í raun eins og við gerðum í dæminu, beygja þætti blár, eins og við halda áfram. Svo er það versta afturkreistingur, þá? Mundu, ef við þurfum að skipta hvert sem n þættir hugsanlega n stöðu, vonandi sem gefur þér hugmynd sem versta afturkreistingur er Big O n veldi. 

Ef array er fullkomlega raðað, allt sem við höfum til að gera er að líta á hvert einasta þáttur einu sinni, og þá erum við að gera. Svo í besta tilfelli, það er ómega n. 

Ég er Doug Lloyd. Þetta er CS50.