>> [Мусиц плаиинг]
>> Даг Ллоид: Дакле, убацивање врста је још један алгоритам можемо користити за сортирање низ.
Идеја која стоји иза овог алгоритма је да се изгради свој сортирану низ
у мјесту, пребацивање елементе из начин како идете, како би направили места.
Ово је нешто другачија од одабира врсте или балон
сорт, на пример, где ми прилагођавање локације,
где правимо свопови.
>> У овом случају оно што уствари раде је клизни елементи
преко, ван пута.
Како ово алгоритам рад у псеудокоду?
Па хајде да кажем да је произвољно Први елемент низа се сортирају.
Ми га граде на месту.
>> Идемо један елемент у једном тренутку и граде га, тако да је прва ствар коју видимо
је низ један елемент.
И по дефиницији, један Елемент низ сортира.
>> Онда ћемо поновити овај процес док-- ћемо поновити следећи процес
док сви елементи су поредани.
Поглед на следећем обичан елемент и убаците га у сортираног део,
померањем потребног броја елемената од начина.
Надам се да ово визуализација ће вам помоћи да видите шта је
дешава са унесени врсте.
>> Дакле, опет, ово је наш Читав низ мусиц,
све елементе наведено у црвено.
И да пратите кораци наше псеудокоду.
Прва ствар коју радимо, је зовемо Први елемент низа, поредани.
Дакле, ми смо само да рецимо пет, ви сада поредани.
>> Онда погледате следећи мусиц елемент низа
и желимо да убаците да у сортирани део,
померањем елемената преко.
Дакле, два је следећа мусиц елемент низа.
Јасно припада пре пет, па шта ћемо урадити
је врста држите два одвојена за секунду, схифт пет преко, а затим убаците два
пре пет година, где треба да иде.
И сада можемо рећи да су две сортира.
>> Дакле, као што видите, имамо само сам до сада Погледао два елемента низа.
Ми нисмо погледали рест уопште, али смо
добио та два елемента поредани према начин померање механизма.
>> Тако смо поновите поступак поново.
Погледајте следећи мусиц елеменат, то је један.
Хајде да сматрају да страну на секунд, схифт све преко, и стави један
где је требало да иде.
>> Опет, ипак, само смо икада погледао један, два и пет.
Ми не знамо шта друго долази, али смо поредани та три елемента.
>> Следећа мусиц елемент је три, па ћемо га издваја.
Ми ћемо схифт над оним што требају којој, овај пут
није све као у претходна два случаја, то је само пет.
А онда ћемо остати у три, између два и пет.
>> Шест је следећи мусиц елемент низа.
И, у ствари шест је већа од пет, со ми ни не треба да урадите било премештају.
Можемо само да прикаче шест право на крај сортирана дела.
>> На крају, четири је прошле мусиц елемента.
Тако ћемо га издвојила, мијења се у елементи треба да пређу преко,
а затим ставите четири тамо где и припада.
И сада изгледају, некако смо си од свих елемената.
Обратите пажњу са убацивањем врста, нисмо имали
да се вратим и назад преко низа.
Ишли смо само преко низа једном, а ми померио ствари
да смо већ би наишли, како да би се направио простор за нове елементе.
>> Дакле, оно што је најгори случај сценарио са уметања врстом?
У најгорем случају, низ је обрнутим редоследом.
Морате да пребаци сваки од н елемената до н позицијама, сваки пут кад
направити уметање.
То је много мења.
>> У најбољем случају, низ је савршено поредани.
И нешто као што се догодило са пет и шест у примјеру,
где бисмо могли да га тацк на без да уради било померање,
ми у суштини би то.
>> Ако замислите да је наш низ је био један кроз шест,
да кренемо са стране проглашавајући једну сортира.
Два долази након што је један тако да једноставно не могу кажу, у реду, добро један и два су поредани.
Три долази после два тако, у реду, један и два и три су поредани.
>> Нећемо било каквих замјену, ми смо Само креће ову произвољна граница
између поредани и мусиц како идемо.
Како ефикасно као што смо урадили у примеру, окретање елементе плаво, као што наставите.
Дакле, оно што је најгори случај рунтиме, онда?
Запамтите, ако морамо да пребаци сваки од се н елемената евентуално н позиција,
надамо се да вам даје идеја да је најгори случај
Рунтиме је Биг О од н на квадрат.
>> Ако је низ савршено поредани, све што треба да урадите
се погледати сваког елемента једном, а онда смо готови.
Дакле, у најбољем случају, то је омега н.
>> Ја сам Доуг Лојд.
Ово је ЦС50.