СПІКЕР 1: Прывітанне ўсім! Сардэчна запрашаем у профіль. Так рада, што так многія з вас як тут, і кожны, хто глядзіць онлайн. Так, як звычайна Сардэчна запрашаем. Я спадзяюся, што вы ўсё былі выдатныя выхадныя, поўныя адпачынку, рэлаксацыі. Гэта было прыгожа ўчора. Так што, я спадзяюся, вам спадабалася на адкрытым паветры. 

Такім чынам, спачатку пару аб'яваў. Класіфікацыя. Так, большасць з вас павінен быў атрымаць па электроннай пошце ад мяне аб вашым драпін Pset, а таксама класіфікацыі для Pset 1. Так, толькі пара рэчаў. Абавязкова выкарыстоўвайце check50 ў style50. Яны прызначаны, каб быць Рэсурсы для вас, хлопцы, каб пераканацца, што вы атрымліваеце як мага больш ачкоў, як вы можаце без патрэбы губляць іх. Так, такія рэчы, як стыль вельмі важныя. Мы збіраемся зняць для яго. Некаторыя з вас, магчыма, ужо заўважыў, што ад вашага Pset. І check50 проста сапраўды просты спосаб, каб пераканацца, што мы на самай справе вяртання таго, што павінен быць вернуты карыстальніку, і што ўсё працуе правільна. 

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

Я ведаю, што гэта рана, але я цалкам былі ўзятыя знянацку па эсэ, гэта з-за гэтага ў пятніцу, то мае прафесара былі проста падабаецца, о да. Памятаеце, у вас ёсць эсэ за пятніцу. Так, я ведаю, ніхто не любіць думаць аб прамежкавых выбарах, але ваш першы віктарына на 15 кастрычніка якія кастрычніка пачынае на гэтым тыдні. Так, гэта можа быць раней чым вы чакалі ўсё. Так што вы не кінулі знянацку, калі Я ўжо раздзел на наступным тыдні, што о, ваш тэст на наступным тыдні, я думаў, Я хацеў бы даць вам крыху больш з кіраўнікоў цяпер. 

Так, устаноўлена, ваша праблема, нумар тры. Як людзі чыталі спец з цікаўнасці? Добра. Мы атрымалі некалькі. Выгляд ўніз з мінулага тыдзень, але гэта нармальна. Я ведаю, што гэта было прыгожа па-за. Так Break Out. Вызначана, пасля вы зрабілі сёння прачытаў вашу спецыфікацыю па меншай меры, паспрабуйце, як скачка Код размеркавання і працуе як у першы ініцыял рэч, што яны пытаюцца вас. Так як мы выкарыстоўваем Код размеркавання і бібліятэка што мы толькі using-- --Яна толькі У другі раз мы зрабілі гэта Pset, вар'яты рэчы могуць адбыцца з Вашай машыны, і вы хочаце, каб знайсці, што прама цяпер у параўнанні з пазней. 

Таму што, калі гэта ў чацвер вечарам ці гэта У сераду ўвечары, і чаму- Ваш прыбор проста не хачу працаваць з бібліятэкай або з размеркаваннем Код, які сродкі Вы не можаце нават пачаць рабіць кадаваньне. Таму што вы не можаце праверыць каб убачыць, калі ён працуе. Ваш не збіраюся быць у стане каб убачыць, калі ён збірае. Вы хочаце, каб клапаціцца пра тых, у пачатку тыдзень, калі вы ўсё яшчэ можаце напісаць мне або адзін з іншых ТФ, і мы можам атрымаць тыя фіксаванай. Таму што тыя пытанні, што збіраюцца, каб спыніць вас ад якіх-небудзь рэальнага прагрэсу. Гэта не так, як адна памылка, што Вы можаце толькі збольшага прапусціць. Калі ў вас узніклі праблемы з вашым Прыбор ці код размеркаванне, Вы сапраўды хочаце, каб што прынята клапаціцца аб хутчэй раней, чым пазней. Так што нават калі вы не збіраецеся на самай справе пачаць кадаваньне, загрузіць дыстрыбутыў Код, прачытаць спецыфікацыю, пераканайцеся усё працуе там. Добра? Калі вы можаце проста зрабіць гэта, я абяцаю вам жыццё будзе лягчэй. І так вы, верагодна, зрабіць гэта прама цяпер не так? Добра. Такім чынам, любыя пытанні там? Любыя лагістычныя рэчы? Усё добра? Добра. 

Адмова ад адказнасці для тых з Вы ў пакоі і на сайце. Я збіраюся спрабаваць пераключыць паміж PowerPoint ў прыборы таму што мы збіраемся быць рабіць некаторыя кадаваньне сёння па шматлікіх просьбах з ананімнага Прапанова апытанне я разаслаў на мінулым тыдні. Такім чынам, мы будзем рабіць некаторыя кадавання. Так што, калі вы, хлопцы, таксама хачу каб запусціць вашы прыборы, і вы павінны ёсць па электроннай пошце ад мяне, з файлам ўзору. Калі ласка, не саромейцеся зрабіць гэта. 

Так, мы збіраемся казаць пра GDB, які з'яўляецца адладчык. Гэта дапаможа вам выгляд высветліць, дзе справы ідуць не так у вашым кодзе. Гэта проста спосаб для вас крок па кодзе, як гэта адбываецца, і мець магчымасць раздрукаваць зменныя або паглядзець, што адбываецца на самай справе пад капот вершы праграму проста працуе, гэта як разломаў, і вы, як, не маючы ўяўлення, што толькі што адбылося тут. Я не ведаю, што лінія яго не ўдалося ў. Я не ведаю, дзе пайшло не так. Так, GDB будзе дапамагаць вам у гэтым. Акрамя таго, калі вы вырашыце працягнуць так, і прыняць 61, гэта будзе вельмі, вельмі б ваш лепшы сябар, таму што я магу вам сказаць, таму што я збіраюся праз гэтага класа. 

Мы будзем глядзець на двайковым Пошук, які, калі вы, хлопцы, памятайце Выдатны прыклад тэлефонная кніга Відовішча з класа. Мы будзем рэалізацыі, што і хадзіць праз што крыху больш, а затым мы збіраемся праз чатыры розныя віды, якія Bubble, Выбар, ўстаўкі, і аб'яднаць. Прахладны. Так, GDB, як я ўжо казаў, гэта адладчык. І гэта свайго роду вялікі рэчы, вялікія функцыі або каманды што вы выкарыстоўваеце ў GDB, і буду хадзіць Вы праз дэма ёй у секунду. 

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

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

Крок у залежнасці. Так як я ўжо казаў, як з своп, гэта было б дазваляюць на самай справе, як быццам ты як фізічна актывізацыі ўнутры, Вы можаце звязвацца з гэтымі зменнымі, друк тое, што яны, бачыце, што адбываецца. Спіс будзе літаральна друку з навакольнага кода. Так што, калі вы накшталт забыць дзе вы знаходзіцеся ў вашай праграме, ці вам цікава што адбываецца вакол яго, гэта будзе проста раздрукаваць сегмент з падабаюцца пяць ці шэсць ліній вакол яго. Такім чынам, вы можаце зарыентавацца аб тым, дзе вы знаходзіцеся. 

Раздрукаваць некаторыя зменныя. Так што, калі ў вас ёсць ключ, як у Цэзара, што мы будзем глядзець на. Вы можаце сказаць, друку Key ў любы момант. Гэта вам скажу, што гэта значэнне так што, можа быць, дзе-то па шляху, Вы перапісаў свой ключ. Вы сапраўды можаце сказаць, што з-за Вы можаце фактычна назіраць гэта значэнне. 

У мясцовых жыхароў, усяго прынтамі з вашых лакальных зменных. Так, у любы час вы ў цыкле, і вы проста хочаце, каб убачыць, як, ой. Якая мая я? Што гэта ключавая каштоўнасць што я ініцыялізаваць тут? Што такое паведамленне ў гэтай кропцы? Гэта будзе проста раздрукаваць ўсе з тых, так што вам не павінны індывідуальна кажуць, друку I. друку паведамленне. Друк Key. А потым Дысплей. Тое, што гэта робіць, як вы крок у рамках праграмы, гэта проста каб пераканацца, што гэта адлюстраванне некаторых пэўную зменную у кожнай кропцы. Так што вы also-- --Яна гэта выгляд цэтліка дзе Вы не павінны працягваць ісці, як, ай. Друк Key або друку I. Гэта проста аўтаматычна зробіць гэта за вас. 

Так, з тым, што мы збіраемся каб бачыць, як гэта ідзе. Я збіраюся паспрабаваць і перамыкач у мой прыбор. Глядзіце, калі я магу зрабіць гэта. Ўсё. Мы проста збіраемся, каб адлюстраваць яго. Там няма нічога, з розуму на маім ноўтбуку ў любым выпадку. Добра. Гэта павінен быць гэты. Гэта настолькі малюсенькія. Давайце паглядзім, калі мы можам зрабіць гэта. 

Добра. Аліса, відавочна, змагаецца тут ледзь-ледзь, але мы атрымаем яе ў Momento. Добра. Мы проста збіраемся павялічыць гэта. Добра. Можа ўсё быццам бачылі? Можа быць, трохі? Я ведаю, гэта крыху малая. Вы не можаце дастаткова высветліць як зрабіць гэта больш. Калі хто-небудзь ведае. Хто-небудзь ведае, як зрабіць яго больш? Добра. Мы збіраемся звярнуць з яго. Не мае значэння, у любым выпадку, таму што гэта проста што код, які вы, хлопцы, павінны ёсць. 

Што больш важна, з'яўляецца тэрмінал тут. І тут мы маем Чаму так мала? Налады. О. Праўда Айк. Як гэта? З там. Так лепш для ўсіх? Добра,. Прахладны. 

Вы ведаеце, калі вы знаходзіцеся ў CS тэхнічныя цяжкасці класа з'яўляюцца свайго роду часткай the-- Так, давайце растлумачым гэта. Добра. Так, прама тут, у раздзеле, якія мы мелі тут. Цэзар ўяўляе сабой выкананы файл. Так што я зрабіў гэта. Так, адна рэч, каб зразумець, з GDB з'яўляецца што ён працуе толькі на выкананых файлах. Такім чынам, вы не можаце запусціць яго на dotsy. Вы павінны рэальна зрабіць Пераканайцеся, што ваш код кампілюецца, і што ён на самай справе можа працаваць. 

Такім чынам, пераканайцеся, што калі гэта не так кампіляцыі, атрымаць яго для кампіляцыі, так што вы можаце роду праходзяць праз яго. Такім чынам, для пачатку GDB, усё, што вам рабіць, Глорыя тыпу GDB, а затым проста файл, які вы хочаце. Я заўсёды памылкі друку Цэзара. Але вы хочаце, каб пераканацца, так як гэта выкананы, Кропка ўспышкі Ці так што азначае, што вы ідзяце запусціць CSI вы збіраецеся выканаць гэта файлы альбо з дапамогай адладчыка. Добра. Так, вы што, вы атрымліваеце гэты від тарабаршчыну. Гэта проста ўсе рэчы аб адладчыка. Вы сапраўды не трэба турбавацца пра гэта прама цяпер. І, як вы бачыце, у нас ёсць гэта адкрытыя круглыя ​​дужкі, ВУП, блізкія круглыя ​​дужкі, і толькі збольшага падобны наша камандны радок, ці не так? 

