[Muusika mängib] 

DOUG LLOYD: Nii sisestamise sorteerida on teise algoritmi saame kasutada sortida massiivi. Mõte algoritm on ehitada oma sorteeritud massiiv kohale, minnes elemendid välja Muide, kui sa lähed, et teha ruumi. See on mõnevõrra erinev valikust omamoodi või mull sorteerida, näiteks siis, kui me reguleerides kohtades, kus me teeme vahetustehinguid. 

Sel juhul, mida me tegelikult tehes on liugelemendid üle, välja viis. Kuidas see algoritm töötada pseudokoodi? Noh olgem lihtsalt suvaliselt öelda, et Esimene osa massiiv on järjestatud. Me arendame oma kohale. 

Me läheme ühe elemendi korraga ja ehitada, ja nii esimene asi, mida me näha on üks element massiivi. Ja definitsiooni järgi üks element massiivi on järjestatud. 

Siis me korrata seda protsessi until-- me korrata järgmise protsessi kuni kõik elemendid on järjestatud. Vaata järgmise sorteerimata element ja pistke see sorteeritud osa, minnes vajalik arv elementide välja viis. Loodetavasti see visualiseerimine aitab teil näha, millised täpselt on toimub koos sisestamise omamoodi. 

Nii jälle, siin on meie Kogu sorteerimata massiiv, kõik elemendid punasega märgitud. Ja olgem järgi etappe meie pseudokoodi. Esimene asi, mida me teeme, on me nimetame Esimene element massiivi, järjestatud. Nii et me lihtsalt ütled viis, sa oled nüüd järjestatud. 

Siis me vaatame järgmise sorteerimata element massiivi ja me tahame lisada, et arvesse järjestatud osa, nihutades elementide üle. Nii kahe on järgmine sortimata element massiivi. On selge see kuulub enne viis, nii et mida me teeme on omamoodi hoidke kaks kõrvale teise, vahetustega viis üle ja seejärel sisestage kaks enne viit, kuhu peaks minema. Ja nüüd võib öelda, et kaks on järjestatud. 

Nii et nagu näete, me oleme ainult seni vaatasin kaks elementi massiivi. Me ei ole vaadanud puhata üldse, kuid me oleme sain need kaks elementi järjestatud vastavalt teed käiguvahetusmehhanism. 

Nii me korrata protsessi uuesti. Vaata järgmise sorteerimata element, mis on üks. Olgem hoida, et kõrvale teise, suhtumist kõigesse üle ja panid ühe kus see peaks minema. 

Jällegi, ikka oleme alles kunagi vaadeldi üks, kaks, ja viis. Me ei tea, mida veel on tulemas, kuid me oleme järjestatud need kolm elementi. 

Järgmine sorteerimata element on kolm, nii me pange kõrvale. Me minema üle, mida me vaja mis seekord ei ole kõik nagu eelmistes Kahel juhul on see lihtsalt viis. Ja siis me kinni kolm, Kahe ja viie. 

Kuus on järgmine sorteerimata element massiivi. Ja tegelikult kuue on rohkem kui viis, nii me isegi ei pea tegema muud vahetada. Me lihtsalt pühitakse kuus õigus edasi lõppu järjestatud portsjonina. 

Lõpuks nelja on viimase sorteerimata element. Nii me pange kõrvale, vajub elemendid peame minema üle, ja siis pane neli kuhu see kuulub. Ja nüüd vaatame, me oleme omamoodi kõiki elemente. Märka sisestamisega sorteerida, meil ei olnud minna edasi-tagasi üle massiivi. Me ainult läks kogu massiivi üks kord, ja me nihkunud asjad et me tahaks juba tekkinud, et et teha ruumi uutele elementidele. 

Mis siis halvimal juhul stsenaarium sisestamise omamoodi? Halvimal juhul massiiv on vastupidises järjekorras. Sa pead minema iga n elemendid kuni n seisukohti, iga kord, kui me teha sisestamist. See on palju nihutada. 

Parimal juhul massiiv on täiesti järjestatud. Ja omamoodi nagu juhtus viie ning kuus näiteks kus me võiks lihtsalt pühitakse see ilma teha käikudes, olime sisuliselt seda teha. 

Kui te kujutate ette, et meie massiiv oli üks läbi kuue, olime alustad kuulutatakse üks on järjestatud. Kaks on pärast üht nii saame lihtsalt öelda, OK, samuti üks ja kaks on järjestatud. Kolm tuleb pärast kaht nii, OK, üks ja kaks ja kolm on järjestatud. 

Me ei anna mingit vahetustehingud, me oleme lihtsalt liigub selle suvalise rea vahel sorteeritud ja sorteerimata nagu me minna. Nii tõhusalt kui me tegime näiteks keerates elemendid sinine, kui astume. Mis siis halvimal juhul runtime, siis? Pea meeles, kui me peame minema iga n võimalikest n seisukohti, loodetavasti see annab teile idee, et halvimal juhul runtime on Big O n ruudus. 

Kui massiiv on täiesti sorteeritud, kõik me peame tegema on vaadata iga element kord, ja siis me teinud. Nii et parimal juhul on omega n. 

Ma olen Doug Lloyd. See on CS50.