[Гуляе музыка] 

ANDI Пэн: Сардэчна запрашаем у тыдзень 3 падзелу. Дзякуй, што вы, хлопцы, ўсе, хто прыходзіў на у гэтым больш ранні час пачатку сёння. Мы атрымалі добры, трохі інтымная група сёння. Так што спадзяюся, мы дабяромся да аздабленне, мабыць, рана, трохі крыху раней. Так хутка, проста некаторыя Анонсы парадку дня сёння. Перш чым мы пачнем, мы збіраюся проста перайсці некаторыя кароткія матэрыяльна-тэхнічных пытанняў, PSET пытанні, Інструктаж, такія рэчы, як, што. І тады мы будзем ныраць прама ў. Мы будзем выкарыстоўваць адладчык GDB пад назвай, каб пачаць развянчання наш код, які Дэвід растлумачыў у лекцыі ў іншы дзень. Мы пойдзем на працягу чатырох відаў роду. Мы пойдзем на іх даволі хутка так як яны даволі інтэнсіўна. Але ведайце, што ўсе слайды і Зыходны код заўсёды анлайн. Так што не саромейцеся, у вашым чытанні, каб вярнуцца назад і зірнуць на гэта. 

Мы пойдзем праз асімптатычнай абазначэння, якія гэта проста мудрагелісты спосаб сказаць "час аўтаномнай працы", дзе ў нас ёсць вялікі O, якая Дэвід растлумачыў у лекцыі. І ў нас таксама ёсць Omega, які гэта ніжняя мяжа часу выканання. І мы будзем казаць трохі больш у глыбіні пра тое, як гэтыя працы. І, нарэшце, мы пойдзем па бінарнага пошуку, таму што многія з вас, хто ўжо зірнуў на вашых psets, напэўна, ведаеце, што што гэта пытанне, які знаходзіцца ў вашым PSET. Такім чынам, вы будзеце ўсе будуць шчаслівыя што мы разгледзім гэта сёння. 

І, нарэшце, за ваш раздзел зваротнай сувязі, я на самой справе засталося каля 15 хвілін пры канец проста перайсці лагістыка pset3, якія-небудзь пытанні, можа быць, трохі кіраўніцтвам, калі хочаце, перш чым мы пачнем праграмаванне. Так давайце паспрабуем атрымаць праз матэрыял даволі хутка. І тады мы можам правесці некаторы час прымаючы больш пытанняў для PSET. ДОБРА. 

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

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

Аднак ёсць Некалькі пытанняў Танто Я проста хачу, каб перайсці на што як бы жыццё і шмат іншага ТП «жыве крыху лягчэй. Па-першае, я заўважыў гэта міма week-- як многія з вас былі працуе на check50 код, перш чым прадставіць? ДОБРА. Такім чынам, кожны павінен рабіць check50, because-- secret-- мы на самай справе запусціць check50 як частка нашай праваце скрыпты для тэставання кода. Так што, калі ваш код не атрымоўваецца check50, па ўсёй верагоднасці, гэта, верагодна, будзе пацярпець няўдачу таксама наш чэк. Часам вы, хлопцы, ёсць правільныя адказы. Маўляў, у прагныя, некаторыя з ў вас ёсць правільныя лічбы, Вы проста раздрукаваць некаторыя дадатковыя рэчы. І, што дадатковы матэрыял на самай справе не праходзіць праверку, таму што кампутар не ведаю, што ён шукае. І так будзе проста запусціць праз, бачыць, што ваш вывад не адпавядае таму, што мы чакаем адказ быць, і адзначце, што гэта няправільна. 

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

Акрамя таго, у psets за пятніцах апоўдні. Я думаю, што ёсць сем хвілін ў канцы ільготнага перыяду, што мы даем вам. За час Гарвардскага, яны дазволілі сем хвілін позна, каб усім. Дык вось у Ельскім універсітэце, мы будзем прытрымлівацца, што добра. Але даволі шмат, у 00:07, калі ваш PSET гэта не ў тым, гэта будзе адзначаны як позна. І таму, хоць яна адзначаецца а позна, я TA-- ранейшаму будзе класіфікацыі вашыя psets. Такім чынам, вы ўсё яшчэ будзеце бачыць гатунак з'яўляюцца. Тым не менш, вядома, што ў канец семестра, усе пазнейшыя psets будзе проста аўтаматычна абнуляецца з дапамогай кампутара. 

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

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

АЎДЫТОРЫЯ: Вы сказалі, мы можа ўпасці адзін з psets? 

ANDI Пэн: Так. Так што ў цэлым дзевяць psets на працягу семестра. І калі ў вас ёсць вобласць points-- так проста сфера, даволі шмат, вы спробай выканання Праблема, вы пакласці ў час, вы паказваеце, што вы маеце прадэманстравалі вы чыталі спецыфікацыі. Гэта даволі шмат магчымасцяў. І калі вы выконваеце Сфера пункту, мы можа ўпасці самая нізкая адным з поўным аб'ёме. Дык вось у вашых інтарэсах, каб запоўніць і паспрабаваць усё PSET. 

Нават калі upload-- ні адзін з ім працаваць, загружаць іх усе. І тады мы будзем, мы спадзяемся, змогуць даць вам некаторыя з гэтых кропак назад. Прахладны. Любыя іншыя пытанні? Выдатна. 

Па-другое, офіс hours-- некалькі хуткія нататкі аб працоўных гадзін. Такім чынам, спачатку прыходзяць у пачатку тыдня. Ніхто не калі-небудзь у Прыёмныя гадзіны па панядзелках. Christabel прыйшлі да Прыёмныя гадзіны мінулай ноччу. Так, Christabel. І што мы маем у офісе гадзін мінулай ноччу, Christabel? 

АЎДЫТОРЫЯ: У нас было марозіва. 

ANDI Пэн: Так што гэта правільна, мы павінны былі марозіва на офісных гадзін ўчора ўвечары. Хоць я не магу абяцаць вам, што мы будзем мець марозіва ў працоўны час кожны тыдзень, што я магу абяцаць вам, з'яўляецца тое, што будзе значна лепш студэнт суадносіны TA. Як законна, гэта як тры да аднаго. Прымаючы пад увагу, што з кантрастуюць Чацвер, у вас ёсць каля 150 сапраўды падкрэсліў дзяцей і не марозіва. І гэта проста не прадуктыўна для ўсіх. Так Мараль гэтай гісторыі ў тым, прыйсці крыху раней у працоўны час і добрыя рэчы адбудзецца. 

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

Па-другое, так што я ведаю прафесараў хацеў здзівіць нас з тэстамі. Я быў прафесарам тыя як, йо, дарэчы, памятаеце, што сярэднетэрміновай ў вас ёсць наступны панядзелак. Так, я не ведаю, пра тое, што сярэднетэрміновай. Так што я збіраюся быць, што ТАЯ што нагадвае вам усё, што віктарыну 0-- таму што, вы ведаеце, мы CS. Цяпер, калі мы зрабілі масівы, вы атрымаеце чаму гэта віктарына 0, не віктарыны 1, а? ДОБРА. О, я атрымаў некаторыя смяшкі на тым, што адзін. ДОБРА. 

Так віктарыны 0 будзе 14 кастрычніка, калі Вы знаходзіцеся ў раздзеле панядзелак-сераду і 15 кастрычніка, калі вы знаходзіцеся ў раздзел аўторак-чацвер. Гэта не распаўсюджваецца на тых з вас, у Гарвардзе who-- Я думаю, вы ўсё будзеце прымаць вашыя апытанні на 14-м. 

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