Такім чынам, што ж мы хочам do-- --So, Першае, што гэта мы хочам выбраць месца, каб разбіць яго. Так, ёсць адна памылка У гэтай праграме Цэзар што я ўяўляю, што мы збіраемся высветліць. Гэта Што яна робіць, гэта ён прымае на ўваход Barfoo загалоўнымі літарамі, і чаму- гэта не мяняе А. Гэта проста пакідае толькі яна, усё астатняе правільна, але другая літара Застаецца нязменным. Так, мы збіраемся, каб паспрабаваць высветліць, чаму гэта. Так, першае, што вы, як правіла, хачу зрабіць, калі вы пачынаеце на GDB з'яўляецца высветліць, дзе разбіць яго. 

Так Цэзар з'яўляецца даволі кароткая праграма. Мы проста павінны адну функцыю, ці не так? Што наша функцыя ў Цэзара? Там толькі адна функцыя, Галоўнае правільна? Галоўная функцыя для ўсіх вашых праграм. Калі ў вас не было Main, я мог бы быць трохі хваляваўся зараз, але я спадзяюся, што вы ўсё былі Main там. Такім чынам, што мы можам зрабіць, гэта мы можам проста разарваць Main, як і што. Так, ён кажа, ОК. Мы ставім нашу супыну адзін ёсць. 

Так, у цяперашні час памятаць, Цэзар займае адно камандным радку аргументаў права і мы не зрабілі, што яшчэ нідзе. Такім чынам, што ж вы робіце, калі Вы на самой справе ісці працаваць праграма, любая праграма, што ты працуе ў GDB, які мае патрэбу каманднага радка Аргументы, што вы збіраецеся ўваход пры першым запуску яе запуску. Так, у дадзеным выпадку, мы робім Запуск з ключом у тры разы. І гэта будзе на самой справе пачаць. 

Так што, калі вы бачыце тут, у нас ёсць Калі RC не роўна 2. Так што, калі вы, хлопцы, ва ўсіх ёсць што файл, які я разаслаў да Вы ўбачыце, што гэта як Першая лінія наша галоўная функцыя, ці не так? Гэта праверка таго, калі ў нас ёсць правільнае колькасць аргументаў. Так што, калі вам цікава, калі RC правільна, Вы можаце зрабіць што-то так жа, як для друку RC. RC роўны двум, які што мы чакалі, ці не так? 

Так, мы можам ісці далей, і працягваць да канца. Так, у нас ёсць некаторыя клавішы там. І мы можам раздрукаваць наш ключ каб пераканацца, што гэта правільна. Цікава. Не зусім тое, што мы чакалі. Так, адна рэч, каб зразумець, з GDB таксама, з'яўляецца што гэта не пакуль вы не патрапілі Далей, што лінія, што вы толькі што бачылі на самай справе выкананы. Так, у гэтым выпадку ключ ня быў прызначаны яшчэ. Так, Key некаторы значэнне смецця што вы бачыце на дне там. Адмоўны $ 120-- --Яна аднаго мільярда і што-то дзіўныя рэчы правільна? Гэта не той ключ, які мы чакалі. Але калі мы трапілі Далей, а затым мы паспрабуйце і ключ друку, гэта тры. 

Усё гэта бачылі? Так што, калі вы атрымліваеце нешта што вы, як, чакаць. Гэта цалкам не так, і я не ведаю, як гэта будзе адбывацца, таму што ўсё, што я хачу зрабіць, гэта прызначыць нумар, зменная, паспрабуйце націснуць Далей, паспрабуйце друк гэта зноў, каб убачыць, калі гэта працуе. Таму што гэта толькі збіраецца выканаць і фактычна прызначыць што-то пасля вас хіт Далей. Зрабіць сэнс для ўсіх? Угу? 

СПІКЕР 2: Калі вы выпадковым нумары, што гэта значыць? 

СПІКЕР 1: Гэта проста выпадковы. Гэта проста смецце. Гэта проста нешта, што ваш Кампутар выпадковым чынам прысвоіць. Прахладны. Такім чынам, цяпер мы можам рухацца праз, і так Цяпер у нас ёсць гэты просты тэкставы GetString. Такім чынам, дазвольце мне проста ўвесці што адбудзецца, калі мы трапілі Далей тут. Наша GDB выгляд знікае, ці не так? Гэта таму, што GetString Цяпер выкананне, ці не так? Так, калі мы ўбачылі звычайны тэкст роўны GetString, адкрытыя круглыя ​​дужкі і круглыя ​​дужкі, і мы трапілі Далей, што мае фактычна выканана цяпер. Так, ён чакае нам уваходнага што-то. 

Так, мы збіраемся ўвесці нашу ежу, якая з'яўляецца тое, што ён трывае няўдачу, як я сказаў вам, і што як раз кажа, што гэта скончыў працу, што зачыненыя Кранштэйны азначае, што гэта выхаду з гэтага цыклу. Так, мы можам ударыць Далей, і цяпер, як я што вы ўсе знаёмыя з Цэзарам, гэта, што гэтая лінія збіраецца рабіць. Гэта для Int я роўная 0, N роўны STRLEN, просты тэкст, а затым Я менш п, я, плюс, плюс. Што гэта пятля збіраецеся рабіць? Адкрыйце ваша паведамленне. Прахладны. Так, давайце пачнем гэта рабіць. 

Так, калі гэта ўмова супадаюць, для нашага першага? Калі гэта B, гэта звычайны тэкст І. Мы можна атрымаць інфармацыю аб нашых мясцовых жыхароў. Такім чынам, я роўны нулю, а калі шэсць, які мы чакаем, і наш ключ тры. Усё, што мае сэнс, ці не так? Гэтыя лічбы ўсё менавіта тое, што яны павінны быць. Так, напяваць? СПІКЕР 3: У мяне ёсць выпадковыя ліку для шахты. СПІКЕР 1: Ну, мы можам check-- --Мы можа пагаварыць пра тое, што ў адну секунду. Але вы павінны атрымліваць гэта. Так што, калі ў нас ёсць капітал У нашай першай, гэта ўмова павінна злавіць яго, ці не так? Так што, калі мы трапілі Далей, мы бачым, што гэта Калі на самай справе выконвае. Таму што, калі вы вынікаеце разам у кодзе, гэтая лінія тут, дзе звычайны тэкст я замяняецца гэтай арыфметыкі, выконваецца толькі ў If ўмова правільнага права? 

GDB толькі збіраюся паказаць вам, рэчы, якія на самай справе выканаўцы. Так што калі гэта ўмова Калі не было выканана, гэта проста хачу, каб перайсці да наступнай радку. Добра? Так, у нас ёсць што. Гэты кранштэйн азначае, што гэта зачынены з гэтай завесы цяпер. Так, ён збіраецца пачаць зноў. Гэтак жа, як, што. Так, што мы можам атрымаць інфармацыю аб нашых мясцовых жыхароў тут, і мы бачым, што наша першая Ліст змянілася, ці не так? Гэта цяпер E, як і павінна быць. Так, мы можам працягваць. 

І ў нас ёсць гэты чэк. І гэтая праверка павінна працаваць, ці не так? Гэта А. Гэта павінна быць зменена тры літары наперад. Але калі вы заўважылі, мы атрымаць нешта іншае. Такім чынам, у гэтым выпадку тут, ён злавіў гэта і так гэтая лінія выканана, якія зменены наш B. Але, у гэтым выпадку тут, у нас ёсць, што ён проста прапусціў яго, і пайшоў у [? L Сифф. ?] Так што-то там адбываецца. Тое, што гэта кажа вам, што, мы ведаем, што ён павінен злавіць тут, але гэта не так. Можа хто-небудзь паглядзець, што наш Праблема ў тым, у гэтым радку? Гэта вельмі хвілін, што. І вы таксама можаце паглядзець на кодзе. Ён таксама line-- забыць тое, што лінія гэта у there-- але гэта ў [неразборліва]. Так? 

СПІКЕР 4: Гэта на больш чым старонку, калі вы чытаеце гэта ў кнізе. СПІКЕР 1: Дакладна. Так, адладчык не мог сказаць, Вы што, але адладчык можа вам ўніз да лініі што вы ведаеце, не функцыянуе. І часам, калі асабліва пазней у семестр, калі Вы маеце справу з сотняй, з сто некалькі радкоў кода, і вы не ведаю, дзе гэта не ўдаецца, гэта выдатны спосаб зрабіць гэта. Так, мы знайшлі наш памылка. Вы можаце гэта выправіць у файле, а затым вы можаце запусціць яго зноў, і ўсё будзе працаваць выдатна. І, самае важнае, гэта гэта можа здацца, ОК. Так. Прахладны. Вы ведалі, што вы шукаеце. Такім чынам, вы ведалі, што рабіць. 

GDB можа быць супер карысна, таму што вас можна раздрукаваць ўсе гэтыя рэчы, якія вы не будзе. Гэта значна больш карысна, чым PRINTF. Як многія з вас выкарыстоўваць як PRINTF справаздачнасці каб высветліць, дзе памылка была, ці не так? Так, з гэтым, вы не павінны працягваць вяртацца, і падабаецца каментуючы ў PRINTF або каментавання, і высветліць, што Вы павінны быць друку. Гэта на самай справе проста дазваляе пакрокава, раздрукаваць рэчы як вы праходзіце, так, вы можаце назіраць, як яны мяняюцца ў рэжыме рэальнага часу, як вашай праграме працуе. 

І для гэтага трэба крыху Трохі прывыкнуць. Я вельмі рэкамендую проста выгляд быць трохі расчараваныя з ім прама цяпер. Калі вы праводзіце гадзіну на працягу на наступным тыдні навучання, як выкарыстоўваць GDB, Вы пазбавіце сябе так шмат часу ў далейшым. І літаральна. мы кажам гэта людзям кожны год, і я памятаю, калі я ўзяў клас, я быў бы, мне будзе добра. Няма. Pset 6 загарэліся і я быў як, я збіраюся вучыцца як выкарыстоўваць GDB, таму што я не ведаю, што тут адбываецца. 

Так што, калі вы не спяшайцеся, так выкарыстоўваць яго на больш дробныя праграм што вы збіраецеся быць працаваць, як працуе праз што-то накшталт Visionare, як гэта. Ці, калі вы хочаце дадатковую практыку, я ўпэўнены, што Я мог прыдумаць багі праграм, для адладжваць, калі вы хочаце. 

