[Powered by Google Translate] [Innskot Raða] [Tommy MacWilliam] [Harvard University] [Þetta er CS50.TV] Við skulum taka a líta á Innsetningarröðun, algrím til að taka lista yfir númer og flokkun þeirra. Reiknirit, muna, er einfaldlega skref-fyrir-skref aðferð til að ljúka verkefni. Grunnhugmyndin á bak við Innsetningarröðun, er að skipta lista okkar í tvo hluta, a raðað hluti og unsorted hluta. 

Í hvert skref reiknirit, er fjöldi flutt frá óflokkuðu hluta til raðað hluta þar til að lokum alla lista er raðað. Hér er listi af sex unsorted tölur - 23, 42, 4, 16, 8, og 15. Þar sem þessar tölur eru ekki allt í réttri röð, þá eru þeir Unsorted. Þar sem við höfum ekki byrjað flokkun enn, munum við íhuga öllum sex Elements óflokkuðu hluta okkar. 

Þegar við byrjum að flokkun, munum við setja þessar flokkuð númer vinstra megin við þá. Svo, við skulum byrja með 23, fyrsti þáttur í lista okkar. Við höfum engar þætti í raðaða hluta okkar enn, þannig að við skulum bara íhuga 23 til að byrja og enda á raðaða hluta okkar. Nú, raðað hluti okkar hefur eitt númer, 23, og Unsorted hluti okkar hefur þessar fimm tölur. Við skulum nú setja næsta númer í óflokkuðum hluta okkar, 42, í raðaða hluta. 

Til að gera það, munum við þurfa að bera 42 til 23 - eina þáttur í raðaða hluta okkar svo langt. Fjörutíu og tveir eru stærri en 23, svo við getum einfaldlega auka 42 til enda á raðaða hluta á listanum. Great! Nú hefur raðað hluti okkar tvo þætti, og unsorted hluti okkar hefur fjóra þætti. Svo skulum við nú fara á 4, næsti þáttur í óflokkuðu hluta. Svo, þar ætti þetta að vera sett í raðaða hluta? 

Mundu, við viljum að setja þessa tölu í raðað röð svo er raðað hluti okkar rétt raðað á öllum tímum. Ef við setja 4 til hægri um 42, þá lista okkar mun vera út af röð. Svo skulum við halda áfram að færa hægri til vinstri í hluta röðun okkar. Eins og við flutt, við skulum færa hvern tala niður stað til að gera pláss fyrir nýja númerið. Jæja, 4 er einnig minna en 23, svo við getum ekki sett það hér heldur. Við skulum færa 23 rétta stað. 

Það þýðir að við viljum að setja 4 í fyrsta rifa í raðaða hluta. Taktu eftir hvernig þetta rúm á listanum var þegar tóm, vegna þess að við höfum verið að færa flokkuð þætti niður eins og við höfum upp þá. Allt í lagi. Svo erum við komin með það. Við skulum halda áfram reiknirit okkar með því að setja 16 í raðaða hluta. Sextán er minna en 42, þannig að við skulum færa 42 til hægri. Sextán er einnig minna en 23, þannig að við skulum einnig skipta þessi þáttur. 

Nú, 16 er meira en 4. Svo lítur það eins og við viljum að setja 16 milli 4 og 23. Þó að fara í gegnum raðaða hluta lista frá hægri til vinstri, 4 er fyrsta númerið sem við höfum séð að er minni en fjöldi við erum að reyna að setja inn. Svo nú getum við sett inn 16 í þessu tóma rifa, sem muna, höfum við búið til með því að færa atriði á röðun hluta yfir sem við höfum upp þá. 

Allt í lagi. Nú höfum við fjóra flokkuð þætti og tvo unsorted þætti. Svo skulum við færa 8 í raðaða hluta. Átta er minna en 42. Átta er minna en 23. Og 8 er minna en 16 ára. En 8 er meiri en 4. Svo viljum við gjarnan setja 8 milli 4 og 16 ára. Og nú höfum við bara einn þáttur til vinstri til að flokka - the 15. Fimmtán er minna en 42, Fimmtán er minna en 23. Og 15 er minna en 16 ára. En 15 er meiri en 8. 