АЎДЫТОРЫЯ: Так віктарыны будзе на лекцыі? 

ANDI Пэн: Так. Так віктарыны, я думаю, 60 хвілін, выдзеленыя ў гэтым часовым інтэрвале што вы будзеце проста ўзяць у лекцыйным зале. Такім чынам, вы не павінны прыйсці ў на, быццам бы, выпадковага 07:00 PM. Гэта ўсё добра. Так. Прахладны. 

Добра. Такім чынам, мы збіраемся, каб ўвесці паняцце для вас На гэтым тыдні, што Дэвід ўжо накшталт з закранулі ў лекцыі на мінулым тыдні. Гэта называецца GDB. І, як многія з вас, у той час як у курс напісання psets, заўважыў вялікую кнопку, якая кажа "Адладка" на верхняй часткі IDE? ДОБРА. Так што цяпер мы на самай справе атрымаць, каб раскапаць таямніца які то кнопкі на самай справе робіць. І я гарантую вам, што гэта прыгожая, прыгожая рэч. 

Так да гэтага часу, я думаю, там было дзве рэчы студэнты былі, як правіла, рабіць пры адладцы psets. Адзін з іх, яны альбо дадаць у Е () - так кожныя некалькі ліній, яны дадаюць у Е () - ой, што гэта зменная? О, што гэта зменная now-- і вы, здаецца, убачыць прагрэсаванне ваш код, як гэта працуе. Ці другі спосаб зрабіць дзяцей што яны проста напісаць цэлую рэч а затым перайсці, як гэта ў рэшце рэшт. Спадзяюся, гэта працуе. Я гарантую вам, GDB лепш чым абодва з гэтых метадаў. Так. Так што гэта будзе ваш новы лепшы сябар. Таму што гэта прыгожая рэч якія візуальна адлюстроўвае як што ваш код робіць у пэўны момант а таксама тое, што ўсе вашыя зменныя правядзення, як тое, што іх значэння, ў гэтай канкрэтнай кропцы. І такім чынам, вы можаце сапраўды ўсталяваць кропкі супыну ў кодзе. Вы можаце запусціць праз лінію за лініяй. І GDB будзе проста для Вы, адлюстроўваецца для вас, тое, што ўсе вашыя зменныя якія, што яны робяць, што адбываецца ў кодзе. І такім чынам, гэта так лягчэй ўбачыць што замест адбываецца з-тав PRINTF або запісваючы свае заявы. 

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

Так можа вы, хлопцы, усе бачыць, што ці я павінен павялічыць трохі? У спіну, вы можаце бачыць, што? Ці павінен я павялічыць? Проста трохі? ОК, крута. Там мы ідзем. ДОБРА. 

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

Так, аднак, у той час як гэты код вельмі прыгожа, гэта не працуе належным чынам. Так што давайце працаваць check50 на гэтым. Праверце 50 20-- уп. 2? Гэта pset2? Так. О, pset1. ДОБРА. Такім чынам, мы працаваць check50. 

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

ДОБРА. Такім чынам, давайце паглядзім, адно з правярае мяне няўдачу ў check50 быў уваходнае значэнне 0,41. Такім чынам, правільны адказ, што вы павінны атрымліваць гэта 4. Але замест таго, што я раздрукоўкі гэта 3-н, што няправільна. Так што давайце проста запусціць ўручную, проста пераканайцеся, што check50 працуе. Давайце зробім ./greedy. Ой, я павінен зрабіць прагны. Там мы ідзем. Цяпер ./greedy. 

Колькі належыць? Давайце зробім 0.41. І так, мы бачым тут што гэта выснова 3 калі правільны адказ, На самай справе, павінна быць 4. Так што давайце ўвесці GDB і паглядзець, як мы можа ісці аб фіксацыі гэтай праблемы. 

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

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

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

Так давайце пройдзем, лінію лінія, тое, што тут адбываецца. ДОБРА. Так тут з'яўляюцца тры кнопкі, якія я толькі што патлумачыў. Вы павінны гуляць, ці функцыю Run, Кнопка, у вас ёсць Крок за кнопку, і ў вас таксама ёсць Крок у кнопкі. І, па сутнасці, усе тры ім проста прайсці праз код і рабіць розныя рэчы. 

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

Так Крок над функцыяй толькі пераступае кожнага радка і кажа вам, што кампутар робіць. Крок у функцыі ідзе у рэальнай функцыі гэта на радку кода. Так, напрыклад, як Е (), , Якая з'яўляецца функцыяй, праўда? Калі б я хацеў, каб фізічна крок у функцыі Е (), Я б на самой справе ісці ў частцы Код, дзе Е () была напісана і паглядзець, тое, што там адбываецца. 

Але, як правіла, мы мяркуем, што код, які мы даем вам працы. Мы мяркуем, што Е () працуе. Мы мяркуем, што GetInt () працуе. Такім чынам, няма ніякай неабходнасці крок у гэтых функцый. Але калі ёсць функцыі што вы пішаце самі што вы хочаце, каб праверыць , Што адбываецца, Вы хацелі б крок у гэтай функцыі. 

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

Так п, якая з'яўляецца нашым паплавок, што мы ў initialized-- або declared-- наверсе, мы цяпер роўная, што GetFloat (). Такім чынам, давайце пераступіць што. І мы бачым, на Ніжняя тут, праграма падахвочвае мяне да ўваходу значэнне. Такім чынам, давайце Увядзіце значэнне мы хочам праверыць тут, што 0,41. Выдатна. 

Так што цяпер N-- вы, хлопцы, бачыце тут, на bottom-- гэта stored--, таму што мы яшчэ не акругляецца, гэта захоўваюцца ў гэтым, як гігант паплавок, які ,4099999996, які знаходзіцца досыць блізка да нашага Мэты, прама зараз, да 0,41. І тады мы ўбачым у далейшым, як мы працягваць прасоўванне па праграме, Пасля тут, н стала круглявыя і цэнтаў стала 41. Выдатна. Такім чынам, мы ведаем, што праца нашай акруглення ст. Мы ведаем, што ў нас ёсць правільнае лік цэнтаў, так што мы ведаем, што гэта на самай справе не праблема. 

Такім чынам, мы па-ранейшаму крочыць у гэтай праграме. Мы ідзем сюды. І так пасля гэтага радка кода, мы павінны ведаць, колькі чвэрці ў нас ёсць. Мы пераступіць. І вы бачыце, мы, на самой справе, ёсць адзін чвэрць, таму што мы вычыталі 25 з нашага пачатковага значэння 41. І ў нас ёсць 16 застаецца нашым цэнтаў. 

Ці разумее ўсё, як праграма пакрокавага і чаму цэнтаў стала 16 і чаму, у цяперашні час, манеты стаў 1? Усе наступнае, што логіка? Прахладны. Так, як у дадзены момант, Рабочая праграма, праўда? Мы ведаем, што гэта менавіта рабіць тое, што мы хочам. І мы на самай справе не павінны раздрукаваць, ах, які з'яўляецца цэнтаў на дадзены момант, што манеты ў гэтай кропцы. 

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