Але калі вы проста заняць некаторы час, каб атрымаць прывык да яго, проста пагуляйце з ім, гэта будзе сапраўды служыць вам добра. І гэта сапраўды адзін з тыя рэчы, якія вы проста павінны паспрабаваць, і пэцкаць рукі с, перш чым вы на самой справе зразумець гэта. Я сапраўды толькі зразумеў яго адзін раз У мяне было адладжваць рэчы з ім, і гэта значна прыемней мець уяўленне аб тым, як адладжваць хутчэй раней, чым пазней. Добра. Прахладны. Я ведаю, што гэта накшталт як паскораны курс GDB, і я, безумоўна, працаваць на атрыманне гэта глядзець больш у наступны раз. Прахладны. 

Так што, калі мы вернемся да нашага PowerPoint. Ці будзе гэта працаваць? АДД. Так. Добра. Так што, калі вы калі-небудзь спатрэбіцца любы з тыя, зноў жа, ёсць спіс. Так Двайковы пошук, які ўсё памятае вялікую відовішча Давіда раздзіраючы тэлефонныя кнігі ў палове. Я сапраўды не атрымаць тэлефонныя кнігі больш, таму як дзе ты атрымаць тэлефонныя кнігі ў гэтыя дні? Я сапраўды не ведаю. Двайковы пошук. Ці памятае хто- Як бінарны пошук працы? Любы наогул? Так? СПІКЕР 5: Вы ведаеце, калі Вы глядзіце на якіх палова гэта было б у, Зыходзячы з гэтага, і пазбавіцца ад другой паловы. 

СПІКЕР 1 Роўна. Так, бінарны пошук, гэта збольшага a-- --мы падабаецца называць гэта падзяляй і ўладар. Такім чынам, што ж вы будзеце рабіць гэта Вы будзеце выглядаць у сярэдзіне, і вы ўбачыце, калі ён адпавядае тое, што вы шукаеце. А калі гэта не так, то вы спрабуеце высветліць, ён збіраецца пакінуць палова ці правая палова. Так, гэта можа быць, калі вы шукаеце на што-тое, што гэта алфавітны, Вы бачыце, а. Прыходзіць Ці Элісан да М? Так. Так, мы збіраемся паглядзіце на першую палову. 

Ці гэта можа быць як з лікамі. Усё, што вы можаце параўнаць, гэта могуць быць адсартаваныя. Вы можаце выкарыстоўваць бінарны пошук на. Так, хто-небудзь памятае гэта Графік ці што гэта такое? Гэта асімптатычнай складанасці. Такім чынам, гэты графік толькі апісвае, як доўга ён прымае вас, каб вырашыць праблему, як Вы павялічыць колькасць рэчаў што вы выкарыстоўваеце. 

Так, у нас ёсць N, які з'яўляецца лінейнае час. Калі N за два, што крыху лепш, яшчэ расце вельмі хутка. А потым мы Увайдзіце, які з'яўляецца што мы лічым бінарны пошук. Калі мы заўважаем, як вашай праблемы становіцца нашмат і нашмат больш, Час, якое патрабуецца вам яе вырашыць на самай справе не павялічыць, што шмат. Гэта як супастаўныя Тут у пачатку. Ты як, у парадку. Нічога тут не сапраўды ад таго, які мы выкарыстоўваем, але вы выйсці на мільён, мільярд. Вы спрабуеце знайсці some-- --you're спрабуючы знайсці іголку ў стозе сена. 

Я думаю, што вы жадаеце гэтую праблему. Вы хочаце, каб гэтая складанасць, а не лінейнай, паколькі для ўсіх вас ведаю, што вы збіраліся быць пошук праз кожны чалавек іголка, рэч сена, спрабуючы адшукаць іголку. І гэта не надта цікава, на мой погляд. Я хутка падабаецца. Мне падабаецца эфектыўным. І як працавітыя студэнты вы Хлопцы, вы ведаеце, працаваць разумней, не складаней рэч тыпу, як вам можа зрабіць гэтыя алгарытмы. 

Так, мы збіраемся хадзіць толькі праз невялікі прыклад. Я думаю, што вы, хлопцы, павінны мець Рука на бінарны пошук, але ў выпадку, калі хто трохі невыразная, хочаце, каб умацаваць яго, мы збіраемся, каб проста пайсці праз прыкладу тут. Так, мы шукаем, калі масіў ўтрымлівае сем. 

Так, першае, што мы робім, шукаць у сярэдзіне, ці не так? А таксама вы збіраецеся быць кадавання Двайковы пошук у толькі другі. Такім чынам, гэта будзе весела. Такім чынам, мы з нецярпеннем ў сярэднія маленькія масівы 3. 3 Ці адпавядае 7? Ці не праўда. Гэта шэсць. Такім чынам, гэта менш або больш, чым сем? Менш чым. Так. Добрыя хлопцы працы. Я адчуваю, што я хацеў, я павінен ёсць цукеркі, таму што я хачу кінуць яго ў двары. Гэта тое, што я збіраюся рабіць на наступным тыдні. Ён будзе трымаць вас, хлопцы рэзкі. 

Так, мы выкідваем, што Першая палова, ці не так? гэта было менш, чым. мы ведаем, што ўсё, на гэтай левага боку будзе менш, чым мы на самай справе шукаем. Такім чынам, няма ніякай неабходнасці звярнуць на гэта ўвагу. Проста забудзьцеся пра гэта. Такім чынам, зараз мы глядзім на нашу справа, і мы глядзім на сярэдзіне там, і зараз гэта дзевяць. Так, 9 is-- --Everyone? Больш, чым тое, што мы шукаю, ці не так? Так, мы збіраемся кінуць ад усё направа. Вось так. Цяпер, усё, што мы засталіся з адным. Так мы правяраем, гэта адзін, што мы шукаем? гэта. Мы знайшлі, што мы хацелі. Такім чынам, мы зрабілі. Білінейны Пошук. 

І калі вы заўважылі, мы было сем уваходаў там. Гэта толькі нам, як тры разы, але калі вы робіце, як мільярд, Вы, хлопцы, ведаеце, колькі крокаў было б прыняць, калі ў нас было чатыры мільярды рэчы? Любыя здагадкі? Гэта 32. 32 крокаў, каб знайсці што-то у чатыры мільярды элемент масіва з ступеняў двойкі. Так два гэта 32, гэта да чатырох мільярдаў. 

Так даволі вар'ятам, як вы ўсё яшчэ ў як досыць невялікага ліку крокаў знайсці што-то ў чатыры мільярды элементаў. Так на гэтай ноце, мы збіраюся кадзіраваць гэта так вы, хлопцы, можа на самай справе выгляд паглядзець, як гэта працуе. Добра, так што вы, хлопцы, можаце закадаваць. Я збіраюся дазволіць вам, хлопцы гаварыць на трохі. Пазнаёмцеся з людзьмі вакол вас, што з'яўляецца што хто-то хацеў ад апошняй секцыі. 

Так што ведаць людзей вакол вас. Пагаворыце для няшмат. І ўсё, што я хачу ад вас Хлопцы зараз проста паспрабаваць стварыць накід псевдокоде. Добра? Вау. Усё, што я хачу ад вас, хлопцы гэта ты проста хачу, каб запоўніць гэта пакуль выпадку. Так я паставіў гэтыя верхняя і ніжняя межы якой ўяўляюць сабой пачатак і канец нашага масіва. І вы збіраецеся на самай справе цыкл па і высветліць што мы робім у гэтым час цыклу. 

Так што калі вы можаце высветліць out-- мяне ёсць намёк there-- якія справы што мы маем тут? Так што, калі вы хочаце, каб высветліць, выпадкі, мы будзем псевдокод тых і тады мы будзем сапраўды закадаваць іх. І гэта будзе, я думаю, мы спадзяемся, гэта будзе быць крыху лягчэй, чым вы чакаеце. Таму што гэта не так ужо шмат кода, на самай справе, што гэта сапраўды крута. 

Мм-хм? 

СТУДЕНТ: [неразборліва]? Выкладчыкі: Так. Існаваў што-то знайсці ў сярэдзіне. 

СТУДЕНТ: Такім чынам, мы можам выкарыстоўваць яго. Добра. 

Выкладчыкі: Выдатна. Так што першае, што нам трэба зрабіць. Так знайсці сярэдзіну. Вялікая. Так што ў вас ёсць уяўленне аб тым, як мы маглі б на самой справе знайсці сярэдзіну з кодам? 

СТУДЕНТ: Так. п над 2? Выкладчыкі: Так п над 2. Так што галоўнае памятаць, што Вашы верхнія і ніжнія межы змены. Мы працягваем звужаючы ўдзел з масіва мы спадзяемся. Так п над 2 будзе працаваць толькі для першай рэчы мы робім. Так што, верхні і ніжні пад увагу, як мы маглі б атрымаць, што сярэдні элемент? Таму што мы хочам, каб сярэдзіна паміж верхняй і ніжняй, ці не так? Мм-хм? 

СТУДЕНТ: [неразборліва]. 

Выкладчыкі: Такім чынам, мы маем некаторую сярэдзіну. І гэта будзе верхняя плюс ніжэй больш за 2. Дзіўны. Там мы ідзем. Адна лінія ўніз. Вы, хлопцы, на вашым шляху. Так што цяпер у нас ёсць наш сярэдняга, тое, што мы хочам зрабіць? Проста ў цэлым. Вам не трэба кадзіраваць яго. Так. СТУДЕНТ: [неразборліва]? Выкладчыкі: Так што гэта плюс, таму што ты знайсці сярэдняе паміж двума з іх. Так што калі вы думаеце пра іх, як выгляд павелічэння ў з бакоў, думаю пра гэта, калі вы набліжаецеся сярэдні, вы хочаце так. Так што, калі вы былі па абодва бакі ад сярэдні, і ў нас ёсць як 5 і 7. Пры даданні іх разам вам атрымаць 12, вы падзеліце на 2, 6. 

Часам гэта цяжка растлумачыць, чаму гэта працуе, але калі вы працуеце праз прыклад часам, гэта дапаможа вам зразумець, калі яна павінна быць плюс або мінус. Так. 

СТУДЕНТ: [неразборліва] роўна пасярэдзіне калі яны быў выпадак, калі ёсць шмат меншых колькасцях і як адзін вялікай колькасці? 

Выкладчыкі: Усё, што Вам трэба гэта сярэдзіна масіва. Так што, калі ў вас была куча невялікіх колькасцях а затым адзін сапраўды вялікая колькасць у рэшце рэшт, гэта не мае значэння. Усё, што мае значэнне ў тым, што яны сартуюцца, вы проста хачу паглядзець на сярэдзіне масіў, таму што вы ўсё яшчэ нарэзкі вашу праблему ў два разы. Прахладны. Так што цяпер у нас ёсць сярэдні, што мы будзем рабіць далей? 

СТУДЕНТ: Параўнанне. Выкладчыкі: параўнаць. Так параўноўваць сярэдні для value_wanted. Прахладны. Такім чынам, вы бачыце тут у нас ёсць гэта значэнне мы хочам тут. Памятаеце, што гэта масіў. Так сярэдні ставіцца да індэксу. Такім чынам, мы хочам зрабіць значэння сярэдзіне. Не забывайце, калі вы хочаце параўнаць, двайныя роўных. Вы робіце адзін складае вы проста хачу, каб перапрызначыць яго, а затым, вядома, гэта будзе значэнне, якое вы хочаце. Так што не рабіце гэтага. 