Svo, hér er þar sem við viljum gera endanlega innsetningu okkar. Og við erum að gera. Við höfum ekki fleiri þætti í óflokkuðu hluta, og raðað hluti okkar er í réttri röð. Tölurnar eru pöntuð frá smæstu til stærstu. Svo skulum við taka a líta á sumir sauðakóðanum sem lýsir skref sem við gerðar rétt. 

Í línu 1, getum við séð að við munum þurfa að iterate yfir hvert frumefni á listanum nema fyrst, þar sem fyrsti þáttur í óflokkuðu hluta mun einfaldlega verða Fyrsti þátturinn í raðaða hluta. Á línum 2 og 3, erum við að halda utan um núverandi stað okkar í óflokkuðu hluta. Element táknar fjölda við erum nú að flytja inn í raðaða hluta, og j táknar vísitölu okkar í óflokkuðu hluta. 

Á línu 4, við erum iterating gegnum raðaða hluta frá hægri til vinstri. Við viljum hætta iterating einu frumefni til vinstri á núverandi stöðu okkar er minna en frumefni sem við erum að reyna að setja inn. Á línu 5, erum við að breytast í hvert frumefni við lendum eitt pláss til hægri. Þannig munum við hafa skýra pláss til að setja inn þegar við finnum í fyrsta frumefnið minna en frumefni sem við erum að flytja. On Line 6, við erum að uppfæra gegn okkar að halda áfram að færa til vinstri gegnum raðaða hluta. Að lokum, í línu 7, við erum að setja hluti inn í raðaða hluta á listanum. 

Við vitum að það er í lagi að setja inn j stöðu, vegna þess að við höfum nú þegar flutt þáttur sem er notað til að vera þar einn pláss til hægri. Mundu, við erum að fara í gegnum raðaða hluta frá hægri til vinstri, en við erum að fara í gegnum óflokkuðu hluta frá vinstri til hægri. Allt í lagi. Við skulum nú kíkja á hversu lengi í gangi að reiknirit tók. Við munum fyrst spyrja hversu langan tíma tekur það fyrir þetta reiknirit til að keyra í versta tilfelli. Muna að við komum þetta gangi tíma með Big O merki. Til að raða listanum okkar, áttum við að iterate yfir þá þætti í óflokkuðu hluta, og fyrir hvert af þessum þætti, hugsanlega yfir alla þætti í raðaða hluta. Innsæi, þetta hljómar eins og O (n ^ 2) starfsemi. 

Þegar litið er á sauðakóðanum höfum við lykkju hreiður inni annað lykkju, sem reyndar hljómar, eins og O (n ^ 2) starfsemi. Hins vegar raðað hluti lista ekki innihalda alla lista þar til enda. Samt gætum við hugsanlega setja inn nýja hluti í upphafi raðaða hluta á hverjum endurtekning á reiknirit, sem þýðir að við myndum þurfa að líta á hvert frumefni sem nú eru í raðaða hluta. Svo, sem þýðir að við gætum hugsanlega gera einn samanburð í annað frumefni, tveir samanburð þriðja frumefni, og svo framvegis. Svo heildarfjölda skref er summan af heiltölur frá 1 til lengd listanum mínus 1. Við getum táknað þetta með samantekt. 

Við munum ekki fara inn summations hér, en það kemur í ljós að þessi samantekt er jafnt n (n - 1) yfir 2, sem jafngildir N ^ 2/2 - N / 2. Þegar rætt er um asymptotic afturkreistingur, This N ^ 2 tíma er að fara að ráða þessa n tíma. Svo insertion sort er Big O (n ^ 2). Hvað ef við hljóp insertion sort á þegar raðað lista. Í því tilviki, myndi við einfaldlega að byggja upp raðað hluta frá vinstri til hægri. Svo munum við bara þurfa á röð n skrefum. 

Það þýðir að insertion sort hefur best í frammistöðu n, sem við tákna með Ω (n). Og það er það fyrir Innsetningarröðun, bara einn af mörgum reiknirit sem við getum notað til að raða listanum. Mitt nafn er Tommy, og þetta er CS50. [CS50.TV] Ó, að þú getur ekki hætt að einu sinni byrjar það. Oh, gerði við það - >> Boom!