Пяройдзем драбяза, і мы бачым што мы атрымалі, тыя, што засталіся цэнтаў. Хм, гэта дзіўна. Да тут праграмы, я павінен быў каб аднялі мае драбяза. Можа быць, я проста не быў робіць гэты радок права. І, на жаль, вы можаце ўбачыць тут, таму што мы ведаем, што мы ўступаем праз лініі 32 і 33, вось дзе наша праграма няправільна было зменныя працаваць. Такім чынам, мы можам паглядзець і ўбачыць, аб, Я аднімання цэнтаў тут, але я на самой справе не дадаючы да маёй кошту манеты. Я дадаю да цэнтаў. І я не хачу, каб дадаць да цэнтаў, я хачу, каб дадаць да манетах. Так што, калі мы мяняем што манеты, мы атрымалі рабочую праграму. Я магу запусціць check50. Вы можаце проста выйсці з GDB правы тут і затым запусціць check50 зноў. Я мог бы проста зрабіць гэта. Я павінен зрабіць прагны. 0,41. І вось, гэта друк з правільнага адказу. 

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

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

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

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

Так што выдатна, таму што, калі мы кажам пра змест у lecture-- або прабачце, у section-- Мне падабаецца звязаць шмат, што таму да таго, што гэта PSET і як вы хочаце, каб ажыццявіць, што ў вашым PSET. Так што, калі вы прыходзіце, якія маюць чытаць спецыфікацыі, ён будзе будзе нашмат прасцей для вас, каб зразумець, тое, што я кажу пра тое, калі я кажу, эй, гэта можа быць сапраўды добрае месца для рэалізацыі такога роду. Так што тыя, з вас, хто чытаў особое_разрешение ведаю, што, як частка вашага PSET, Вы будзеце мець, каб напісаць тып роду. Так што гэта можа быць вельмі карысна для многіх з вас сёння. 

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

І вось нагляднае тлумачэнне пра тое, як гэта будзе працаваць. Так, напрыклад, калі мы павінны былі пачаць з масівам з пяці элементаў, індэкс Ад 0 да 4, з 3, 5, 2, 6, і 4 значэння змешчаны ў array-- гэта прама цяпер, мы проста будзем лічыць, што яны ўсе без сартавання таму што мы не зведалі ў адваротным выпадку. 

Бо выбар роду будзе праца, што б перш праходзяць праз цалкам у малокомплектных масіва. Было б выбраць найменшае значэнне. У гэтым выпадку, 3, правы Цяпер, з'яўляецца найменшай. Ён атрымлівае да 5. Няма, 5 не болей than-- або прабачце, не менш за 3 than--. Такім чынам, мінімальнае значэнне па-ранейшаму 3. І тады вы атрымаеце 2. Кампутар бачыць, ой, 2 менш, чым 3. Цяпер 2 павінна быць мінімальная значэнне. І так 2 свопы з гэтай першай велічыні. 

Такім чынам, пасля аднаго праходу, мы сапраўды бачым што 2 і 3 мяняюцца месцамі. І мы толькі збіраемся працягваць рабіць Гэта зноў з астатняй часткай масіва. Такім чынам, мы збіраемся, каб проста запусціць праз Апошнія чатыры індэксы масіва. Мы ўбачым, што 3 наступны мінімальнае значэнне. Такім чынам, мы збіраемся, каб памяняць што з 4. І тады мы проста будзем працягваць не праходзіць праз да, у рэшце рэшт, вы трапіць у адсартаваным масіве, у якім 2, 3, 4, 5, 6 і ўсе сартуюцца. Усе разумеюць Ці логіку пра тое, як працуе выбар роду? 

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

Такім чынам, як вы, хлопцы, накшталт бачыў з мімаходам, мы збіраемся псевдокод гэта. Так што, калі вы, хлопцы, у задняй хочаце ўтвараюць групу, кожны ў табліцы могуць утвараць мала партнёра, я збіраюся каб даць вам, хлопцы, як тры хвіліны проста казаць праз логіка, на англійскай мове, аб тым, як мы маглі б рэалізаваць псевдокод напісаць выбару роду. І ёсць цукеркі. Калі ласка, прыходзьце і атрымаеце цукерку. Калі вы знаходзіцеся ў спіне і вы хочаце цукеркі, я магу кінуць цукеркі на вас. На самай справе, зрабіць you-- халаднавата. О, прабачце. ДОБРА. 

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

АЎДЫТОРЫЯ: Вы хочаце, каб стварыць некаторыя роду [неразборліва], што вы праходзіць праз увесь масіве. 

ANDI Пэн: Права. Такім чынам, вы будзеце жадаць, каб ітэрацыі праз кожны прасторы, правільна? Так, вялікі. Калі вы, хлопцы, жадаеце, каб даць мне Наступны line-- так, у спіну. 

АЎДЫТОРЫЯ: Праверце іх усё для самых маленькіх. 

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

АЎДЫТОРЫЯ: [неразборліва] ANDI Пэн: Так што вы збіраецеся хочуць пераключыць яго з першага гэтым масіве, дакладна? Гэта пачатак, я збіраюся сказаць. Добра. Так што цяпер вы памяняліся першым Адзін з іх, што вы хочаце зрабіць пасля гэтага? Так што цяпер мы ведаем, што гэта адно тут павінны быць найменшае значэнне, ці не так? Тады ў вас ёсць дадатковы адпачынак масіва, што гэта малокомплектных. Так што вы хочаце зрабіць тут, калі вы хлопцы, жадаеце, каб даць мне наступны радок? АЎДЫТОРЫЯ: Такім чынам вы хочаце перабраць праз астатнюю частку масіва. ANDI Пэн: Так. І так, што ж пераборы выгляд мае на ўвазе мы, напэўна, трэба? Які тып of-- 

АЎДЫТОРЫЯ: О, дадатковая зменная? ANDI Пэн: Магчыма іншы цыкл, ці не так? Такім чынам, мы, верагодна, захочуць для перабору through-- выдатна. І тады вы будзеце ісці назад і верагодна, праверыць мінімум раз дакладна? І вы збіраецеся паўтараць гэта, таму што завесы толькі збіраецца трымаць працуе, праўда? 

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

Залы: для завесы. 

ANDI Пэн: для цыкла? Дакладна. Так гэта, напэўна, будзе цыкл. Што такое праверка тут збіраецца значыць? Як правіла, калі вы хочаце, каб праверыць калі што-небудзь што-небудзь else-- 

АЎДЫТОРЫЯ: Калі. 

ANDI PENG: калі, праўда? А потым своп тут, мы будзем перайсці пазней, таму што Давіда прайшоў праз гэта ў лекцыі, а таксама. А потым другі ітэрацыі implies-- 

АЎДЫТОРЫЯ: Яшчэ цыкл. 

ANDI Пэн: --another цыкл, дакладна. Так што, калі мы шукаем на гэта правільна, мы можна ўбачыць, што мы, верагодна, спатрэбіцца укладзены цыкл з умоўным заявай у там а затым фактычнае кавалак кода, які гэта збіраецца памяняць значэння. Так што я проста наогул напісана псевдокод код тут. І тады мы на самай справе адбываецца фізічна, як клас, паспрабаваць ажыццявіць гэта сёння. Давайце вернемся ў гэты IDE. 

Ой-ой. Чаму гэта не-- там. ДОБРА. Выбачайце, дазвольце мне паспрабаваць павялічыць трохі больш. Там мы ідзем. Усё, што я раблю тут, я стварыў Праграма называецца "выбар / sort.c." Я стварыў масіў з дзевяці Значэння, 4, 8, 2, 1, 6, 9, 7, 5, 3. У цяперашні час, як вы можаце Разумееце, яны не ўпарадкаваны. н будзе лік, кажа вам суму значэнняў ў вас ёсць у вашым масіве. У гэтым выпадку, у нас ёсць дзевяць значэнняў. І я толькі што атрымаў цыкл тут што выводзіць малокомплектных масіў. 