Такім чынам, мы збіраемся, каб убачыць, калі значэння ў сярэдзіне роўная кошту мы хочам. Не забывайце свае брекеты. Dropbox павінен сысці. Дык што ж нам рабіць у гэтым выпадку? Калі гэта тое, што мы хочам вярнуцца? Мы спрабуем сказаць. 

СТУДЕНТ: Раздрукуйце. 

Выкладчыкі: Ну, мы не хачу, каб раздрукаваць. Так што гэта Ьоо тут, таму мы хачу вярнуцца сапраўдным або ілжывым. Мы кажам, гэта лік [? АСР? ?] Такім чынам, калі яна ёсць, мы толькі што вярнуліся ці праўда. Калі я магу запісаць дакладна. 

СТУДЕНТ: Чаму б вам не вярнуцца да нуля? Выкладчыкі: Такім чынам, вы маглі вярнуць нуль, калі вы хацелі. Але ў дадзеным выпадку, таму што наша функцыя вяртае лагічнае значэнне, мы павінны вярнуцца сапраўдным або ілжывым. СТУДЕНТ: Калі ты кажучы лагічны выраз, Вы можаце ўсталяваць яго роўным хлусня? Як калі я хачу сказаць, калі гэта ўмова не выконваецца, як гэта верхняя раўняецца хлусня. Ці будзе гэта разумець, калі вы проста пакласці хлусня на другі бок? Выкладчыкі: Так. Так на самой справе, калі вы калі-небудзь што-то рабіць як зверху або ніжэй, што вяртае ісціну або хлусня і гэта на самай справе дрэнны стыль скажам роўная роўная праўда ці роўных раўняецца хлусня. Вы хочаце выкарыстаць гэты вынік як сам, як ваш чэк. Не тое, што я хацеў. Гэта тое, што я хацеў. Такім чынам, у выпадку, калі вы пытаеце пра што-то, як захаваць гэта ў с. 

Так што, калі ў нас ёсць Int асноўны (пустэчу) і нешта накшталт гэтага. І ў вас ёсць, калі ёсць верхняя які прыход і ты з просьбай, калі вы можаце зрабіць нешта накшталт гэтага? Ці не так? СТУДЕНТ: я спрабаваў зрабіць гэта [неразборліва]. Таму што, калі it's-- Выкладчыкі: справа. Такім чынам, вы хочаце, каб гэта было ілжывым, ці не так? СТУДЕНТ: Так. Выкладчыкі: Так што ў гэтым выпадку вы хачу, каб гэта зрабіць, калі гэта не так. Так выдатна, што ў вас там такое. Так што памятаеце ўсклік Кропка адмаўляе рэчы? Гэта кажа [неразборліва] азначае не. Так што, калі мы паглядзім на толькі што гэтая частка тут, вы б сказаць, што мае значэнне хлусня, як вы хочаце, каб ён. Ня ілжывае праўдзіва, якія значыць гэта выканаць. Ці мае гэта сэнс? СТУДЕНТ: Так. Выкладчыкі: Awesome. Добра. Такім чынам, мы маглі б проста вярнуцца праўда ў гэтым выпадку. Так што цяпер у нас ёсць два іншых выпадкаў у гэтым выпадку. Якія нашы два іншых выпадку? Давайце проста рабіць гэта такім чынам. Такім чынам, давайце пачнем з яшчэ калі значэння ў сярэдзіне менш, чым значэнне мы хочам. Такім чынам, наша каштоўнасць у сярэдзіне менш чым значэнне, што мы шукаем. 

Такім чынам, якія мяжы зрабіць вас думаю, што мы хочам, каб абнавіць? Верхні ці ніжні? Верхні? Так на чыім баку масіва мы збіраемся быць гледзячы на? 

СТУДЕНТ: Ніжні. 

Выкладчыкі: Мы будзем каб глядзець на левай. Так яшчэ, калі мала значэнне менш. Так вашым сярэдняга значэння тут менш, чым тое, што мы хочам. Таму мы хочам, каб узяць Правая бок масіве. Такім чынам, мы збіраемся абнавіць наш ніжняя мяжа. Такім чынам, мы будзем перапрызначацца нашага ніжэй. І што вы думаеце ніжэй павінна быць? СТУДЕНТ: сярэдняе значэнне? Выкладчыкі: Так сярэдні value-- СТУДЕНТ: Плюс 1. Выкладчыкі: --plus 1. Можа хто-небудзь сказаць мне, чаму у нас ёсць, што плюс 1? 

СТУДЕНТ: [? Няма значэння?] Больш роўная ёй. 

Выкладчыкі: справа. Таму што мы ўжо ведаем, што наша сярэдняе значэнне не роўна гэта, і мы хочам, каб выключыць яго ад ўсіх наступных пошукаў. Калі вы забыліся, што плюс 1, гэта спадабаецца цыкл бясконца. І вы проста патрапіць у бясконцы цыкл, а затым вы будзеце сегментацыі і справы ідуць дрэнна. Так заўсёды пераканайцеся, што вы не у тым ліку значэнне, што вы толькі што паглядзеў на. Такім чынам, мы клапоцімся аб тым, што з плюсам 1. 

Так што цяпер у нас ёсць апошняя ўмова якія я заўсёды дзеля бяспекі Вы можаце праверыць тут, інакш, калі значэнне ў сярэдні больш, чым значэнне мы хочам. Гэта азначае, што мы хочам левая рука напалову. Дык які з іх мы збіраемся абнавіць? Верхні. І што гэта за адзін збіраўся раўняцца? Сярэдні мінус 1, таму што, Вядома, мы хочам, каб пераканацца, што мы не гледзячы на ​​гэтага сярэдняга значэння зноў. А то ў нас яго. Гэта так. Вось і ўсё, бінарны пошук. Гэта не так ужо дрэнна, ці не так? Гэта як 10 радкоў Код з прабеламі. Так, вельмі магутны, вельмі карысна, вы будзеце быць з выкарыстаннем яго ў адным з вашых наступных psets. Можа быць, гэта не адзін, але пазней. Так вывучаць яго. Люблю гэта. Гэта будзе ставіцца да вас добра. Дык хто-небудзь ёсць якія-небудзь пытанні па бінарнага пошуку? Так. 

СТУДЕНТ: гэта мае значэнне ці Ці ваш н цотных або няцотных? 

Выкладчыкі: Не. Таму што мы кінулі яго ў сярэдзіну, як INT, гэта будзе проста абрэзаць яго. Так ён будзе заставацца цэлае, і гэта будзе у рэшце рэшт разабрацца ў ўсім. Такім чынам, вы не павінны турбавацца пра гэта. Усё добра? Дзіўны. Прахладны. Так, вы, хлопцы, атрымаў гэта. Слайд-шоў. Так як мы кажам пра, я ведаю, Дэвід узгадаў цяжкасці аўтаномнай працы. 

Такім чынам, у лепшым выпадку, гэта проста адзін, які мы называем пастаяннае час. Можа хто-небудзь сказаць мне, чаму гэта можа быць? Які тып сцэнара будзе, што цягне за сабой? Мм-хм. 

СТУДЕНТ: [неразборліва] first-- Выкладчыкі: Так сярэдні з'яўляючыся Першы элемент, які мы падыходзім да, ці не так? Так што альбо масіў з аднаго або усё, што мы шукаем толькі здараецца, прама па сярэдзіне. Так што гэта наш лепшы выпадак. Вы атрымліваеце ў рэальных праблем, верагодна, не збіраецца дасягнуць [неразборліва], што часта. А як наконт нашай горшым выпадку? Наш горшы выпадак часопіса н. І што павінен рабіць з усім Паўнамоцтвы два рэчы, якія я казаў пра. 

Такім чынам, у горшым выпадку гэта будзе азначаць, што мы павінны былі нарэзаць масіў ўніз пакуль ён не быў элементам адзін. Так што нам прыйшлося калоць яго напалову столькі разоў, колькі мы магчыма маглі. Вось чаму гэта часопіс н таму Вы проста падзяляць на два. Так здагадкі, рэчы, якія вы трэба ведаць, калі вы калі-небудзь збіраецеся выкарыстоўваць бінарны пошук. Вашы элементы павінны быць адсартаваныя. Яны павінны быць адсартаваныя, таму што гэта адзіны спосаб можа ведаць, калі вы зможаце выкінуць палову з яго. 

Калі ў вас гэта перамяшаныя мяшок лікаў і вы кажаце, ОК, я збіраюся праверыць сярэдзіну Колькасць і лік Я шукаю менш, чым, я проста хачу, адвольна выкінуць палову. Вы не ведаеце, калі ваша Лічбы ў гэтай іншай палове. Ваш спіс павінен быць адсартаваны. Акрамя таго, гэта можа быць ісці наперад трохі, але вы павінны мець адвольны доступ. Вы павінны быць у стане проста перайсці на гэтую сярэдняга элемента. Калі ў вас ёсць, каб прайсці праз што-то ці гэта зойме ў вас дадатковыя крокі каб дабрацца да гэтага сярэдняга элемента, гэта не ўвайсці н больш, таму што Вы дадаеце больш працы ў ім. І гэта зробіць крыху больш сэнсу ў два тыдні, але я толькі збольшага хацеў бы папярэдзіць, даць вам, хлопцы ўяўленне пра тое, што прыйсці. Але тыя два важныя дапушчэння што вам трэба для бінарнага спісу. Пераканайцеся, што ён адсартаваны. Гэта вялікі для Вы, хлопцы, прама цяпер. І на што мы можам пайсці ў Астатнія нашы гатункаў. Так чатыры sorts-- бурбалка, устаўка, выбар, і зліццё. Яны ўсе крута. Калі вы, хлопцы, вырашылі ўзяць CS 124, Вы даведаецеся аб разнастайных гатункаў. І калі вы прыхільнік XKCD, ёсць гэта сапраўды выдатна комікс пра як сапраўды неэфектыўных відаў, якія я вельмі рэкамендую вам ісці глядзець. Адным з іх з'яўляецца, як панічнае роду, якія як, ой не, вярнуць масіў выпадковых. Shutdown сістэма. Пакіньце. Так што выклікаюць гумар заўсёды добра. 

Дык хто-небудзь памятае выгляд з як толькі агульнае ўяўленне пра тое, як працуе пузырьковый сартавання. Вы памятаеце? 

СТУДЕНТ: Так. 

Выкладчыкі: Пайсці на гэта. 

СТУДЕНТ: Дык што вы збіраецеся праз і калі ён больш, то трэба памяняць месцамі два. 

