[Powered by Google Translate] [Vstavi Razvrsti] [Tommy MacWilliam] [Harvard University] [To je CS50.TV] Oglejmo si uredi vstavljanja, algoritem za sprejemanje seznam številk in njihovo razvrščanje. Algoritem, se spomnite, je le korak-po-korak, postopek za dokončanje opravila. Osnovna ideja neke vstavljanja, je razdeliti naš seznam na dva dela, razporejene del in del razvrščeni. 

Na vsakem koraku algoritma je preselil številka od nesortiranih dela na razvrščeni del dokler na koncu je urejen celoten seznam. Tu je seznam šestih nesortiranih številkami - 23, 42, 4, 16, 8, in 15. Ker so te številke niso vsi v naraščajočem vrstnem redu, oni so nesortirani. Ker še nismo začeli sortiranje še, bomo upoštevali vseh šestih prvin našega neurejen del. 

Ko smo začeli sortiranje, bomo dal te številke razporejeni na levi strani teh. Torej, začnimo z 23, prvi element v našem seznamu. Nimamo nobenih elementov, razvrščenih v našem delu še tako da je le 23 menijo, da je začetek in konec našega razvrščene dela. Zdaj je naša razporejene del ima eno številko, 23, in naša neprebrani del je teh pet številk. Pojdimo zdaj vstavite naslednjo številko v naši nesortiranih del, 42, razvrščenih v delu. 

To storite tako, bomo morali primerjati od 42 do 23 - edini element našega dela razvrščenih doslej. Dvainštirideset je večja od 23, tako da lahko preprosto dodate 42 do konca na izločen del seznama. Čudovito! Sedaj naš razporejene del ima dva elementa, in naš razvrščeni del ima štiri elemente. Torej, kaj je zdaj premakniti na 4, naslednji element v nesortiranih dela. Zato je treba, kadar je to postaviti v razvrščenih dela? 

Ne pozabite, da želimo, da se to število v urejenih da tako da naše razporejene delež ostaja pravilno razporejene v vsakem trenutku. Če želimo postaviti na 4 na desni strani 42, potem bo naš seznam lahko v okvari. Torej, kaj je še premika od desne proti levi v naši razvrščanja dela. Kot smo se, kaj je premik navzdol vsako številko, kjer bi naredili prostor za novo številko. Ok, 4 je prav tako manj kot 23, tako da ga ne moremo postaviti niti tukaj. Naj premakniti 23 pravi eno mesto. 

To pomeni, da bi radi, da se da 4 v prvo režo na razvrščeni dela. Obvestilo o tem, kako ta prostor na seznamu je bil že prazen, ker smo bili razporejeni elementi gibljejo tako, kot smo jih srečal. V redu. Torej smo na pol poti. Naj nadaljujemo algoritem, ki ga vstavite v 16 razvrščenih dela. Šestnajst je manj kot 42, tako da je prehod 42-desno. Šestnajst je manj kot 23, tako da je tudi ta element premika. 

Zdaj, 16 je več kot 4. Torej, izgleda, da bi radi, da vstavite 16 med 4 in 23 let. Medtem ko se skozi izločen del seznama, od desne proti levi, 4 je prva številka, ki smo jih videli, da je manjši od števila poskušamo vstaviti. Torej, zdaj bomo lahko vstavite 16 v to prazno režo, ki Zapomnite si, da smo ustvarili s premikanjem elementov v razvrščanja dela v kot smo jih srečal. 

V redu. Zdaj imamo štiri razporejeni elementi in 2 nesortirane elemente. Torej, kaj je premakniti 8 v razvrščenih dela. Osem je manj kot 42. Osem je manj kot 23. In 8 je manj kot 16. Ampak 8 je večja od 4. Torej, bi radi, da vstavite 8 med 4 in 16 let. In zdaj imamo samo eno levo element za razvrščanje - 15. Petnajst je manj kot 42, Petnajst manj kot 23. In 15 je manj kot 16. Ampak 15 je več kot 8. 