І ў рэшце рэшт, я таксама атрымаў для цыкл, які друкуе яго зноў. Так, тэарэтычна, калі гэтая праграма працуе правільна, у рэшце рэшт, Вы павінны ўбачыць друкаваны цыкл у якім 1, 2, 3, 4, 5, 6, 7, 8, 9 усё правільна ў парадку. 

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

АЎДЫТОРЫЯ: [неразборліва] 

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

АЎДЫТОРЫЯ: Для INT я роўная 0-- 

ANDI Пэн: Так, добра. 

АЎДЫТОРЫЯ: я менш даўжыні масіва. 

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

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

АЎДЫТОРЫЯ: не было б н мінус 1? ANDI Пэн: Гэта адбываецца п мінус 1, дакладна. Ці мае гэта сэнс, чаму гэта п мінус 1, ўсё? Гэта таму, што масівы роўныя нулю, індэксаваная. Яны пачынаюцца з 0 і запусціць да н мінус 1. Так, гэта крыху больш складана. ДОБРА. І then-- АЎДЫТОРЫЯ: Isnt'1, што ўжо паклапаціліся, хоць, , Проста не кажу "менш або роўна "і проста кажу" менш "? 

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

Права. Можа быць, лепш, што назва будзе be-- "Тэмп" цалкам works-- можа быць, больш трапна назваў бы, калі мы хочам, каб маленькі value-- 

АЎДЫТОРЫЯ: Мін. ANDI Пэн: мін, там мы ідзем. мін будзе добра. І вось што нам рабіць хачу, каб ініцыялізаваць яго? Гэта крыху больш складана. Таму што цяпер на пачатак гэтага масіва, Вы яшчэ не глядзелі ні на што, ці не так? Так што, аўтаматычна, калі мы толькі на я роўная 0, тое, што мы хочам, каб ініцыялізаваць наш першы мінімальнае значэнне для? АЎДЫТОРЫЯ: я. ANDI Пэн: я, дакладна. Christabel, чаму мы хочам ініцыялізаваць яго я? 

АЎДЫТОРЫЯ: Таму што, ну, мы, пачынаючы з 0. Так, таму што мы не маем нічога, каб параўнаць гэта, мінімум будзе ў канчатковым выніку 0. 

ANDI Пэн: Точно. Такім чынам, яна зусім дакладна. Таму што ў нас на самай справе не паглядзеў на што-небудзь яшчэ, мы не ведаем, што наша мінімальнае значэнне. Мы хочам, каб проста ініцыялізаваць яго я, што, у цяперашні час, прама тут. І, як мы па-ранейшаму рухацца ўніз гэты масіў, мы ўбачым, што, адзін з Дадатковы праход, я павялічвае. І так у гэтай кропцы, я, верагодна, будзе хочуць быць мінімальным, таму што гэта будзе што заўгодна пачатак неотсортированной масіва. Прахладны. 

Так што цяпер мы хочам, каб дадаць для цыклу тут гэта збіраецца паўтараць праз малокомплектных або астатняя частка гэтага масіва. Хто-небудзь хоча, каб даць мне радок кода, якая будзе гэта рабіць? Hint-- што нам трэба тут? Што збіраецца ісці ў гэтым для цыкла? Так. АЎДЫТОРЫЯ: Такім чынам, мы хацелі б мець розны лік, таму што мы бяжым да канца масіва замест I, так што, магчыма J. 

ANDI Пэн: Так, J гучыць добра для мяне. Роўна? 

АЎДЫТОРЫЯ: Так бы я плюс 1, таму што Вы пачынаеце на наступным значэння. А потым да end-- так зноў, J з'яўляецца менш, чым п мінус 1, а затым J ++. ANDI Пэн: Выдатна. 

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

АЎДЫТОРЫЯ: калі заяву. 

ANDI PENG: калі заяву. Так if-- і тое, што будзе ўмова, што мы хочам у нашай, калі заяву? 

АЎДЫТОРЫЯ: Калі значэнне J менш, чым значэнне i-- 

ANDI Пэн: Точно. Так if-- так што гэта масіў называецца "масіў". Выдатна. Так што, калі array-- што гэта было? Скажыце, што яшчэ раз. 

АЎДЫТОРЫЯ: Калі масіў-J менш Масіў-я, то мы б змяніць мін. Такім чынам, мін будзе к. 

ANDI Пэн: Ці мае гэта сэнс? ДОБРА. А цяпер сюды, мы на самай справе хочам рэалізаваць абмен, праўда? Так Нагадаем, што ў лекцыі, што Давід, калі ён спрабаваў абмяняць the--, што было it-- апельсінавы сок і milk-- 

АЎДЫТОРЫЯ: Гэта было агідна. 

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

АЎДЫТОРЫЯ: часовая пераменная. 

ANDI Пэн: часовая пераменная. Так давайце зробім Int тэмп. Глядзі, гэта было б лепш Час, мэтай якіх эй, што гэта было? ДОБРА. Так што гэта было б лепш час назваць зменную "Тэмп". Так давайце зробім Int тэмп. Што мы збіраемся SET TEMP роўную тут? АЎДЫТОРЫЯ: Мін? ANDI Пэн: Гэта крыху больш складана. Гэта на самай справе не мае значэння, у рэшце рэшт. Гэта не мае значэння, што заказ вы вырашыце памяняць у так доўга, як вы робіце, што вы адсочваць тое, што вы падпампоўкі. 

АЎДЫТОРЫЯ: Гэта можа быць масіў я. 

ANDI Пэн: Так, давайце зробім масіў-I. І тады тое, што наступная радок кода мы хочам мець тут? АЎДЫТОРЫЯ: масіў я роўная масіва-J. ANDI Пэн: І, нарэшце? АЎДЫТОРЫЯ: масіў J роўная масіва я. АЎДЫТОРЫЯ: Ці масіва J роўна Масіў-temp-- або тэмпературы. 

ANDI Пэн: ОК. Так што давайце працаваць і паглядзім, калі ён будзе працаваць. Дзе, што адбываецца? О, што гэта праблема. Глядзі, на лініі 40, мы спрабуе выкарыстоўваць масіў-J? Але дзе J існуе толькі ў? 

АЎДЫТОРЫЯ: На працягу цыклу. ANDI Пэн: Права. Так што мы збіраемся трэба зрабіць? 

АЎДЫТОРЫЯ: Вызначыць яго межамі the-- АЎДЫТОРЫЯ: Так, я думаю, вы павінны выкарыстаць іншы, калі заяву, ці не так? Так як, калі minimum-- Усё ў парадку, дайце мне падумаць. 

ANDI Пэн: Хлопцы, паспрабуйце зірнуць Давайце см, што гэта тое, што мы можам зрабіць тут? 

АЎДЫТОРЫЯ: ОК. Такім чынам, калі мінімальная не роўная j-- так што калі мінімальная яшчэ i-- то мы б не памяняць. 

ANDI Пэн: Ці значыць гэта, роўна я? Што вы хочаце сказаць тут? 

АЎДЫТОРЫЯ: Ці так, калі мінімум не роўнае I, да. ANDI Пэн: ОК. Ну, што вырашае, накшталт, нашы праблемы. Але гэта яшчэ не вырашыць Праблема што адбудзецца, калі j-- так J не існуе па-за ім, тое, што Вы хочаце, каб мы з ім рабіць? Аб'явіць яго межамі? Давайце паспрабуем гэта працуе. Ой-ой. Наша роду не працуе. 