Выкладчыкі: Мм-хм. Дакладна. Такім чынам, вы проста перабраць. Вы праверыць два ліку. Калі адзін перад больш чым той, пасля, Вы проста абмяняць іх такім чынам, каб у Такім чынам, усё больш высокімі нумарамі бурбалка уверх да канца спісу і ўсё меншы лік бурбалка ўніз. 

Ён пакажа вам, хлопцы выдатна гукавы эфект сартаванне відэа? Гэта крута. Так як Роберт проста сказаў, алгарытму што вы проста перамяшчацца па спісе, абмен суседнія значэння калі яны не ў парадку. А потым проста паўтараць пакуль вы не рабіць якія-небудзь свопы. Так не дрэнна, ці не так? Так што мы проста мець хуткі прыклад. Дык гэта будзе сартаваць іх у парадку ўзрастання. Таму, калі мы праходзім праз першы Час, мы глядзім праз восем і шэсць, відавочна, не для таго, што мы памяняць іх месцамі. 

Так што глядзіце на наступным. Восем і чатыры не ў парадку. Памяняць іх. А потым восем і два, памяняць іх месцамі. Там мы ідзем. Такім чынам, пасля першага праходу, вы ведаеце, што ваш самы вялікі нумар будзе цалкам у верхняй, таму што гэта проста будзе пастаянна больш, чым усе астатняе і гэта толькі збіраецца бурбалкі ўсю дарогу да канца там. Ці значыць гэта, мае сэнс для ўсіх? Прахладны. 

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

І гэта вялікая рэч з пузырьковый сартавання. Мы ведаем, што, калі мы маюць нулявыя свопы, што азначае, што ўсё, знаходзіцца ў поўным парадку. Гэта свайго роду, як мы правяраем. Такім чынам, мы таксама збіраемся кадзіраваць бурбалка роду, якія таксама не ў тым, што дрэнна. Ні адзін з іх не так ужо дрэнна. Я ведаю, што яны могуць здацца трохі страшна. Я ведаю, калі я ўзяў клас, нават калі я выкладаў клас для першы раз у мінулым годзе, Я быў, як, як я магу гэта зрабіць? Гэта мае сэнс у тэорыі, але як мы на самай справе гэта зрабіць? Менавіта таму я і хачу, каб ісці праз код з вамі, хлопцы тут. Так што ў мяне псевдокод для вас, хлопцы на гэты раз. Так што майце гэта на ўвазе, як мы збіраемся перайсці на працягу. Таму ў нас ёсць які-небудзь лічыльнік, што адсочвае нашы свопы, таму што нам трэба, каб пераканацца, што мы правяраем, што. І мы ітэрацыі ўвесь масіў як мы толькі што зрабілі з гэтым прыкладам. Калі элемент, перш чым больш элемент пасля, дзе мы знаходзімся, мы абмяняць іх і мы павялічваем OUR Лічыльнік таму што як толькі мы памяняць, мы хочам, каб наш лічыльнік ведаю, што. Любыя пытанні ёсць? Што-то, здаецца, смешна тут. СТУДЕНТ: Вы ўсталяваць лічыльнік на нуль кожны раз, калі вы ідзяце праз пятлю? Вы не працягваць назад да нуля кожны раз? Выкладчыкі: Не абавязкова. Дык што ж адбываецца ў нас прайсці тут. Так што ў той час, памятаеце, што гэта будзе выконваць адзін раз у абавязковым парадку. Дык гэта будзе ўстаноўлена лічыльнік роўны нулю, то гэта будзе для перабору. Як яно праходзіць па, яна абновіць лічыльнік. Як ён абнаўляе лічыльнік, калі гэта будзе зроблена, калі ён дасягнуў канца масіва, калі наш спіс не адсартаваны, Лічыльнік былі абноўленыя. 

Так то яно правярае стан і кажа, добра, гэта лічыльнік больш за нуль. Калі гэта так, зрабіць гэта зноў. Вы хочаце скінуць, так што, калі вам прайсці праз, лічыльнік роўны нулю. Калі вы ідзяце праз адсартаваны Масіў, нічога не мяняецца, гэта не атрымоўваецца, і вы вярнуцца адсартаваны спіс. Ці значыць гэта, мае сэнс? СТУДЕНТ: Гэта можа ў трохі. Выкладчыкі: ОК. Калі ёсць якая-небудзь іншая Пытанне, які прыходзіць. Так. 

СТУДЕНТ: Што б функцыя быць для перапампоўкі элементы? 

Выкладчыкі: Такім чынам, мы можам на самай справе пісаць што калі мы збіраемся прама цяпер. Прахладны. Так на гэтай ноце, Элісан збіраецца Каб вярнуцца назад у прыбор. Гэта будзе весела. І ў нас ёсць наш слаўны пузырьковый сартаванне рэч тут. Так што я ўжо зрабіў на ровары праз масіў. У нас ёсць нашы свопы, якія роўныя нулю. Таму мы хочам, каб памяняць прылеглых элементы, калі яны выйшлі з ладу. Таму першае, што мы павінны робім, перабору нашага масіва. 

Такім чынам, як вы думаеце, мы маглі б перабору нашага масіва? У нас ёсць для, і я роўная 0. Мы хочам, каб я быць менш чым п мінус 1 мінус к. І я растлумачу, што ў секунду. Так што гэта аптымізацыя тут, дзе, памятаю, як я сказаў, пасля кожнага праходу праз масіў мы ведаю, што ўсё, што гэта on-- 

Такім чынам, пасля аднаго праходу мы ведаю, што гэта сартуецца. Пасля двух праходаў мы ведаем што ўсё гэта сартуецца. Пасля трох праходаў мы ведаю, што гэта сартуюцца. Так Дарэчы я ітэрацыі праз масіў тут, будзе гэта рабіць абавязкова ісці толькі праз тое, што мы ведаем, гэта малокомплектных. Добра? Вось толькі аптымізацыя. Вы маглі б напісаць яго наіўна проста перабору за ўсё, гэта было б проста заняць больш часу. З гэтага чатыры цыклу гэта проста добры аптымізацыя таму што мы ведаем, што пасля таго, як кожны поўны ітэрацыі па масіве тут, як кожны поўны завесы тут, мы ведаем, што больш з гэтых элементаў аднаго будуць размеркаваны ў канцы. 

Такім чынам, мы не павінны турбавацца пра іх. Ці значыць гэта, мае сэнс для ўсіх? Гэта выдатна маленькая хітрасць? Такім чынам, у гэтым выпадку, калі мы ітэрацыі, мы ведаем, што мы хочам, каб праверыць, Масіў п і п + 1 у парадку. Добра. Дык вось псевдокод. Мы хочам, каб праверыць, калі масіў н і н плюс 1 у парадку. Так што, магчыма, у нас там? Гэта будзе нейкі ўмоўны. Гэта будзе, калі. 

СТУДЕНТ: Калі масіў п менш масіва н плюс 1. Выкладчыкі: Мм-хм. Ну, менш ці больш, чым. СТУДЕНТ: Больш. Тады мы хочам памяняць іх месцамі. Дакладна. Так што цяпер мы трапляем у тое, што Механізм для перапампоўкі іх? Такім чынам, мы прайшлі праз гэтую коратка, тып функцыі падпампоўкі на мінулым тыдні. Хто-небудзь памятае, як ён працаваў? Такім чынам, мы не можам проста перадаць іх, ці не так? Таму што адзін з іх будзе губляцца. Калі мы сказалі, роўная Б, а той роўная A, усе раптам абодва проста роўная B. 

Такім чынам, што мы павінны зрабіць, гэта мы ёсць часовую зменную вось збіраецца правесці адзін з нашых-то час мы знаходзімся ў працэсе перапампоўкі. Так што ў нас ёсць, мы будзем мець некаторы Int Тэмпература роўная to-- можна прызначыць у залежнасці ад таго, што вы хочаце, проста пераканайцеся, што вы адсочваць it-- таму ў дадзеным выпадку, я збіраюся прызначыць яго на масіве н плюс 1. Так што адбываецца, каб змясціць усе Значэнне ў гэтым другім блоку што мы глядзім на. 

І тады мы можам зрабіць, гэта мы можам пайсці наперад, а таксама перапрызначацца масіў н плюс 1, таму што мы ведаем, што ёсць гэта значэнне захоўваецца. Гэта таксама з'яўляецца адным з вялікай things-- Я не ведаю, калі хто з вас былі праблемы, калі пры пераключэнні два радкоў кода раптам усё працавала. Замовіць вельмі важна ў CS. Таму пераканайцеся, што вы дыяграме рэчы, калі гэта магчыма адносна таго, што адбываецца на самай справе. Так што цяпер мы збіраемся перапрызначыць масіва п плюс 1, таму што мы ведаем, што ёсць гэта значэнне захоўваецца. 

І мы можам прызначыць, што ў масіве н а ў дадзеным выпадку масіў я. Занадта шмат зменных. Добра. Так што цяпер мы перакладзены масіў, які я плюс 1 роўным, што знаходзіцца ў масіве I. І зараз мы можам вярнуцца і прызначыць масіў я да чаго? Любы? 

СТУДЕНТ: 10. 

Выкладчыкі: 10. Дакладна. І апошняе. Калі мы памяняліся гэта цяпер, Што мы павінны зрабіць? Што адна справа што збіраецца расказаць нам калі мы калі-небудзь спыніць гэтую праграму? Што кажа нам, што мы ёсць адсартаваны спіс? Калі мы не выконваюць ніякіх свопов, ці не так? Калі свопы роўная нуля ў канцы гэтага. Таму, калі вы выканаць абмен, як мы толькі што зрабіў тут, мы хочам абнавіць свопы. І я ведаю, што было Пытанне раней аб можаш выкарыстоўваць нуль або адзін, а з праўдзівымі або ілжывымі. І вось што гэта робіць тут. Такім чынам, гэта кажа калі не свопы. Так што, калі свопы роўная нулю, што is-- я заўсёды атрымаць мае ісціны і мае falses пераблыталі. Мы хочам, каб нам ацаніць каб дакладна і гэта не так. Так што, калі гэта нуль, то гэта хлусня. Калі вы адмаўляць яго [? бац?] становіцца праўдай. Такім чынам гэтая лінія выконвае. 

Ісціны і хлусня, і нулі і адзінкі атрымаць з розуму. Проста, калі вы павольна хадзіць праз яго будзе мець сэнс. Але вось што гэта крыху кавалак кода тут робіць. Такім чынам, гэта правярае, мы зрабілі ніякіх свопов. Так што, калі гэта што-небудзь, акрамя нуля, гэта будзе хлусня і ўсё гэта з'яўляецца збіраецца выканаць зноў. Прахладны? 

СТУДЕНТ: Што перапынак зрабіць? 

Выкладчыкі: Перапынак проста ламае цябе з пятлі. Такім чынам, у дадзеным выпадку гэта было б гэтак жа, як завяршыць праграму і вы б проста ёсць свой адсартаваны спіс. СТУДЕНТ: Цудоўна. Выкладчыкі: Я шкадую? СТУДЕНТ: Таму што раней мы б напісаў 1 над напісана нуля ўявіць, што калі што будзе працаваць ці не. 