Torej, tukaj je, če želimo, da bo naš končni namestitev. In končamo. Nimamo več elementov v nesortiranih dela, in naš razporejene del je v pravilnem vrstnem redu. Številke so razvrščena od najmanjšega do največjega. Torej, vzemimo si nekaj psevdokod, ki opisuje ukrepe, sva izvedli. 

Na linijo 1, lahko vidimo, da bomo morali ponoviti čez vsak element na seznamu razen prvega, saj je prvi element v nesortiranih dela bodo preprosto postali Prvi element v razvrščenih dela. Na progah 2 in 3, smo sledenja naše sedanje mesto v nesortiranih dela. Element predstavlja število se trenutno gibljejo v razvrščeni dela, in j predstavlja naš indeks v nesortiranih dela. 

Na vrsti 4, smo ponavljanjem preko razvrščenih del od desne proti levi. Želimo ustaviti ponavljanjem, ko element na levi strani našega trenutnega položaja manj kot elementa, bomo poskušali vstaviti. V skladu 5, mi premikajo vsak element se srečamo eno mesto v desno. Na ta način bomo imeli prazen prostor za vstavitev v ko smo ugotovili, prvi del manj kot element selimo. Na vrsti 6, bomo posodobiti naš števec, bi se še naprej levo skozi razvrščene del. Končno na liniji 7, bomo vstavite element v izločen del seznama. 

Vemo, da je v redu, da vstavite j lega, ker smo se že preselili element, ki se uporablja za obstajal en prostor na desni. Ne pozabite, da smo se skozi izločen del od desne proti levi, vendar smo se skozi nesortiranih del leve proti desni. V redu. Pojdimo zdaj si oglejte, kako dolgo vožnjo, da je algoritem. Mi bomo najprej vprašati vprašanje, kako dolgo traja, da ta algoritem, da delujejo v najslabšem primeru. Spomnimo se, da smo predstavljajo ta čas delovanja z Big O zapisu. Za razvrščanje naš seznam, smo morali ponoviti čez elementov v nesortiranih dela, in za vsakega od teh elementov, lahko na vseh elementov razvrščenih dela. Intuitivno, to zveni kot O (n ^ 2) operacije. 

Če pogledamo na našem psevdokod, imamo zanko ugnezdena znotraj druge zanke, ki dejansko zveni kot O (n ^ 2) operacije. Vendar pa je razvrščenih del seznama ne vsebuje celoten seznam do konca. Kljub temu pa bi lahko potencialno vstaviti nov element na samem začetku razvrščeni dela na vsaki ponovitvi algoritem, kar pomeni, da bomo morali gledati na vsak element, ki je trenutno v razvrščenih dela. Torej, to pomeni, da bi lahko naredili eno primerjavo za drugi element, 2 primerjave za tretji element, in tako naprej. Tako se je skupno število korakov, je vsota števil od 1 do dolžine seznama minus 1. Mi lahko predstavlja to s seštevanjem. 

Mi ne bo šel v summations tukaj, vendar se je izkazalo, da je ta vsota enaka n (n - 1) več kot 2, kar je enako n ^ 2/2 - n / 2. Ko govorimo o asimptotične runtime, To n ^ 2 Izraz se bo prevladovala ta izraz n. Torej, vstavljanje vrsta je Big O (n ^ 2). Kaj, če bi tekel za vstavljanje vrste na že sortirane seznama. V tem primeru, bi enostavno vzpostaviti urejen del od leve proti desni. Torej se bomo morali le na vrstni red korakov n. 

To pomeni, da je vključitev vrsta ima najboljšem primeru uspešnosti n, ki jih zastopa v Ω (n). In to je to za razvrščanje vstavljanja, Samo lahko eden od mnogih algoritmov, ki jih uporabljamo za razvrščanje seznama. Moje ime je Tommy, in to je CS50. [CS50.TV] Oh, si ne more ustaviti, da, ko se začne. Oh, res je, da je - >> Boom!