[Predvaja glasba] 

Doug LLOYD: Torej vstavljanje vrsta je še ena Algoritem lahko uporabimo za razvrščanje array. Ideja tega algoritma je, da zgraditi vaš urejen niz V mestu, ki preusmerja elemente iz tako kot greš, da bi naredili prostor. To je nekoliko drugačen od izbora vrste ali mehurček sortiranje, na primer, kadar smo prilagoditvi lokacije, kjer smo kar zamenjavami. 

V tem primeru, kaj smo pravzaprav šel je drsni elementi konec, iz poti. Kako ta algoritem delo v psevdokoda? No, kaj je samo arbitrarno pravijo, da je Prvi element matrike je razvrščen. Mi smo jo gradi na mestu. 

Mi boš šel en element naenkrat in graditi, zato je prva stvar, ki jo vidim je matrika ena element. In po definiciji, eno element matrike je razvrščen. 

Potem bomo ta postopek ponovite until-- bomo ponovili naslednji postopek dokler so razporejene vse elemente. Poglej naslednjo nesortirani elementa in ga vstavite v urejenem delu, s premikom zahtevanega števila elementov iz poti. Upajmo, da to vizualizacija vam bo pomagal videti, kaj je dogaja z vstavljanja vrste. 

Torej še enkrat, tu je naš Celotna nesortirani matrika, vse elemente, navedene v rdeči barvi. In naj sledijo koraki našega psevdokoda. Prva stvar, ki jo storite, se pravimo Prvi element matrike, razporejene. Tako smo si samo hotel reči pet, ste zdaj razporejene. 

Potem gledamo na naslednji neprebrani element matrike in želimo, da vstavite da v razvrščenih obrok, s premikanjem elementov konec. Torej, dva je naslednji neprebrani element matrike. Jasno je, da pripada pred pet, kaj bomo storili je nekako držite dve rezerviran za sekundo, premik pet čez, in nato vstavite dva pred petimi, kjer bi morala iti. In zdaj lahko rečemo, da je dva razporejene. 

Torej, kot lahko vidite, smo samo tako daleč pogledal na dveh elementih matrike. Nismo pogledal na počitek na vse, vendar smo dobil ta dva elementa razporejene po Tako mehanizma spreminjajočo. 

Tako smo še enkrat ponoviti postopek. Poglej naslednjo nerazvrščenih element, ki je ena. Oglejmo presodilo, da na stran za sekundo, premik vse več, in dal eno kjer bi morala iti. 

Again, vedno, smo jih le kdaj pogledal na eno, dve, pet. Ne vemo, kaj prihaja, vendar smo razporejene te tri elemente. 

Naslednji neprebrani element tri, tako da bomo ga razveljavi. Bomo premik nad tem, kaj smo morali ki tokrat ni vse tako kot v prejšnji dva primera, to je samo pet. In potem bomo držijo tri v, med dvema in petimi. 

Šest je naslednji neprebrani element v matriki. In v resnici je šest večja od pet, tako mi sploh ne potrebujete storiti vse swapping. Mi lahko samo prečenje šest desno na Konec razvrščeni odseka. 

Končno, štiri je zadnji neprebrani element. Torej ga bomo v prahi, premik preko elemente moramo premik več, in nato dal štiri, kamor spada. In zdaj poglej, ki smo jih nekako vseh elementov. Opazili z vstavljanjem razvrščanje, nismo imeli iti naprej in nazaj po matriki. Smo šli samo čez polja en čas, in smo premaknilo stvari da sva že srečali, da bi da bi naredili prostor za nove elemente. 

Torej, kaj je v najslabšem primeru Scenarij z vstavljanja vrste? V najslabšem primeru je Niz je v obratnem vrstnem redu. Moraš premik vsakega izmed n elementov do n položaje, vsak čas smo narediti vstavljanje. To je veliko premikajo. 

V najboljšem primeru Niz je popolnoma urejeno. In nekaj podobnega kar se je zgodilo s pet in šest ur na primer, kjer smo lahko samo prečenje ne da bi morali storiti vse prestavljanje, sva v bistvu to. 

Če si predstavljate, da je naš Niz je bil eden skozi šest, sva začnete z razglasitvi eno je razvrščen. Dva pride po enega, tako da lahko samo reči, OK, tudi ena in dve so razporejene. Tri pride po dveh tako, OK, ena in dva in tri so razporejene. 

Mi ne podaja nobenih zamenjav, smo Pravkar se gibljejo to samovoljno črto med razporejene in razvrščen kot gremo. Tako učinkovito, kot smo to storili v primeru, obrača elemente, modra, saj bomo nadaljevali. Torej, kaj je v najslabšem primeru runtime, potem? Ne pozabite, če bomo morali preusmeriti vsako je n elementov, ki bi n stališča, upajmo, da vam daje ideja, ki v najslabšem primeru runtime je Big O n kvadrat. 

Če array je popolnoma razporejene, vse, kar moramo storiti je pogled na vsak element enkrat, nato pa smo končali. Torej v najboljšem primeru, da je omega n. 

Sem Doug Lloyd. To je CS50.