Выкладчыкі: Так. Такім чынам, вы можаце вярнуцца да нуля або 1. У гэтым выпадку, таму што мы на самай справе не рабіць што-небудзь з дапамогай функцыі, мы проста хочам, каб зламаць. Мы сапраўды не клапоцяцца пра гэта. Тармазная таксама добра, калі ён выкарыстоўваецца для выхаду з з чатырох завес або ўмоў, якія Вы не хочаце, каб выкананне. Гэта зойме вас з іх. Гэта нешта накшталт нюанс рэчы. Я адчуваю, што ёсць шмат ручной завіўкі, як вы даведаецеся пра гэта ў бліжэйшы час. 

Але вы даведаецеся пра гэта ў бліжэйшы час. Я абяцаю. Добра. Гэтак жа ўсе атрымліваюць пузырьковый сартавання? Ці не занадта дрэнна. Перабору, своп рэчы з дапамогай Пераменная тэмпература, і мы ўсё ж тут? Прахладны. Дзіўны. Добра. Вярнуцца да PowerPoint. Любыя пытанні ў цэлым аб іх да гэтага часу? Прахладны. Мм-хм. 

СТУДЕНТ: [неразборліва] Int асноўны звычайна. Вы павінны мець, што для гэтага? 

Выкладчыкі: Такім чынам, мы проста шукалі проста па фактычнай алгарытму сартавання. Калі вы мелі яго на працягу як вялікай праграмы, Вы б мець Int асноўны недзе. У залежнасці ад таго, дзе вы выкарыстаць гэты алгарытм, было б вызначыць, што вяртаецца да яе. Але для нашага выпадку, мы строга гледзячы на ​​тое, як гэта робіць на самай справе перабору масіва. Такім чынам, мы не турбавацца пра гэта. 

Такім чынам, мы гаворым аб лепшым выпадку і горшыя сцэнары для бінарнага пошуку. Так што гэта таксама важна зрабіць што для кожнага з нашых гатункаў. Так што вы думаеце, гэта горшы Справа часу выканання пузырьковый сартавання? Вы, хлопцы, памятаеце? 

СТУДЕНТ: N мінус 1. Выкладчыкі: N мінус 1. Значыць, ёсць н мінус 1 параўнання. Так адна справа разумець, што на першай ітэрацыі, мы ідзем да канца, мы параўнаем гэтыя two-- так вось 1. Гэтыя два, тры, чатыры. Такім чынам, пасля адной ітэрацыі мы ўжо ёсць чатыры параўнанняў. Калі я кажу пра час выканання і п. N ўяўляе сабой колькасць параўнанняў як функцыя ад таго, колькі элементаў у нас ёсць. Добра? 

Так мы ідзем да канца, у нас ёсць чатыры. У наступны раз, вы ведаеце, мы не павінны паклапаціцца пра гэта. Мы параўноўваем гэтыя два, гэтыя двое, гэтыя двое, і калі ў нас не было, што аптымізацыя з чатырма завесы, што я напісаў, Вы б параўноўваць тут у любым выпадку. Такім чынам, вы павінны былі б запусціць праз масіў і зрабіць п параўнанняў н раз, таму што кожны раз, калі мы запусціць праз гэта мы накшталт адно. 

І кожны раз, калі мы сутыкаемся з дапамогай масіў, мы робім п параўнанняў. Такім чынам, наша асяроддзе для гэтага на самай справе н квадрат, які значна горш, у нашым увайсці канцы, таму што, што значыць, калі ў нас было чатыры мільярд элементы, гэта збіраецца ўзяць нас чатыры мільярды квадрат замест 32. Дык ці не лепш серада, але для некаторых рэчаў, Вы ведаеце, калі вы на працягу пэўны дыяпазон элементаў пузырьковый сартаванне можа быць штраф, каб выкарыстаць. 

Добра. Так што цяпер, што гэта лепшы выпадак выканання? СТУДЕНТ: Нуль? Або 1? 

Выкладчыкі: Так 1 будзе адным параўнанне. Права. 

СТУДЕНТ: N мінус 1? 

Выкладчыкі: Дык што, так. Так н мінус 1. Кожны раз, калі ў вас ёсць такое паняцце, як п мінус 1, мы, як правіла, проста высадзіць яго і мы проста скажам, п, таму што вы ёсць параўнаць кожны з these-- кожнай пары. Таму было б н мінус 1, які мы мы проста скажам, прыкладна н. Калі вы маеце справу з выканання, усё ў набліжае. Да тых часоў, як экспаненты правільна, вы вельмі добра. 

Вось як мы з ёй змагаемся. Так што ў лепшым выпадку гэта п, азначае, што спіс ужо адсартаваны, і ўсё, што мы зрабіць, гэта запусціць праз і пераканайцеся, што гэта сартуюцца. Прахладны. Добра. Такім чынам, як вы бачыце тут, мы проста ёсць яшчэ некалькі графікаў. Так п квадрат. Fun. Значна горш, чым п, як мы бачым, і значна, значна горш, чым часопіса 2n. І тады вы таксама атрымліваеце ў часопісах часопісаў. І вы бераце 124, вы атрымаеце ў як лог зоркі, якая, як вар'ят. Так што калі вы зацікаўлены, пошук часопіса зорка. Гэта пацешна. Таму ў нас ёсць гэты вялікі графік. Проста галавы, гэта выдатны графік, каб мець для сярэднетэрміновай перспектыве, таму што мы доўга б задаць вам гэтыя радзее. Так проста галавы, ёсць гэта на Сярэднетэрміновай на добрым шпаргалку ёсць. Такім чынам, мы проста глядзелі на пузырьковый сартавання. У горшым выпадку, п квадрат, лепшы выпадак, п. І мы збіраемся глядзець на іншых. 

І як вы можаце бачыць, толькі той, які сапраўды добра з'яўляецца сартаванне зліццём, якія мы атрымаем у чаму. Такім чынам, мы збіраемся пайсці ў Наступны here-- выбар роду. Ці памятае хто-небудзь, як Выбар роду працаваў? Пайсці на гэта. 

СТУДЕНТ: У асноўным ідуць праз Парадак і стварыць новы спіс. І гэтак жа, як вы кладзеце элементы у, пакласці іх у правільным месцы ў новым спісе. 

Выкладчыкі: Так што гукі больш падобна ўстаўкі роду. Але вы сапраўды блізкія. Яны вельмі падобныя. Нават я блытаю часам. Перад гэтай частцы я быў як, чакаць. Добра. Так што вы хочаце зрабіць выбар роду, як вы можаце думаць, пра гэта і шляху Я пераконваюся, што стараюся не атрымаць блытаю, гэта праходзіць праз і ён выбірае найменшае лік, і гэта ставіць, што ў пачатку спісу. Гэта мяняе яго з той першай месцы. Яны на самай справе ёсць прыклад для мяне. Дзіўны. Так проста спосаб думаць аб it-- выбару роду, абярыце найменшае значэнне. І мы збіраемся праходзяць праз прыкладу што я думаю, што дапаможа, таму што Я думаю, што візуальныя заўсёды дапамагчы. Такім чынам, мы пачынаем з чым-то што цалкам без сартавання. Чырвоны будзе малокомплектных, зялёны будуць адсартаваныя. Гэта ўсё будзе мець сэнс у секунду. 

Такім чынам, мы прайсці і мы ітэрацыі ад пачатку і да канца. І мы кажам: ОК, 2 наш маленькі нумар. Такім чынам, мы збіраемся ўзяць 2, і мы збіраемся каб перанесьці яго на фронт нашага масіва таму што гэта Найменшая колькасць у нас ёсць. Дык вось што гэта робіць тут. Гэта проста будзе памяняць гэтыя два. Так што цяпер мы сартуюцца частку і малокомплектных частку. І тое, што добра памятаць аб выбары роду гэта мы толькі выбару ад неотсортированной часткі. 

Адсартаваны частка вы проста пакінуць у спакоі. Мм-хм? 

СТУДЕНТ: Як гэта ведаю, што гэта самы маленькі, ня параўноўваючы яго да кожнага іншага значэнні ў масіве. Выкладчыка, ён робіць параўнаць яго. Нам падабаецца прапусціў яго. Гэта проста наогул у цэлым. Так. Калі мы пішам код, я што вы будзеце больш задаволены. Але вы захоўваеце гэты першы Элемент як найменшае. Вы параўнайце, і вы сказаць, у парадку, гэта менш? Так. Трымаеце яго. Вось гэта менш? Няма? 

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

Так мінімальная роўная я. Гэта проста кажу ў дадзеным выпадку Індэкс нашай мінімальнага значэння. Такім чынам, што гэта збіраецца перабору і яна ідзе ад J роўная я плюс 1. Такім чынам, мы ўжо ведаем, што гэта наш першы элемент. Нам не трэба, каб параўнаць яго з сябе. Такім чынам, мы пачынаем параўноўваць яго з шэрагам адзін, які з'яўляецца, чаму гэта я плюс 1 да п мінус 1, якое з'яўляецца канец масіва там. І мы сказалі, што калі масіў на J з'яўляецца менш масіва мін, Затым мы перапрызначыць дзе нашы мінімальныя паказчыкі з'яўляецца. 

І калі мін не роўны I, як у якім мы ўжо былі тут. Бо калі мы ўпершыню зрабілі гэта. У гэтым выпадку, было б пачаць з нуля, гэта будзе ў канчатковым выніку два. Так мін не будзе роўная я, у рэшце рэшт. Гэта дазваляе нам ведаць, што мы павінны памяняць іх месцамі. Я адчуваю, што на канкрэтным прыкладзе дапаможа значна больш, чым гэта. Так што я буду кадзіраваць гэта з вамі, хлопцы прама зараз, і я думаю, што гэта будзе лепш. 

Гатункі, як правіла, працуе такім чынам у тым, што гэта часта лепш проста ўбачыць іх. Такім чынам, што мы хочам зрабіць, гэта спачатку мы хацелі найменшая элемент у яго пазіцыі ў масіве. Менавіта тое, што Якаў казаў. Вы павінны захаваць што-то. Такім чынам, мы збіраемся пачаць тут ітэрацыі па масіве. Мы збіраемся сказаць, што гэта наш Першы раз, каб пачаць з. Такім чынам, мы будзем мець Int маленькі роўная масіва ў I. 

Так што, адно заўважыць, кожны Час гэта цыкл выконваецца, мы пачынаем яшчэ адзін крок наперад разам. Калі мы пачынаем глядзець на гэтае. У наступны раз мы перабору, мы пачынаем у гэтым і прысваення яго нашым найменшае значэнне. Так што гэта вельмі падобна на пузырьковый сартавання дзе мы ведаем, што пасля аднаго праходу, гэта апошні элемент сартуецца. З выбару роду, гэта як раз наадварот. 