Як вы можаце бачыць, нашу пачатковую Масіў былі тыя значэння. І пасля гэтага ён павінен мець быў у 1, 2, 3, 4, 5, 6, 7, 8, 9. Гэта не працуе. Ах. Што мы робім? АЎДЫТОРЫЯ: Адладка. ANDI Пэн: Добра, мы можам паспрабаваць. Мы можам адладзіць. Агледзіце няшмат. Давайце ўсталюем наш пункт супыну. Давайце like-- OK. 

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

АЎДЫТОРЫЯ: Так кропкі супыну дзе пачынаецца адладка? ANDI Пэн: Ці прыпынкаў. АЎДЫТОРЫЯ: Ці прыпынкаў. ANDI Пэн: Так. Вы можаце ўсталяваць кропкі супыну і некалькі ён можа проста скакаць ад аднаго да іншага. Але ў гэтым выпадку мы не ведаем, дзе памылка адбываецца. Такім чынам, мы проста хочам пачаць зверху ўніз. Так. ДОБРА. 

Так гэтая лінія тут, мы можам умяшацца. Вы можаце ўбачыць тут, мы атрымалі масіў. Тыя значэння што ў масіве. Вы бачыце, што, як індэкс 0, адпавядае value-- аб, Я збіраюся паспрабаваць, каб павялічыць. На жаль, гэта сапраўды цяжка каб see-- па індэксе масіва 0, мы маем значэнне 4 і Затым гэтак далей, і гэтак далей. У нас ёсць лакальныя зменныя. Зараз я роўная 0, што мы хочам, каб гэта было. 

І так давайце трымаць пакрокавае. Наш мінімальны роўны 0, якія мы таксама хочам, каб гэта было. І тады мы ўваходзім наш другі для цыкл, калі масіў J менш, чым масіў-I, які яго не было. Гэтак жа вы бачыце, як што прапусціў што? 

АЎДЫТОРЫЯ: так павінна, калі Мінімальны ўсе that-- не вынікае, што быць унутры першым цыкл? ANDI Пэн: Не, таму што Вы ўсё яшчэ хочаце, каб праверыць. Вы хочаце, каб зрабіць параўнанне кожны Час, нават пасля запуску праз яго. Вы не проста хочаце, каб зрабіць гэта на першым праход. Вы хочаце, каб зрабіць гэта з кожны праход зноў. Такім чынам, вы хочаце, каб праверыць Ваш стан ўнутры. Такім чынам, мы толькі збіраемся трымаць працуе праз тут. Я дам вам падказку хлопцам. Гэта звязана з тым, што пры Вы правяраеце ваш ўмоўны, Вы не правяраючы для правільнага азначніка. Так што цяпер вы праверка Індэкс масіва J менш, чым масіў Індэкс I. Але тое, што ты робіш на пачатак для цыкла? Вы не усталяваўшы J, роўны I? 

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

Такім чынам ўнутры тут, мы створым мінімальнае значэнне і ўсталяваць, што ў I роўныя. Хіба мы гэта робім? Так, гэта зрабіў. У цяперашні час у нашай унутранай завесы для, мы збіраецца рабіць J роўная я ў п мінус 1. Хіба мы гэта робім? На самай справе, мы зрабілі гэта. 

Так, аднак, што мы тут параўнання? 

АЎДЫТОРЫЯ: J + 1. ANDI Пэн: Точно. І тады вы будзеце жадаць, каб усталяваць мінімальная роўная J плюс 1, а. Так што я прайшоў праз гэта вельмі хутка. Як вы, хлопцы разумеюць чаму гэта J + 1? ДОБРА. 

Такім чынам, у вашым масіве, у Ваш першы праход праз, Ваш цыкл, для Int я роўная 0, давайце проста выказаць здагадку, што гэта не была змененая яшчэ. У нас ёсць масіў, цалкам, усяго чатыры малокомплектных элементы, праўда? Таму мы хочам, каб ініцыялізаваць я раўняцца 0. І я маю намер проста праходзяць праз гэтую пятлю. І таму ў першым праходзе, мы збіраемся ініцыялізаваць зменную "мін" што таксама роўна I, таму што мы не мець мінімальнае значэнне. Дык вось у цяперашні час роўны 0, а таксама. І тады мы будзем ісці да канца. І мы хочам, каб ітэрацыі зноў. Цяпер, калі мы знайшлі, што наш мінімальны ёсць, мы хочам, каб перабору зноў, каб убачыць, калі гэта параўнанне, ці не так? Так J, вось, ідзе на роўнае I, які з'яўляецца 0. І потым, калі масіў J плюс я, што гэта той, які далей зноў, як менш чым тое, што ваш бягучы мінімум значэнне, вы хочаце памяняць месцамі. 

Так што давайце проста сказаць, што мы атрымаў, як, 2, 5, 1, 8. Прама цяпер, я роўная 0 і J роўны 0. І гэта наша мінімальнае значэнне. Калі масіў-J плюс i-- так што калі адзін гэта пасля таго, што мы, гледзячы на больш, чым адзін перад гэтым, гэта стане мінімум. 

Дык вось, мы бачым, што 5 ня менш, чым. Дык гэта будзе, каб не быць 5. Мы бачым, што 1 менш, чым 2, ці не так? Такім чынам, зараз мы ведаем, што наша мінімум будзе значэнне індэкса на 0, 1, 2. Да? А потым, калі вы атрымліваеце тут, Вы можаце памяняць правільныя значэння. 

Так што, калі вы, хлопцы, проста маючы J раней, вы не гледзячы на ​​тое пасля яе. Вы шукалі на тое ж самае значэнне, што Таму ён проста нічога не рабіў. Ці мае гэта сэнс для ўсіх, Таму нам трэба што плюс 1 там? ДОБРА. Зараз давайце проста запусціць праз яго, каб зрабіць што астатняя частка кода з'яўляецца правільным. Чаму, што здарылася? Ах, гэта мін прама тут. Мы параўноўвалі няправільнае значэнне. О, няма. 

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

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

Так што ў лепшым выпадку выканання адборачнага роду? Калі вы збіраецеся мець для перабору спісу а затым перабору астатнія гэтага спісу, колькі разоў Вы збіраецеся верагодна, у горшым case-- ў лепшым выпадку, sorry-- запусціць праз? Можа быць, лепш спытаць каб спытаць, што гэта горшы выпадак выканання адборачнага роду. АЎДЫТОРЫЯ: п у квадраце. ANDI Пэн: Гэта н квадрат, правільна. Так просты спосаб думаць пра гэта, як, у любы час у вас ёсць два ўкладзеных цыклаў для, гэта будзе н у квадраце. Таму што не толькі ты якая праходзіць праз раз, ў вас ёсць, каб вярнуцца і бегчы праз яго зноў ўнутры для кожнага значэння. Такім чынам, у гэтым выпадку, вы працуеце п раз н квадрат, які is-- прабачце, п разоў п, роўны п у квадраце. 

І накшталт таксама трохі унікальным у тым сэнсе што гэта не мае значэння, калі гэтыя Значэння ўжо ў парадку. Ён па-ранейшаму збіраецца запусціць праз любым выпадку. Давайце проста сказаць, што гэта быў 1, 2, 3, 4. Незалежна ад таго, ці з'яўляецца ён у парадак, гэта ўсё роўна б прабег і да гэтага часу правяраецца мінімальнае значэнне. Гэта зрабіла б такое ж колькасць праверак кожны раз, нават калі ён на самай справе не чапаць. 

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

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

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

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

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

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

