[Powered by Google Translate] [Убацивања Сортирај] [Томми МацВиллиам] [Универзитет Харвард] [Ово је ЦС50.ТВ] Хајде да погледамо уметања врсте, алгоритам за узимање листу бројева и сортирање их. Алгоритам, сетите се, једноставно корак-по-корак процедура за остваривање задатка. Основна идеја која стоји иза убацивања врсте, јесте да поделите нашу листу на два дела, сортирано део и некласификовани део. 

На сваком кораку алгоритма, број се помера од некласификовани дела у сортираном делу док се на крају цела листа сортирана. Овде је листа од шест Унсортед бројева - 23, 42, 4, 16, 8, и 15. Пошто се ови бројеви нису сви у растућем редоследу, они несортиран. Пошто нисмо почели сортирање ипак, ми ћемо размотрити све шест елемената наше унсортед део. 

Када почнемо сортирање, ми ћемо ставити ове сортиране бројеве лево од њих. Дакле, почнимо са 23, први елемент у нашој листи. Ми још увек немамо никакве елементе у нашој сортираног дела, па хајде да једноставно сматрамо да је 23 почетак и крај нашег сортираног дела. Сада, наш сортирано део има један број, 23, и наша некласификовани порција има ових пет бројева. Хајде сада убаците следећи број у нашој некласификовани порцији, 42, у сортираном делу. 

Да бисте то урадили, морамо да упоредимо 42 до 23 - једини елемент у нашој сортираног дела до сада. Четрдесет два је већи од 23, тако да једноставно можете додати 42 до краја од сортираног дела листе. Сјајно! Сада је наш сортирано део има два елемента, а наша некласификовани порција има четири елемента. Дакле, хајде да пређемо на 4, следећи елемент у некласификовани дела. Па, где би то требало да буде постављен у сортираном делу? 

Запамтите, ми желимо да тај број у сортираном редоследу тако да наш сортирано део остаје правилно поредани у свим временима. Ако ми поставите 4 десно од 42, онда се наша листа ће бити ван реда. Дакле, хајде да наставимо здесна налево у нашем сортирања порцији. Као што смо напред, идемо померају сваки број доле место да би се направило места за нови број. Ок, 4 је такође мање од 23, тако да не можемо да га поставите овде било. Идемо на 23 прави једно место. 

То значи да бисмо желели да поставите 4 у први слот у сортираном делу. Обратите пажњу како се овај простор на листи је већ празна, јер смо се кретали сортиране елементе доле као да смо их срели. У реду. Дакле, ми смо на пола пута. Хајде да наставимо наш алгоритам убацивањем 16 у сортираном делу. Шеснаест је мање од 42, па хајде да смени је 42 са десне стране. Шеснаест је такође мање од 23, па хајде да се пребаце тај елемент. 

Сада, 16 је већи од 4. Дакле, изгледа да смо желели да убаците 16 између 4 и 23. Док се креће кроз сортираног део листе са десна на лево, 4 је први број видели смо да је мањи од броја покушавамо да убаците. Дакле, сада можемо да убаците 16 у овај празан слот, који, запамтите, ми смо створили померањем елемената у делу сортирања преко као што смо их срели. 

У реду. Сада имамо четири сортиране елементе и два унсортед елементе. Дакле, идемо на 8 у сортираном делу. Осам је мање од 42. Осам је мање од 23. И 8 је мање од 16. Али 8 је већи од 4. Дакле, ми смо желели да убаците 8 између 4 и 16 година. И сада имамо само још један елемент преостало сорт - од 15. Петнаест је мање од 42, Петнаест је мање од 23. И 15 је мање од 16. Али 15 је већа од 8 година. 

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

На линији 1, можемо видети да ћемо морати да прелазили преко сваки елемент у листи осим прве, од првог елемента у некласификовани делу ће једноставно постати први елемент у сортираном делу. На линијама 2 и 3, имамо праћење наше садашње место у некласификовани дела. Елемент представља број тренутно се креће у сортираном делу, и ј представља нашу индекс у некласификовани дела. 

На линији 4, ми смо итератинг кроз сортираног дела са десна на лево. Ми желимо да зауставимо итератинг једном елементу са леве стране нашег тренутног положаја је мање од елемента покушавамо да убаците. На линији 5, ми помера сваки елемент сусрећемо један простор са десне стране. На тај начин, ми ћемо имати јасну простора да убаци у кад нађемо први елемент мање од елемента смо у покрету. На линији 6, ми смо ажурирање наше бројач да настави да се креће лево кроз сортираног дела. Коначно, на линији 7, ми убацивање елемента у сортираном делу листе. 

Знамо да је у реду да убаците у положај ј, јер смо већ преселили елемент који се користи тамо један простор са десне стране. Запамтите, ми крећемо кроз сортираног део са десна на лево, али ми крећемо кроз некласификовани део слева на десно. У реду. Хајде сада да погледамо колико ради тај алгоритам узео. Прво ћемо се поставити питање колико је потребно за овај алгоритам да се приказују у најгорем случају. Подсетимо се да заступамо ову време рада са великим О нотацији. У циљу сортирали нашу листу, морали смо да прелазили преко елементе у некласификовани дела, и за сваки од тих елемената, потенцијално над свим елементима у сортираном делу. Интуитивно, ово звучи као О (н ^ 2) рада. 

Гледајући наше Псеудокод, имамо петљу угнежђену у другој петље, који је, заиста, звучи као О (н ^ 2) рада. Међутим, сортиран део листе не садржи комплетну листу до самог краја. Ипак, ми смо потенцијално могли убацити нови елемент на самом почетку сортираног дела на сваком итерација алгоритма, што значи да ћемо морати да погледамо сваки елемент тренутно у сортираном делу. Дакле, то значи да смо потенцијално могли направити једну компарацију за други елемент, два поређења за трећи елемент, и тако даље. Дакле, укупан број корака је збир бројева од 1 до дужине листе минус 1. Можемо представљају ово са збирно. 

Нећемо ићи у сумматионс овде, али се испоставило да је ова сума једнака н (н - 1) преко 2, што је еквивалентно н ^ 2/2 - н / 2. Када говоримо о асимптотско рунтиме, ово н ^ 2 Термин ће доминирати овом н мандат. Дакле, убацивање врста је велики О (н ^ 2). Шта ако смо без уметања врсте на већ сортиране листе. У том случају, можемо једноставно да се изгради сортирани део слева надесно. Дакле, ми смо само ћемо морати по налогу н корака. 

То значи да убацивање врста има најбоље перформансе случај н, које представљају са Ω (н). И то је то за убацивање врсте, само један од многих алгоритама можемо користити да сортирате листу. Моје име је Томи, а ово је ЦС50. [ЦС50.ТВ] Ох, не могу да престанем да једном када почне. Ох, то смо урадили - >> Бум!