На кожным праходзе, мы ведаем, што Першы сартуецца. Пасля другога праходу, Другая будуць адсартаваныя. І, як вы бачылі на прыкладах слайд, наша сартуюцца частка проста працягвае расці. Так, усталяваўшы наш маленькі сябар для масіваў я, усё, што ён робіць з'яўляецца сціскаючы што мы глядзім на таго, каб звесці да мінімуму колькасць параўнанняў мы робім. Ці мае гэта сэнс для ўсіх? Вам патрэбен мне, каб прабегчы, што зноў павольней або рознымі словамі? Я шчаслівы. Добра. 

Такім чынам, мы захоўвання Значэнне ў гэтым пункце, але мы таксама хочам, каб захоўваць індэкс. Такім чынам, мы збіраемся захоўваць Становішча найменшая адзін, які толькі збіраецца быць, я. Так што цяпер Якаў задаволены. У нас ёсць рэчы, якія захоўваюцца. І зараз мы павінны глядзець праз без сартавання частка масіва. Такім чынам, у дадзеным выпадку гэта будзе наша малокомплектных. Гэта я. Добра. 

Такім чынам, што мы збіраемся зрабіць будзе для завесы. Кожны раз, калі вам трэба перабору масіва, Ваш розум можа пайсці для завесы. Такім чынам, для некаторых Int да equals-- што мы думаем Да збіраецца раўняцца пачаць? Гэта тое, што мы паставілі як наша маленькая каштоўнасць, і мы хочам, каб параўнаць яго. Што мы хочам, каб параўнаць яго з? Гэта збіраецца быць гэта наступны, ці не так? Таму мы хочам, K, каб ініцыялізаваць каб я плюс 1, каб пачаць. 

І мы хочам, каб да ў гэтым выпадку мы ўжо памер захоўваюцца тут, так што мы можам проста выкарыстоўваць памер. Памер быўшы памер масіва. І мы проста хочам, каб абнавіць K на адзінку кожны раз. Прахладны. Так што цяпер мы павінны знайсці найменшы элемент тут. Так што, калі мы перабору, мы хачу сказаць, калі масіў на да менш нашага маленькага value-- гэта дзе мы на самай справе адсочвання таго, што гэта самы маленькі here-- Затым мы хочам перадаць што наша маленькая велічыня. 

Гэта азначае, што, ну, мы перабору тут. Незалежна ад значэнне тут ня наш маленькі рэч. Мы не хочам яго. Мы хочам, каб перапрызначыць яго. Так што, калі мы перапрызначэння яго, што рабіць Вы думаеце, можа быць у гэтым кодзе тут? Мы хочам, каб перапрызначыць маленькі і становішча. Так што гэта самы маленькі ў цяперашні час? СТУДЕНТ: Array к. Выкладчыкі: Array к. І тое, што гэта становішча зараз? Што індэксы наша найменшае значэнне? Гэта проста к. Так масіва Да, Да, яны супадаюць. Такім чынам, мы хацелі перадаць гэта. А потым, калі мы выявілі, што наш маленькі, так у канцы гэтага для завесы Тут мы знайшлі тое, што наш маленькі значэнне, так што мы проста памяняць яго. У гэтым выпадку, як кажуць нашы Найменшае значэнне тут. Гэта наша найменшае значэнне. 

Мы проста хочам, каб памяняць яго тут, які з'яўляецца што гэта функцыя падпампоўкі на дне зрабіў, які мы толькі што напісалі разам пару хвілін таму. Так яно і павінна выглядаць знаёмым. І тады гэта будзе проста перабіраць праз пакуль ён не дасягне ўпора да канца, а гэта значыць, што вас маюць нулявыя элементы, якія без сартавання а ўсё астатняе было разабрацца. Зрабіць сэнс? Ледзь больш канкрэтна? Код дапамогу? 

не студэнты: Для памеру, вы ніколі сапраўды вызначыць або змяніць яго, як гэта даведацца? 

Выкладчыкі: Так адна справа заўважыць тут з'яўляецца памер унутр. Так мы кажам у гэтым sort-- роду ёсць функцыя ў гэтым case-- гэта Выбар роду, ён прайшоў У з функцыяй. Так што, калі ён не быў прыняты у, вы маглі б зрабіць што-то як з даўжынёй масіва ці вы б перабору каб знайсці даўжыню. Але таму што гэта прайшло ў, мы можам проста выкарыстоўваць яго. Вы проста выкажам здагадку, што карыстальнік даў вам правільны памер, што на самай справе ўяўляе памер вашага масіва. Прахладны? 

Калі вы, хлопцы, ёсць якія-небудзь праблемы з гэтым або хочаце больш практыкі кадавання віды па сваім меркаванні, вы павінны перайсці да study.cs50. Гэта інструмент. У іх ёсць праверкі, што Вы можаце фактычна пісаць. Яны робяць псевдокод. Яны маюць больш відэа і слайды у тым ліку і я выкарыстоўваю тут. Так што калі вы ўсё яшчэ адчуваеце трохі невыразнай, паспрабуйце гэта. Як заўсёды, прыйшоў пагаварыць са мной, таксама. Пытанне? 

СТУДЕНТ: Вы хочаце сказаць, памер вызначана раней? Выкладчыкі: Так. Памер папярэдне вызначана з дакладнасцю тут у аб'яве функцыі. Такім чынам, вы выказаць здагадку, што гэта было прынята ў карыстальнікам, і для прастаты, мы будзем лічыць, што Карыстальнік даў нам правільны памер. Прахладны. Дык вось выбар роду. Хлопцы, я ведаю, сёння мы даведаліся шмат. Гэта шчыльная дадзеныя для часткі. Так з гэтым, мы збіраемся пайсці ў сартаванне ўстаўкамі. 

Добра. Таму, перш чым, што мы павінны зрабіць, наш аналіз выканання тут. Такім чынам, у лепшым выпадку, прадастаўляецца, так як я паказаў вам, табліца я ўжо выгляд аддаў яго. Але лепш за ўсё справа часу выканання, што мы думаем? Усе Сартаваць. N ў квадраце. Любы, ёсць тлумачэнне чаму вы думаеце? 

СТУДЕНТ: вы параўноўваеце through-- Выкладчыкі: справа. Ты параўнання праз. На кожнай ітэрацыі, нягледзячы на ​​тое, мы памяншаючы гэта адзін, Вы ўсё яшчэ шукаеце праз усё, каб знайсці самыя маленькія. Такім чынам, нават калі ваша найменшае значэнне Тут у пачатку, Вы ўсё яшчэ параўноўваючы яго супраць усяго астатняга каб пераканацца, што гэта самае малое. Такім чынам, вы будзеце ў канчатковым выніку працуе праз прыкладна н квадраце раз. Добра. І тое, што ў горшым выпадку? Таксама п квадраце, таму што вы збіраецеся каб рабіць тую ж самую працэдуру. Так, у дадзеным выпадку, выбар накшталт ёсць што-то што мы называем чаканы час выканання. Такім чынам, у іншых, мы проста ведаем, верхнія і ніжнія межы. У залежнасці ад таго, як з розуму нашага Спіс або як малокомплектных гэта, яны адрозніваюцца паміж п або п квадрата. Мы не ведаем. 

Але з-за выбару роду мае тое ж самае горшае і лепшае справа, што кажа нам, што незалежна ад таго, які тып ўводу мы ёсць, ці з'яўляецца гэта цалкам сартуюцца або цалкам зваротная сартуюцца, гэта збіраецца ўзяць такое ж колькасць часу. Так што ў гэтым выпадку, калі вы памятаеце з нашай табліцы, ён на самай справе мае значэнне, што гэтыя два выгляду не маюць, які, як чакаецца, падчас выканання. Такім чынам, мы ведаем, што кожны раз, калі мы бяжым выбару роду, гэта гарантавана запусціць н квадраце час. Там няма зменлівасць ёсць. Гэта проста чакаў. І, зноў жа, калі вы хочаце даведацца, Больш за тое, прыняць CS 124 вясной. Добра. Мы бачылі гэта. Прахладны. Так уставак. І я, верагодна, пракласці праз гэта. Я не дазволю табе хлопцы кадзіраваць яго. Мы проста прайсці праз гэта. Так уставак добры з падобны на выбар роду у тым, што ў нас ёсць і малокомплектных і сартуюць частка масіва. 

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

Таму што вы знаходзіцеся ў спісе самастойна, вы сартуюцца. Віншуем быць Першы элемент у гэтым масіве. Вы ўжо адсартаваныя усё па сваім меркаванні. Так што цяпер мы сартуюцца і малокомплектных масіў. Так што цяпер мы возьмем першы. Што адбываецца паміж тут і ў тым, што мы кажам: Добра, мы будзем глядзець на Першае значэнне нашай малокомплектных масіва і мы збіраемся ўвесці яго ў сваёй правільнае месца ў масіве. 

Такім чынам, што мы робім, мы бярэм 5 і мы кажам, добра, 5 больш 3, так што мы проста ўстаўце яго права справа, што. Мы добра. Такім чынам мы пераходзім да нашай наступнай. І мы бярэм 2. Мы кажам, добра, 2 менш чым 3, так што мы ведаем, што гэта павінен быць у Фронт нашым спісе цяпер. Так што мы робім, мы націскаем 3 і 5 ўніз і мы рухаемся 2 у той першы слот. Такім чынам, мы проста уставіўшы яго ў правільнае месца гэта павінна быць. 

Тады мы паглядзім на наш Наступны, і мы кажам, 6. ОК, 6 больш, чым усё ў нашым масіве, так што мы проста пазначыць яго да канца. А потым мы глядзім на 4. 4 менш, чым 6, гэта менш, чым 5, але гэта больш, чым 3. Так што мы проста ўставіць яго прама ў пасярэдзіне паміж 3 і 5. Такім чынам, каб зрабіць што крыху трохі больш канкрэтнымі, вось накшталт Ідэя пра тое, што адбылося. Такім чынам, для кожнага малокомплектных элемента, мы вызначыць, дзе ў адсартаваным часткі гэта. 

Так маючы на ​​ўвазе, у сартуюцца і малокомплектных, мы павінны прайсці праз і фігура , Дзе яна ўпісваецца ў масіве. І мы ўстаўляем яго, зрушваючы элементы справа ад яго ўніз. А потым мы проста трымаць ня перабор, пакуль мы ёсць цалкам адсартаваны спіс дзе малокомплектных цяпер роўна нуля і адсартаваны займае Сукупнасць нашым спісе. Так, зноў жа, каб зрабіць рэчы яшчэ больш канкрэтнае, у нас ёсць псевдокода. 

Таму ў асноўным для я гэта роўная 0 да п мінус 1, вось толькі даўжыня нашага масіва. Мы маем некаторы элемент, які роўны Першы масіў або першыя паказчыкі. Мы ставім J, роўную. Такім чынам, хоць J больш нуля, а масіў, J мінус 1 больш, чым элемент, так што ўсё, што робіць пераканаўшыся, што Ваша J сапраўды ўяўляе без сартавання частка масіва. 