ДОБРА. Хто-небудзь ёсць здагадка, што ў у горшым выпадку час выканання пузырьковый сартавання з'яўляецца? Так. 

АЎДЫТОРЫЯ: было б, як, п раз п мінус 1 ці нешта падобнае? Маўляў, кожны раз, калі ён працуе, гэта проста, як адзін своп менш што б гэта ні было. 

ANDI Пэн: Так, так Вы цалкам маеце рацыю. І гэта той выпадак, калі ваш Адказ на самой справе больш складаная чым мы павінны даць. Дык гэта будзе run-- Я збіраюся сцерці ўсё гэта тут. Ці ўсё добра? Ці магу я сцерці гэта? ДОБРА. Вы збіраецеся працаваць праз п раз у першы раз, ці не так? І яны збіраюцца запусціць праз п мінус 1 ў другі раз, праўда? І тады вы будзеце трымаць адбываецца, п мой 2, і гэтак далей. Дэвід зрабіў гэта ў лекцыі, дзе, калі вы дадалі ўсе гэтыя каштоўнасці, Вы атрымліваеце тое, што гэта like-- yeah-- больш за 2, што істотна зніжае проста да п квадраце. Вы збіраецеся атрымаць дзіўна доля там. І так проста ведаю, што п квадраце заўсёды мае прыярытэт над фракцыяй. І таму ў гэтым выпадку горшага выканання будзе н у квадраце. Калі б гэта было ў парадку змяншэння парадак, думаю, вам, павінны зрабіць своп кожны раз. 

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

АЎДЫТОРЫЯ: п. ANDI Пэн: Гэта н, дакладна. І чаму гэта п? АЎДЫТОРЫЯ: таму што вы проста павінны праверыць на кожным раз. ANDI Пэн: Точно. Такім чынам, у лепшым выканання, калі гэты спіс быў ужо sorted-- скажам 1, 2, 3, 4-- вы проста прайсці, вы б праверыць, вы ўбачыце, ох, усе яны апраўдаліся. У мяне не было, каб памяняць. Я скончыў. Такім чынам, у гэтым выпадку, гэта проста п або колькасць крокаў, якія вы проста павінен быў праверыць у першым спісе. 

І пасля гэтага, мы цяпер трапіў сартаванне ўстаўкамі, дзе алгарытм, па сутнасці, падзяліць гэта ў адсартаваным і малокомплектных часткі. А потым адзін за адным, неотсортированной значэння ўстаўляецца ў адпаведных пазіцыі ў пачатку спісу. 

Так, напрыклад, у нас ёсць Спіс 3, 5, 2, 6, 4 зноў. Мы ведаем, што гэта ў цяперашні час малокомплектных, таму што мы толькі што пачаў глядзець на яго. Мы глядзім і мы ведаем, што першае значэнне сартуецца, праўда? Калі вы толькі гледзячы на ​​масіў Памер аднаго, вы ведаеце, што гэта сартуецца. 

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

Мы зірнем на 2. Спачатку мы правяраем яго 5. Гэта менш, чым 5? Гэта не так. Такім чынам, мы павінны трымаць гледзячы ўніз. Тады вы праверыць 2 ад 3. Гэта менш, чым? Няма. Такім чынам, вы ведаеце, што 2 павінен быць устаўлены у пярэдняй і 3 і 5 абодва павінны быць выцесненыя. Зрабіце гэта зноў 6 і 4. І мы проста сочыце сутнасці, дзе мы проста праверыць, праверыць, праверыць. І пакуль гэта не ў праве пасаду, мы б проста устаўце яго ў правільным становішчы, які з'яўляецца, дзе імя прыйшоў. 

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

ОК ці хто-небудзь хоча даць мне горшы выканання? Так. 

АЎДЫТОРЫЯ: п у квадраце. 

ANDI Пэн: Гэта н квадраце. І чаму гэта п квадраце? 

АЎДЫТОРЫЯ: Таму што ў зваротны парадак, у вас ёсць прайсці праз п разоў п, is-- ANDI Пэн: Так, менавіта так. Гэтак жа, як і ў пузырьковый сартавання. Калі гэты спіс у парадку змяншэння, вы прыйдзецца праверыць першы раз. А потым з кожным дадатковая кошт, вы прыйдзецца праверыць яго супраць кожны значэнне, праўда? І так у цэлым, вы збіраецеся зрабіць А.М. раз н-пас іншы п прайсці, што ў п квадраце. Што можна сказаць аб лепшым выпадку? Так. 

АЎДЫТОРЫЯ: N мінус 1, паколькі Першы ўжо ў квадрат. 

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

Такім чынам, у лепшым выпадку, гэта на самай справе проста будзе н. Калі ў вас ёсць 1, 2, 3, 4, 5, 6, 7, 8, вы збіраецца запусціць праз што ўвесь спіс адразу каб праверыць, калі ўсё ў парадку. Гэта ўсё ясна, на які працуе раз адбору, а? Я ведаю, што іду праз гэта вельмі хутка. Але дакладна ведаю, што, калі вы ведаеце, агульныя паняцці, вы павінны быць добра. ДОБРА. Так што я проста дам вам, хлопцы, можа быць, як, хвіліну, каб пагаварыць з вашымі суседзямі на тое, што толькі некаторыя з асноўных адрозненняў паміж гэтымі тыпамі гатункаў. Мы пойдзем над тым у бліжэйшы час. АЎДЫТОРЫЯ: О, добра. ANDI Пэн: Так. ДОБРА. Прахладны, давайце зноў склікаць як клас. ДОБРА. Так што гэта было свайго роду адкрытае пытанне ў тым сэнсе, што ёсць шмат адказаў на іх. І мы будзем ісці над некаторымі з іх коратка. Я проста хацеў, каб вы, хлопцы думаючы пра тое, што дыферэнцыраваны усе тры тыпу гатункаў. І пачуў я, таксама, вялікі question-- што ж сартавання зліццём зрабіць? Вялікае пытанне, таму што гэта тое, што мы ў наступным пакрыцця. 

Так аб'яднаць роду з'яўляецца адзін выгляд, што функцыі вельмі па-рознаму ад іншых відаў. Як вы, хлопцы, можаце see-- зрабіў Давід, што дэма дзе ён усё крута шумы, бачачы, як аб'яднаць Сартаваць пабег, як бясконца хутчэй, чым двух іншых тыпаў? ДОБРА. Так гэта таму, што зліццё Сартаваць рэалізуе гэты разрыў і заваяваць канцэпцыю, што мы казалі пра многае ў лекцыі. У тым сэнсе, што мы хацелі б працаваць разумнейшы, а не цяжэй, калі вы падзеліце і заваяваць праблемы, і зламаць іх ўніз, а затым пакласці іх разам, добрыя рэчы заўсёды адбываюцца. 

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

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

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

І тады мы будзем глядзець на яго візуальна, таму што я візуальны вучань. Гэта працуе лепш для мяне. Такім чынам, мы будзем глядзець на наглядным прыкладзе тут. 

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

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

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

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

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

