[Мусиц плаиинг] 

Даг Ллоид: Дакле, убацивање врста је још један алгоритам можемо користити за сортирање низ. Идеја која стоји иза овог алгоритма је да се изгради свој сортирану низ у мјесту, пребацивање елементе из начин како идете, како би направили места. Ово је нешто другачија од одабира врсте или балон сорт, на пример, где ми прилагођавање локације, где правимо свопови. 

У овом случају оно што уствари раде је клизни елементи преко, ван пута. Како ово алгоритам рад у псеудокоду? Па хајде да кажем да је произвољно Први елемент низа се сортирају. Ми га граде на месту. 

Идемо један елемент у једном тренутку и граде га, тако да је прва ствар коју видимо је низ један елемент. И по дефиницији, један Елемент низ сортира. 

Онда ћемо поновити овај процес док-- ћемо поновити следећи процес док сви елементи су поредани. Поглед на следећем обичан елемент и убаците га у сортираног део, померањем потребног броја елемената од начина. Надам се да ово визуализација ће вам помоћи да видите шта је дешава са унесени врсте. 

Дакле, опет, ово је наш Читав низ мусиц, све елементе наведено у црвено. И да пратите кораци наше псеудокоду. Прва ствар коју радимо, је зовемо Први елемент низа, поредани. Дакле, ми смо само да рецимо пет, ви сада поредани. 

Онда погледате следећи мусиц елемент низа и желимо да убаците да у сортирани део, померањем елемената преко. Дакле, два је следећа мусиц елемент низа. Јасно припада пре пет, па шта ћемо урадити је врста држите два одвојена за секунду, схифт пет преко, а затим убаците два пре пет година, где треба да иде. И сада можемо рећи да су две сортира. 

Дакле, као што видите, имамо само сам до сада Погледао два елемента низа. Ми нисмо погледали рест уопште, али смо добио та два елемента поредани према начин померање механизма. 

Тако смо поновите поступак поново. Погледајте следећи мусиц елеменат, то је један. Хајде да сматрају да страну на секунд, схифт све преко, и стави један где је требало да иде. 

Опет, ипак, само смо икада погледао један, два и пет. Ми не знамо шта друго долази, али смо поредани та три елемента. 

Следећа мусиц елемент је три, па ћемо га издваја. Ми ћемо схифт над оним што требају којој, овај пут није све као у претходна два случаја, то је само пет. А онда ћемо остати у три, између два и пет. 

Шест је следећи мусиц елемент низа. И, у ствари шест је већа од пет, со ми ни не треба да урадите било премештају. Можемо само да прикаче шест право на крај сортирана дела. 

На крају, четири је прошле мусиц елемента. Тако ћемо га издвојила, мијења се у елементи треба да пређу преко, а затим ставите четири тамо где и припада. И сада изгледају, некако смо си од свих елемената. Обратите пажњу са убацивањем врста, нисмо имали да се вратим и назад преко низа. Ишли смо само преко низа једном, а ми померио ствари да смо већ би наишли, како да би се направио простор за нове елементе. 

Дакле, оно што је најгори случај сценарио са уметања врстом? У најгорем случају, низ је обрнутим редоследом. Морате да пребаци сваки од н елемената до н позицијама, сваки пут кад направити уметање. То је много мења. 

У најбољем случају, низ је савршено поредани. И нешто као што се догодило са пет и шест у примјеру, где бисмо могли да га тацк на без да уради било померање, ми у суштини би то. 

Ако замислите да је наш низ је био један кроз шест, да кренемо са стране проглашавајући једну сортира. Два долази након што је један тако да једноставно не могу кажу, у реду, добро један и два су поредани. Три долази после два тако, у реду, један и два и три су поредани. 

Нећемо било каквих замјену, ми смо Само креће ову произвољна граница између поредани и мусиц како идемо. Како ефикасно као што смо урадили у примеру, окретање елементе плаво, као што наставите. Дакле, оно што је најгори случај рунтиме, онда? Запамтите, ако морамо да пребаци сваки од се н елемената евентуално н позиција, надамо се да вам даје идеја да је најгори случај Рунтиме је Биг О од н на квадрат. 

Ако је низ савршено поредани, све што треба да урадите се погледати сваког елемента једном, а онда смо готови. Дакле, у најбољем случају, то је омега н. 

Ја сам Доуг Лојд. Ово је ЦС50.