Так, пакуль яшчэ ёсць рэчы, сартаваць і J мінус адзін is-- што з'яўляецца элементам яе? J ніколі не вызначаецца тут. Гэта свайго роду раздражняе. Добра. У любым выпадку. Так J мінус 1, вы правяраеце элемент перад ім. Вы хочаце сказаць, што, у парадку, гэта элемент да куды б я ні am-- давайце на самай справе зрабіць гэта. Так скажам, гэта як на нашым другім праходзе. Так што я будзе роўная 1, якая знаходзіцца тут. 

Такім чынам, я маю намер быць роўны 1. Гэта было б 2, 4, 5, 6, 7. Добра. Такім чынам, наш элемент у дадзеным выпадку будзе роўная 4. І ў нас ёсць некаторы J Вось будзе роўная 1. О, J з'яўляецца памяншаючы. Вось што гэта такое. Так J роўная I, так што гэта гаворыцца, што, як мы рухаемся наперад, мы толькі пераканаўшыся, што мы не больш індэксацыі гэты шлях, калі мы спрабуем ўставіць рэчы ў нашым спарадкаваным спісе. 

Таму, калі J роўны 1, у гэтым выпадку і Масіў J мінус одно-- так масіў J мінус 1 2 у гэтым case-- калі гэта больш, чым элемент, Затым усё гэта робіць ссоўваецца рэчы ўніз. Так, у дадзеным выпадку, масіў J мінус адзін Масіў будзе нулявым, які з'яўляецца 2. 2 не болей, чым 4, так што гэта не выконваецца. Так зрух ня з'язджаць. Што гэта робіць тут проста перасоўванне адсартаваны масіў ўніз. У гэтым выпадку, на самай справе, мы можа do-- давайце зробім гэта 3. Так што, калі мы хочам ісці праз з гэты прыклад, мы зараз тут. Гэта сартуецца. Гэта малокомплектных. Прахладны? Так я роўны 2, так наш элемент роўны 3. І наша J роўная 2. Такім чынам, мы з нецярпеннем праз і мы сказаць, у парадку, гэта масіў J мінус адзін больш, чым элемента што мы глядзім? І так, ці не так? 4 больш, чым 3 і J 2, так што гэты код выконваецца. 

Так што цяпер, што мы робім масіў на 2, так прама тут, мы памяняць іх месцамі. Такім чынам, мы проста сказаць: ОК, масіў на 2 зараз будзе 3. І J збіраецца раўняцца J мінус 1, які роўны 1. Гэта жахліва, але вы, хлопцы, атрымаеце гэтую ідэю. J цяпер роўная 1. І масіў J толькі збіраецца быць роўная нашага элемента, які быў 4. Я сцёр што-то я не павінен ёсць або miswrote-то, але вы, хлопцы, атрымаеце гэтую ідэю. 

Гэта рухацца ў п. І потым, калі б гэта было, гэта было б пятля зноў, і гэта было б сказаць, у парадку, J = 1 зараз. І масіў J мінус 1 цяпер 2. Ёсць 2 менш, чым нашы элемента? Няма? Гэта азначае, што мы ў ўстаўляецца гэты элемент ў правільным месцы ў нашым масіве. Тады мы можам узяць гэта, і мы кажам, ОК, наш спарадкаваны масіў тут. І гэта было б узяць гэты нумар 6 і быць як, у парадку, складае 6 менш, чым гэты лік? Няма? Прахладны. У нас усё добра. 

Зрабіце гэта зноў. Мы кажам, 7. З'яўляецца 7 менш, чым у канцы нашай масіве? Няма. Так што мы ў парадку. Так што гэта будзе адсартаваны. У асноўным усё гэта робіць Хіба гэта кажа дубль Першы элемент Ваш малокомплектных масіў, высветліць, дзе ён ідзе ў масіве. І гэта толькі клапоціцца свопов, каб зрабіць гэта. Вы ў асноўным проста памяняўшы пакуль гэта не ў патрэбным месцы. Візуальны вобраз, што вы рухаецца ўсё ўніз, робячы гэта. 

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

Так накшталт сыходзіць ад таго, што мы казалі аб нашых папярэдніх радах, горшае Справа ў тым, што ў час выканання, калі гэта цалкам Unsorted, мы павінны параўнаць ўсе гэтыя п раз. Мы робім кучу параўнанняў таму што, калі гэта ў зваротным парадку, мы збіраемся сказаць, у парадку, гэта гэта тое ж самае, гэта добра, і гэты павінен будзе параўноўвацца супраць першага перанесці назад. І, як мы атрымаем да канец хваста, у нас ёсць параўноўваць, супастаўляць, і параўнаць супраць усяго. 

Так ён апынуўся прыкладна н квадрат. Калі гэта правільна, то вы сказаць, у парадку, 2, вы добра. 3, вы па параўнанні з 2. Ты добры. 4, вы проста параўнайце з хвастом. Ты добры. 6, у параўнанні з хваста, вы выдатныя. Такім чынам, для кожнага месца, калі гэта ўжо сартуюцца, вы робіце адно параўнанне. Так што гэта проста п. І таму, што ў нас ёсць лепшы выпадак выканання п і горшым выпадку выканання п квадрат, у нас няма ніякай чаканага выканання. 

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

Хто-небудзь хоча сказаць? Вы хочаце паспрабаваць? Так рэкурсіўная функцыя з'яўляецца проста функцыя, якая называе сябе. Так што, калі вы, хлопцы, знаёмыя з паслядоўнасцю Фібаначы, які лічыцца рэкурсіўнай таму вы бераце дзве папярэднія і дадаць іх разам каб атрымаць наступны. Так рэкурсыўнай, я заўсёды думаю, рэкурсіі як як спіраль так што вы, як па спіралі ўніз ў яго. Але гэта ўсяго толькі функцыя якая называе сябе. 

І, на самай справе, вельмі хутка я можа паказаць вам, як гэта выглядае. Так рэкурсіўны тут, калі мы паглядзім, што гэта рэкурсіўны спосаб сумаваць масіў. Так што ўсё, што мы робім, у нас ёсць функцыя сумы Сума, якая прымае памер і масіў. І калі вы заўважылі, памер памяншаецца на адзінку кожны раз. І ўсё гэта робіць, калі х роўна zero-- так што калі памер масіва роўная zero-- вяртаецца нуль. 

У адваротным выпадку гэта падводзіць гэта Апошні элемент масіва, а затым прымае суму астатняя частка масіва. Так што гэта проста разбіць яго на ўсё больш дробныя праблемы. Карацей кажучы, рэкурсіі, Функцыя, якая называе сябе. Калі гэта ўсё, што вы выйшлі з гэтага, гэта тое, што рэкурсіўная функцыя. Калі ўзяць 51, вы атрымаеце вельмі, вельмі зручна з дапамогай рэкурсіі. Гэта сапраўды выдатна. Гэта мела сэнс у падобным 3 раніцы аднойчы ноччу. І я падумала: чаму ня я не выкарыстоўваю гэта? 

Такім чынам, для сартавання зліццём, у асноўным што ён збіраецца зрабіць, гэта гэта збіраюся разбіць яго і разбіць яго ўніз, пакуль гэта не проста асобныя элементы. Асобныя элементы лёгка адсартаваць. Мы бачым, што. Калі ў вас ёсць адзін элемент, гэта ўжо лічыцца адсартаваны. Так на ўваходзе п элементаў, калі п менш, чым 2, проста вярнуць, таму што гэта азначае, што гэта альбо 0, або 1, як мы ўжо бачылі. Тыя, лічацца адсартаваныя элементы. 

У адваротным выпадку разарваць яго напалову. Сартаваць першую палову, адсартаваць другі палова, а затым аб'яднаць іх разам. Чаму гэта называецца сартаванне зліццём. Такім чынам, мы маем тут мы будзем сартаваць гэтыя. Так мы працягваем мець іх да таго часу, пакуль памер масіва роўны 1. Таму, калі гэта 1, мы проста вярнуцца таму што гэта спарадкаваны масіў, і гэта спарадкаваны масіў, і гэта спарадкаваны масіў, мы ўсё разабраліся. Такім чынам, што мы робім, мы пачаць зліццё іх разам. 

Так як вы можаце думаць пра зліццё Вы проста выдаліце ​​менш Колькасць кожнага з масіваў суб і проста дадаць яго ў сітуацыі, якая масіва. Так што, калі вы паглядзіце тут, калі ў нас ёсць гэтыя наборы ў нас ёсць 4, 6 і 1. Калі мы хочам аб'яднаць гэтыя, мы глядзім на гэтых першых двух і мы кажам, добра, 1 менш, ён ідзе на фронт. 4 і 6, няма нічога, каб параўнаць гэта, проста пазначыць яго да канца. 

Калі мы аб'яднаем гэтыя два, мы проста ўзяць меншы адзін з гэтых двух, так што гэта 1. А цяпер возьмем Меншае з гэтых двух, так 2. Менш гэтых двух, 3. Менш гэтых двух, 4, 5, 6. Такім чынам, вы проста сцягваючы іх. І таму, што ў іх ёсць адсартаваныя раней, Вы толькі адзін з іх Параўнанне кожны раз там. Так больш кода тут, проста паданне. Такім чынам, вы пачынаеце ў сярэдзіне і вы як бы левы і правы а затым вы проста аб'яднаць тых. 

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

Паглядзіце, як шмат лепш, што ёсць. Такі добры крывая. Так значна больш эфектыўным. Калі вы калі-небудзь можа, выкарыстанне сартаванне зліццём. Гэта дапаможа вам зэканоміць час. З іншага боку, як мы ўжо казалі, калі вы ўніз ў гэтай ніжняй галіне, гэта не робіць, што асаблівай розніцы. Вы атрымліваеце да тысячы і тысячы уваходаў, вы вызначана хочаце больш эфектыўны алгарытм. І, зноў жа, наша выдатная табліца ўсіх віды, што вы, хлопцы даведаліся сёння. 

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

Дык вось менавіта для часткі. Ўніз да провада. Я зрабіў гэта на працягу адной хвіліны. Але там вы ідзяце. І ў мяне будзе пончыкі або цукеркі. Хто-небудзь алергія на што-небудзь, дарэчы? Яйкі і малако. Так што пончыкі ня? Добра. Добра. Шакалад не? Starburst. Starbursts добрыя. Добра. Мы збіраемся мець Starburst на наступным тыдні, то. Гэта тое, што я атрымаю. Вы, хлопцы, ёсць вялікая тыдзень. Прачытайце спецыфікацыю. 

Дайце мне ведаць, калі ў вас ёсць якія-небудзь пытанні. Pset два гатункі павінны быць да вас на чацвер. Калі ў вас ёсць якія-небудзь пытанні пра тое, як я класіфікуюцца што-то ці чаму я класіфікуюцца што-то, як я так, калі ласка, напішыце мне, прыходзяць пагаварыць са мной. Я ледзь з розуму ў гэтым тыдзень, але я абяцаю, Я да гэтага часу адказаць на працягу 24 гадзін. Так ёсць вялікі тыдзень, усё. Ўдачы на ​​PSET.