АЎДЫТОРЫЯ: Дык вы сказалі, што вы бераце 1, а затым 4 і 6 і паклаў іх у. Так не those-- ня Вы шукаеце на іх як асобныя элементы, а не як у цэлым? ANDI Пэн: Так. Так, што адбываецца з'яўляецца тое, што вы ў асноўным ствараюць зусім новы масіў. Такім чынам, вы ведаеце, што, вось, у мяне ёсць два масіва памерам 3, праўда? Такім чынам, вы ведаеце, што мой адсартаваны масіў павінен мець шэсць элементаў. Такім чынам, вы проста стварыць Новы аб'ём памяці. Дык вы накшталт як быўшы марнатраўным памяці, але гэта не мае значэння таму што гэта так мала. Такім чынам, вы глядзіце на 1 і вы паглядзіце на 2. І вы ведаеце, што 1 менш, чым 2. Такім чынам, вы ведаеце, што 1 павінны ісці ў пачатак усіх тых. 

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

АЎДЫТОРЫЯ: Дык ты проста заўсёды Параўноўваючы [неразборліва]? 

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

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

ДОБРА. Так і Давід падышоў гэта ў лекцыі. Што ў лепшым выпадку Час аўтаномнай працы, у горшым выпадку час аўтаномнай працы, і чаканыя аўтаномнай працы ад сартавання зліццём? Праз пару секунд, каб падумаць. Гэта даволі цяжка, але выгляд інтуітыўным, калі вы думаеце пра гэта. Добра. 

Залы: у горшым выпадку п п часопіса? ANDI Пэн: Точно. І чаму гэта п п ўвайсці ў сістэму. 

АЎДЫТОРЫЯ: Хіба гэта не таму, што ён становіцца экспанентна хутчэй, так што гэта, як функцыі, якія а проста быць п квадрат або што-то? ANDI Пэн: Точно. Такім чынам, прычына, па якой выканання на гэта н часопіса п because--, што ты рабіць ва ўсіх гэтых крокаў? Вы проста секчы яго напалову, праўда? І таму, калі мы робім увайсці, усё, што ён робіць дзеліць праблему напалову, у два разы, у два разы, у больш за палову. І ў гэтым сэнсе, вы можаце выгляд з ліквідаваць лінейную мадэль што мы выкарыстоўвалі. Таму што, калі вы нарэзаць рэчы ў палове, гэта часопіс. Вось толькі матэматычны спосаб прадстаўлення яго. 

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

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

У вас ёсць некаторыя часопіс N. У вас ёсць некаторыя часопіс часопіса N. Мы не дакранаемся іх у гэтым класе цяпер. Але калі вы, хлопцы, цікава, не саромейцеся Google, што найбольш эфектыўныя механізмы сартавання. Я не ведаю, ці ёсць некаторыя сапраўды смешныя, like-- ёсць некаторыя сапраўды смешныя, якія людзі робяць. І вы дзівіцеся, як яны калі-небудзь думалі пра гэта. Так Google, калі ў вас ёсць запасны Час, на тое, што некаторыя пацешныя спосабы што people-- а таксама эфектыўныя ways-- людзі змаглі рэалізаваць разнастайныя. ДОБРА. І вось толькі маленькі зручны графік. Я ведаю ўсё пра цябе, да гэтага віктарыне 0, будзе ў вашай пакоі, верагодна, спрабуе запомніць гэта. Так што прыемна там для вас, хлопцы. Толькі не забывайце, логіку, made-- Таму гэтыя лічбы былі адбываецца. Калі вы заўсёды губляецца, проста пераканайцеся, упэўнены, што вы ведаеце, што гатунку. І вы можаце запусціць праз іх у сваім розуме каб высветліць, чаму тыя, адказы адказы на гэтыя пытанні. 

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

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

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

Такім чынам, шлях, які мы б ісці аб рэалізацыі двайковага пошуку ёсць, калі ў нас было мноства, Індэкс 0 да 6, сем элементаў, мы можам глядзець у сярэдзіне, right-- прабачце, калі наша пытанне first-- калі мы хочам, каб задаць пытанне аб, ня масіў ўтрымлівае элемент 7, Відавочна, быўшы людзей, і які мае такі маленькі масіў, гэта проста для нас каб сказаць так. Але шлях да рэалізацыі двайковы Пошук будзе выглядаць у сярэдзіне. 

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

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

Так што цяпер мы глядзім на Сярэдзіна тое, што засталося. Гэты паказчык 5. Мы робім тое ж самае яшчэ раз праверку і мы бачым, што гэта менш. Такім чынам, мы глядзім у левай частцы, што. І тады мы бачым, што чэк. Ці з'яўляецца значэнне масіва ў Індэкс 4 роўная 7? Гэта. Такім чынам, мы можам вярнуцца так, таму што мы знайшлі значэнне ў нашым спісе. Ці шлях я прайшоў што сэнс усім? ДОБРА. Я дам вам, хлопцы, можа быць, як, тры, чатыры хвіліны, каб высветліць, як псевдокод гэта. 

Такім чынам, уявіце, я папрасіў вас напісаць Функцыя называецца пошук (), што вярнуўся значэнне, лагічнае значэнне, што гэта праўда ці false-- як, дакладна, калі вы знайшлі значэнне, хлусня, калі вы не зрабілі. І тады вы былі прайшоў у кошту вы шукалі ў каштоўнасці, якія гэта array-- аб, я вызначана паставіць што ў няправільным месцы. ДОБРА. У любым выпадку, што павінна быць быў справа значэнняў. А потым Int N гэты лік элементаў у гэтым масіве. Як бы вы ісці аб спробе у псевдокоде гэтую праблему ў? Я дам вам, хлопцы, як тры хвіліны, каб зрабіць гэта. Не, я думаю, што ёсць only-- так, ёсць адна прама тут. АЎДЫТОРЫЯ: Ці магу я? ANDI Пэн: Так, у мяне ёсць ты. Гэта працуе? ОК, крута. 

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

АЎДЫТОРЫЯ: [неразборліва] АЎДЫТОРЫЯ: Вы хацелі для перабору through-- АЎДЫТОРЫЯ: Проста яшчэ адзін цыкл? АЎДЫТОРЫЯ: --для. 

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

АЎДЫТОРЫЯ: Да [неразборліва] значэнне роўна гэтага значэння. ANDI Пэн: Точно. Такім чынам, вы можаце на самой справе проста write-- мы можам нават спрасціць яго больш. Мы можам проста зрабіць той час як цыкл, праўда? Такім чынам, вы можаце проста loop-- мы ведаем, што гэта нейкі час. Але цяпер, я збіраюся сказаць "пятлю" - праз што? Цыкл until-- што наш заканчваючы стан? Я думаю, што я чуў. Я чуў, хто-небудзь сказаць. 

Аўдыторыя: Значэнні роўная сярэдзіну. ANDI Пэн: Скажы гэта яшчэ раз. АЎДЫТОРЫЯ: Ці, да Значэнне вы шукаеце Для роўная сярэдняга значэння. 

ANDI Пэн: Што рабіць, калі гэта не там? Што рабіць, калі значэнне вы шукаеце для на самай справе не ў гэтым масіве? АЎДЫТОРЫЯ: Вы вяртаецеся 1. 

ANDI Пэн: Але тое, што мы хочам, каб цыкл да калі ў нас ёсць стан? Так. 

