>> [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.