[Powered by Google Translate] [Сартаванне зліццём] [Rob Боуден - Гарвардскі універсітэт] [Гэта CS50. - CS50.TV] Давайце пагаворым аб сартавання зліццём. Да гэтага часу вы бачылі пузырьковый сартавання, сартавання устаўкай, і выбар роду. Хоць я накшталт хвалі маёй рукой на тое, што я маю на ўвазе лепш, сартаванне зліццём звычайна працуе лепш, чым любы з гэтых 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. І мы зрабілі. Цяпер у нас ёсць адсартаваны спіс. Так, як хутка было гэта на самай справе? З тэхнічнага пункту гледжання, зліццё сартавання O (п § п), у той час як усе пузырьковый сартавання, сартавання устаўкай, і выбар роду з'яўляюцца O (N ²). На самай справе, як вы даведаецеся ў бліжэйшы час, вы не зможаце прыдумаць свайго роду , Што працуе лепш, чым O (п § п) у агульным выпадку. Зноў жа, не турбуйцеся аб гэтым вялікім пазначэнне O, калі вы яго яшчэ не бачыла. 

Проста ведаю, што гэта значыць, калі мы хочам, каб адсартаваць сапраўды вялікі спіс пузырьковый сартаванне, сартаванне устаўкай, і выбар роду патэнцыйна могуць прымаць значна даўжэй, чым сартаванне зліццём. Гэта не азначае, што сартаванне зліццём будзе хутчэй для ўсіх спісаў ці нават для любога адзіны спіс пад пэўны памер. Напрыклад, сартаванне устаўкай можа быць самы хуткі від для ўсіх спісаў менш, чым 5 элементаў. На практыцы, сартаванне зліццём, як правіла, хутчэй для спісаў як малыя, як 50 элементаў. 

Але гэтая дадатковая хуткасць не прыходзіць без цэны. У адрозненне ад іншых гатункаў, якія прымаюць спіс і змяніць спіс на месцы пакуль мы не атрымаем адсартаваны спіс, сартаванне зліццём неабходна дадатковае месца аб'яднаць 2 спісу разам. Мы не можам адразу выкарыстоўваць спісы, якія зліваюцца для захоўвання аб'яднанага спісу так як мы можам змяніць элементы, якія яшчэ павінны быць аб'яднаныя. Гэта прастора з'яўляецца трохі цэны, але гэта звычайна не з'яўляецца неабгрунтаваным. І вось менавіта для сартавання зліццём. 

Мяне клічуць Боб Боуден, і гэта CS50. [CS50.TV] - І выбар роду. [Смяецца] Ох, трэба прыняць гэта занадта, таму што я перайшоў, як я ўяўляў яго. Спіс злева. Гэта была памылка друку. [Абмоўлюся] я аблажаўся - [Смяецца] Я не ведаю, што -