АЎДЫТОРЫЯ: пакуль ёсць толькі адно значэнне? ANDI Пэн: Вы можаце цыкл until-- так што вы ведаеце, што вы будзе мець максімальную значэнне, ці не так? І вы ведаеце, што вы збіраецеся мець значэнне мін, праўда? Таму што таксама, гэта тое, што Я забыўся сказаць, перш чым, што нешта, што гэта крытычна бінарнага пошуку з'яўляецца тое, што ваш масіў ўжо адсартаваныя. Таму што няма ніякага спосабу рабіць гэта, калі яны проста выпадковыя значэння. Вы не ведаеце, калі адзін гэта больш, чым іншыя, праўда? 

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

Хіба што сэнс? Я ўзяў некалькі спробаў, каб атрымаць гэта права. Але цыкл, пакуль ваш максімальнага значэння па сутнасці амаль няма чым або роўна вашай мінімум, праўда? Вось калі вы ведаеце, што вы сышліся. АЎДЫТОРЫЯ: Калі ваша максімальная значэнне менш, чым мінімум? ANDI Пэн: Калі вы трымаеце рэгулюючы яго, што гэта тое, што мы збіраемся каб рабіць у гэтым. Ці мае гэта сэнс? Мінімальная і максімальная проста цэлыя лікі, мы, верагодна, збіраецца хочаце стварыць, каб трымаць трэк, дзе мы шукаем. Паколькі масіў існуе незалежна ад таго, што мы робім. Маўляў, мы на самай справе не фізічна отрубание масіва, праўда? Мы проста рэгулюючы дзе мы шукаем. Ці мае гэта сэнс? 

АЎДЫТОРЫЯ: Так. 

ANDI Пэн: ОК. Так што, калі гэта ўмова нашай завесы, тое, што мы хочам ўнутры гэтай завесы? Што мы збіраемся быць жаданне зрабіць? Так што цяпер, у нас ёсць макс і мін, права, верагодна, створана дзе-то тут. Мы збіраемся, верагодна, хочаце знайсці сярэдзіну, праўда? Як мы збіраемся, каб быць магчымасць знайсці сярэдзіну? Што mathematical-- АЎДЫТОРЫЯ: Макс плюс мін падзеленыя на 2. ANDI Пэн: Точно. Ці мае гэта сэнс? І вы, хлопцы, зразумець, чаму мы не проста use--, чаму мы зрабілі гэта а не рабіць проста п дзеліцца на 2? Гэта таму, што п з'яўляецца значэнне што збіраецца застацца тое ж самае. Дакладна? Але, як мы скарэкціруем нашу мінімум і Максімальныя значэння, яны збіраюцца змяніць. І ў выніку, наш сярэдні збіраецца мяняць занадта. Дык вось чаму мы хочам зрабіць гэта прама тут. ДОБРА. 

А потым, у цяперашні час, што мы знайшлі our-- так. 

АЎДЫТОРЫЯ: Проста хутка question-- калі вы кажаце, мін і макс, мы мяркуючы, што гэта ўжо адсартаваныя? 

ANDI Пэн: Так, гэта на самай справе перадумовай для бінарнага пошуку, што вы павінны ведаць, што гэта сартуецца. Менавіта таму-то, вы пішаце ў вашым Праблема ўсталяваць да вашага бінарнага пошуку. ДОБРА. Так што цяпер мы ведаем, дзе наша сярэдзіна з'яўляецца тое, што вы хочаце зрабіць тут? 

АЎДЫТОРЫЯ: Мы хочам, каб параўнаць што да іншага. ANDI Пэн: Точно. Такім чынам, вы будзеце параўноўваць з сярэдзіны да значэння, ці не так? І што гэта кажа нам, калі мы параўноўваем? Што мы хочам рабіць далей? 

АЎДЫТОРЫЯ: Калі гэтае значэньне большае чым сярэдзіне, мы хочам, каб адрэзаць яго. ANDI Пэн: Точно. Такім чынам, калі значэнне больш чым сярэдзіне, мы захоча змяніць гэтыя Мінімальны і вычарпаны, праўда? Што мы хочам змяніць? Так што, калі мы ведаем, што дзесьці значэнне тут, што вы ў нас змяніць? Мы хочам змяніць нашу Мінімальны быць у сярэдзіне, ці не так? А потым яшчэ, калі ён знаходзіцца ў гэтым палова, што мы хочам змяніць? 

АЎДЫТОРЫЯ: Ваша максімальная. ANDI Пэн: Так. А потым вы проста трымаць цыкл, праўда? Таму што цяпер, пасля адной ітэрацыі праз, у вас ёсць макс тут. І тады вы можаце пералічыць сярэдзіне. І тады вы можаце параўнаць. І вы збіраецеся працягваць не да хвілін і Maxes істотна сышліся. І вось, калі вы ведаеце, што Вы патрапілі ў канец. І альбо вы знайшлі яго ці вы не ў гэтай кропцы. 

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

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

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

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

І тады вы будзеце па сутнасці проста пакласці іх усё разам. Спецыфікацыя скажа вам, як пакласці, што ў камандным радку. І вы зможаце праверыць, ці з'яўляецца не ваша сартавання і пошуку працуюць. Прахладны. Хто-небудзь ужо пачалася, і сустракаемыя праблемы або пытанні яны маюць цяпер з гэтым? ДОБРА. 

АЎДЫТОРЫЯ: Пачакайце. У мяне ёсць пытанне. 

ANDI Пэн: Так. 

АЎДЫТОРЫЯ: Так што я пачаў рабіць лінейны пошук у helpers.c і гэта не было сапраўды працуе. Але потым я даведаўся, мы проста павінны выдаліць яго і зрабіць бінарны пошук. Так ці не ўсё роўна, калі ён не працуе? 

ANDI Пэн: Кароткі адказ: не. Але так як мы не-- АЎДЫТОРЫЯ: Але ніхто не на самай справе праверкі. ANDI Пэн: Мы ніколі не ўбачыце, што. Але вы, верагодна, хочаце, каб што ваш пошук працы. Таму што, калі ваш лінейны пошук не працуе, то хутчэй за ўсё, ваш бінарны Пошук не будзе працаваць, як добра. Таму што ў вас ёсць падобнае Логіка ў іх абодвух. І няма, гэта не мае значэння. Такім чынам, адзінымі вы ўключыце у з'яўляюцца свайго роду і бінарны пошук. Так. 

А таксама, шмат дзяцей былі спрабуючы сабраць helpers.c. Вы на самой справе не дапускаюцца каб зрабіць гэта, таму што helpers.c не мае асноўную функцыю. І таму вы павінны толькі быць на самай справе кампіляцыі генераваць і знайсці, таму што знайсці званкі helpers.c і функцыі ў ёй. Так што робіць адладку боль у задніцы. Але гэта тое, што мы павінны рабіць. АЎДЫТОРЫЯ: Вы проста зрабіць усё, праўда? ANDI Пэн: вы можаце проста зрабіць усё як добра, так. ДОБРА. Дык вось яно што ў плане таго, што PSET просіць, каб вы ўсё робіце. Калі ў вас ёсць якія-небудзь пытанні, калі ласка, вольным спытаць мне пасля падзелу. Я буду тут, як, 20 хвілін. 

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

АЎДЫТОРЫЯ: з дадатковымі Функцыі, мы глядзім тыя да? 

ANDI Пэн: Так, тыя ў кодзе. У гульні 15, палова з гэта ўжо напісана для вас. Так што тыя функцыі ўжо ў кодзе. Так. Добра. Ну, ўдачы. Гэта агідна дзень. Так спадзяюся, вы, хлопцы, не адчуваць сябе занадта дрэнна аб знаходжанні ўнутры і кадавання.