[Powered by Google Translate] [Мерге Сорт] [Роб Бовден - Универзитет Харвард] [Ово је ЦС50. - ЦС50.ТВ] Хајде да причамо о стапања врсте. До сада сте видели балон врсте, уметања сортирате, а избор сортирања. Иако ћу некако таласа моју руку на шта мислим и боље, споји некако генерално обавља боље него било који од ова 3 врсте. 

Али пре него што говоримо о врсти стапања, хајде да разговарамо о спајању 2 сортиране листе. Ми ћемо позвати процес узимања 2 сортиране листе, као што су ови, и чинећи јединствену сортирани списак од њих - спајањем листе. Како можемо да урадимо ово? Па, једна од идеја је да се држимо само једну листу на крају друге листе а затим сортирати резултујућу листу. 

Док ово ради, то је много непотребног посла. Можемо то да урадимо брже него само сортирање. Приметите да један погрешан идеја је да се узме само наизменично шоље са сваке листе. Иако то може да изгледа као да радови на први поглед, радили да смо завршили са 4, 8, 15, 23, 16 - обавештења да је 16 и 23 су на месту. То је зато 2 елемента који би требало да се појављују узастопна у обједињеном листи у истој почетној листи. Оба 15 и 16 у листи са леве стране. Трик је у томе да се искористе чињеницу да су оба листа већ сортира. То значи да, ако погледамо на прве елементе обе листе - Овде, 4 и 8 - један од њих мора бити први елемент спојеног листе. Па, зашто је то тако? Обе листе су већ сортиран, па било 4 или 8 мора бити најмањи елеменат када комбинујемо 2 листа. У овом случају, најмања је 4, тако да можемо да изваде 4 и постане први елемент наше спојеном листе. Сада настављамо спајањем преостале 3 елемената прве листе и 4 елементи другој листи. 

Још једном, ми само треба да погледамо на првом елементу обе листе. Мањи од 2 мора бити Други елемент нашег спојеном листе. Овај пут, између 8 и 15 најмања је 8, па смо убацили да као други елемент нашег сортиране листе. Можемо да наставимо упоређујући прве елементе обе листе и отклањање мањих од 2. Упоређујући 15 и 23, 15 је мања па то је наш трећи елемент. Сада упоређујући 16 и 23, 16 је мањи. Дакле, то је четврти елемент. 

Приметимо да су 2 елемента дошао из исте листе за редом. То је разлог зашто обједињена листа не може само смењују елементи из 2 листа. Упоређујући 50 и 23, 23 је мања, тако да бирамо. Између 50 и 42, 42 је мањи. Између 50 и 108, 50 је мањи. И, коначно, имамо само 108, тако да мора да иде на крају наше листе. Приметите да имамо лепу, сортиране листе. Сваки пут смо упоредили прва 2 елементе 2 листа ми смо били у стању да одреди следеће елемент спојеног листе. То значи да ако коначна листа садржи бројеве н, где је н овде је 8, онда морамо највике н поређења да се све те бројеве на правом месту. Такав алгоритам се каже да раде у линеарном времену, али не брините о томе овде. 

Користећи наш алгоритам за спајање, можемо направити брзо стапања сортирања алгоритам. Дакле, хајде да поново наше листе. Постоје 2 велике кораке у процесу стапања врсте. Прво, стално поделити листу куповима у пола док имамо гомилу листа са само 1 шоља у њима. Не брините ако листа садржи непаран број и не може да направи савршено чист рез између њих. Само произвољно одабрати која листа да укључи додатну шољу унутра Дакле, хајде да поделите ове листе. Сада имамо 2 листа. Сада имамо 4 листа. 

И сада имамо 8 листе са једним купу у свакој листи. Дакле, то је то за корак 1. За корак 2, ми смо у више наврата обједињавање пара листа помоћу стапања алгоритам смо научили раније. Спајање 108 и 15, завршимо са листе 15, 108. Спајање 50 и 4, завршимо са 4, 50. Спајање 8 и 42, можемо завршити са 8, 42. И спајањем 23 и 16, можемо завршити са 16, 23. Сада сви наши спискови су величине 2. Приметите да сваки од 4 листа је сортирана. 

Дакле, можемо почети поново спајање парова листама. Спајање 15 и 108 и 4 и 50 - Прво узми 4, затим 15, па на 50, затим 108. Спајање 8, 42 и 16, 23, прво узме 8, затим 16, затим 23, затим 42. Дакле, сада имамо само 2 листе величине 4, од којих је сваки сортирају. Дакле, сада смо споји ове 2 листе. Прво узмемо 4. Онда узмемо 8. Онда узмемо 15 и 16, затим 23, затим 42, затим 50, затим 108. И ми смо урадили. Ми сада имамо сортиран списак. Дакле, колико брзо је ово тачно? У техничком смислу, обједињавање врста је О (н лог н) док сви балон врсте, уметања сортирање и избор сортирање су О (н ²). У ствари, као што ћете ускоро научити, нећете бити у могућности да дођу до неке врсте које обавља боље од О (н лог н) у општем случају. Опет, не брините о овом великом О нотацији, ако нисте видели још. 

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

Али ово екстра брзине не долази без цене. За разлику од наших других врста, које узимају листу и измените листу у месту док не добијемо сортирани списак, обједињавања некако треба неки додатни простор заједно споји 2 листа. Ми не можемо одмах да користите листе које су стопљене за чување обједињену листу јер смо могли заменити елементе који још увек треба да се споје. Овај простор је мало цени, али то обично није неразуман. И то је то за стапања врсте. 

Моје име је Роб Бовден, а ово је ЦС50. [ЦС50.ТВ] - И избор врсте. [Смех] Ох, морам да претпоставим да се превише, јер сам се пребацио како сам представљајући га. Списак са леве стране. То је грешка у куцању. [Лапсус] Ја зезнуо - [Смех] Ја не знам шта је -