[Музички] 

АНДИ Пенг: Добредојдовте на недела 3 од делот. Благодарение, момци, за сите кои доаѓаат до овој ран почеток време денес. Имаме убаво, малку денес интимни група. Па се надевам дека ќе дојдеме до финиш, можеби, на почетокот, малку рано денес. Толку брзо, само некои најави за денеска на дневен ред. Пред да започнеме, ние сме случува само одиме во текот некои кратки логистички прашања, pset прашања, debrief, такви работи. А потоа ќе се нурне во право. Ќе искористиме дебагер наречен GDB да почне откривајќи нашиот код, што Давид објаснето во предавање пред некој ден. Ние ќе одиме во текот на четири видови на сорти. Ќе одиме над нив прилично брзо бидејќи тие се доста интензивни. Но знам дека на сите слајдови и изворниот код се секогаш на интернет. Па можете слободно, во вашиот читање, да се врати се назад и да ги разгледаме во тоа. 

Ќе одиме преку асимптотска нотација, што е само стилизиран начин на велејќи: "runtimes" каде што имаме голема О, што Дејвид е објаснето во предавањето. А имаме и Омега, која е долната граница на извршувањето. И ние ќе зборуваме малку повеќе во-длабочината на поглед на тоа како тие работат. И на крај, ние ќе одиме во текот бинарни пребарување, затоа што многу од вас, кои веќе имаат Погледна во вашиот psets веројатно знаете дека дека е прашање кое е во вашиот pset. Така што сите ќе бидат среќни кои ги покриваат ова денес. 

И на крај, на вашето повратни информации секција, јас всушност остави околу 15 минути на температура од На крајот да се оди само преку логистика на pset3, било какви прашања, можеби малку на насоки, ако сакате, пред да почнеме програмирање. Значи, да се обидат да се добие преку материјалот прилично брзо. И потоа можеме да поминат некое време преземање на повеќе прашања за pset. ВО РЕД. 

Брзо, па само неколку најави пред да почнеме денес. Прво, добредојде да прават тоа преку две од вашиот psets. Зедов погледнете your-- да, ајде добие аплауз за оној. Всушност, јас бев навистина, навистина импресиониран. Се оценува првиот pset за вас момци минатата недела, а вие момци направија неверојатна. 

Стил беше на точка Покрај неколку коментари. Бидете сигурни дека сте секогаш коментирајќи вашиот код. Но вашиот psets беа на точка. И чувајте го до. И тоа е добро за човек кој степенува да види дека вие момци се кријат во колку напор во вашиот стил и вашиот дизајн во вашиот код кои би сакале за да ја видите. Па јас сум минувајќи низ мојата благодарност за остатокот од Тас. 

Сепак постојат debrief неколку прашања Јас само сакам да одам во текот на тој ќе го направи и мојот живот и голем број на други TAS "живее малку полесно. Прво, јас го забележав ова минатото week-- колку од вас се работи за check50 Вашиот код пред да ја поднесете? ВО РЕД. Па секој треба да се прави check50, because-- на secret-- ние всушност check50 работи како дел од нашата коректност сценарија за тестирање вашиот код. Значи, ако вашиот код е неуспешна check50, во сите веројатноста, тоа е веројатно нема да се успеат нашата проверка, како и. Понекогаш вие момци имаат право одговори. Како, во алчни, некои од имате право на броеви, можете само да се печати од некои дополнителни работи. И дека дополнителни работи всушност не чек, бидејќи компјутерот не знаеме што тоа е во потрага за. И така тоа само ќе го изврши преку, видите дека вашиот излез не одговараат на она што го очекуваме одговорот да биде и означете тоа е во ред. 

И знам што се случи во некои од вашите случаи оваа недела. Па се вратив и рачно regraded код на сите. Во иднина, иако, Ве молиме, проверете дали дека сте водење проверете 50 на вашиот код. Затоа што тоа е еден вид на болка за ТС да треба да се вратиш назад и рачно regrade секој pset за секој еден, малку го промаши пример. Па јас не полета поени. Мислам дека јас соблече можеби еден или два за дизајн. Во иднина, иако, ако сте ја изгуби check50, ќе бидат преземени поени исклучување за коректност. 

Понатаму, psets се поради петок на пладне. Мислам дека има седум минути крајот на грејс период, кој ќе ви даде. По Харвард време, им е дозволено да биде седум минути доцна за се. Па еве на Јеил, ние ќе се придржуваат до тоа како добро. Но доста, Во 12:07, ако вашиот pset не е во, тоа се случува да биде означен како доцна. И така додека не се означи како доцна, TA-- сум сè уште нема да биде оценување на вашите psets. Така да сеуште ќе видите градус се појави. Сепак, знаеме дека во на крајот на семестарот, сите доцна psets само ќе биде автоматски zeroed страна на компјутер. 

Ова го правиме од две причини. Една, понекогаш добиваме оправдани, како изговори деканот, подоцна дека јас не знаете за уште. Па ние како да бидете сигурни дека ние сме оценување сè што само во случај, како, јас сум недостасува изговор на деканот. И второ, да ги задржи во умот, може да се уште намали еден pset дека има целосен опфат поени. И така ние сакале да градус на сите ваши psets само да бидете сигурни дека вашиот обем на таму и ти си ги обидува. Па дури и ако тоа е доцна, ќе уште се добие кредит за обемот поени, мислам. 

Па Поуката од оваа приказна е, да направат сигурни дека вашата psets се на време. И ако тие не се во на време, знаете дека тоа не е голема. Да, пред да продолжат понатаму, дали некој има било какви прашања во врска со повратни pset? Је. 

ПУБЛИКАТА: Дали ќе го велат можат да се откажат од еден од psets? 

АНДИ Пенг: Да. Значи има девет psets целокупната во текот на семестарот. И ако имате опсегот points-- така обемот е само, прилично многу, ви се обидуваат на проблем, да не сте ставање во времето, се ви покажува дека сте демонстрираа ќе ги прочитате на спец. Тоа е доста делокруг. И ако сте во исполнување обемот точки, ние може да се намали на најниско еден од целиот опсег. Па тоа е во вашата предност заврши и да се обиде секој pset. 

Upload-- дури и ако ниту еден од работат, ги испратите. А потоа ќе бидат во можност да се надевам да ви даде некои од тие точки назад. Кул. Било какви други прашања? Одлично. 

Второ, канцеларија hours-- неколку брзи белешки во врска со работното време. Значи прво, дојде на почетокот на неделава. Никој никогаш не беше во работното време во понеделник. Christabel дојде до на работното време од минатата ноќ. Да, Christabel. И што имаме во канцеларијата часа минатата ноќ, Christabel? 

ПУБЛИКАТА: Имавме сладолед. 

АНДИ Пенг: Па тоа е во право, ние имавме сладолед во работното време од минатата ноќ. Иако не можам да ви ветувам дека ќе имаме сладолед во работното време секоја недела, она што можам да ветувам е дека ќе има значително подобро студент сооднос ТА да. Како legit, тоа е како 00:57. При што, За разлика од ова Четврток, имаш околу 150 навистина истакна деца и без сладолед. И тоа едноставно не е продуктивна за никого. Па Поуката од оваа приказна е, дојде на почетокот за работното време и добри работи ќе се случи. 

Исто така, да бидат подготвени да се поставуваат прашања. Знаеш? Без оглед на она TAS, јас мислам, се вели, ние сме биле добивање на неколку ученици кои доаѓаат во четврток во, како, 10:50 не ја прочитате спец да се биде како да ми помогне, да ми помогне. За жал, во тој момент, има не многу можеме да направиме за да ви помогнат. Затоа ве молиме да дојде на почетокот на неделава. Дојде на почетокот да се работното време. Се подготвени да поставуваат прашања. Бидете сигурни дека вие, како студент, се таму каде што што треба да биде, така што TAS може да ве водиме заедно, што е она што на работното време треба да бидат распределени за. 

Второ, па знам професори сакал да не изненади со тестови. Имав еден професор оние како и, Ио, патем, се сеќавам дека среднорочни имате следниот понеделник. Да, јас не знаев за што среднорочни. Па јас ќе одам да се биде дека ТС што потсетува сите дека квиз 0-- бидејќи, знаете, ние сме CS. Сега, кога ние го направивме низи, ќе добиете зошто тоа е квиз 0, не квиз 1, а? ВО РЕД. О, јас добив неколку chuckles на оној. ВО РЕД. 

Па квиз 0 ќе биде 14 октомври, ако ти си во делот од понеделник до среда и 15 октомври, ако сте во делот вторникот-четврток. Ова не се однесува за оние од вас на Харвард who-- Мислам дека сите ќе бидат преземање на вашата квизови на 14. 

Така да, следната недела, ако Давид, во предавањето, оди, Да, па во врска со тоа квиз следната недела, ќе се сите нема да бидат шокирани затоа што ќе дојде на секција а знаете дека вашата квиз 0 е за две недели. И ќе имаме преглед седници и сè. Па не се грижи за исплашени за тоа. Било какви прашања before-- какви прашања на сите во врска со логистички прашања, оценување, работното време, делови? Је. 

ПУБЛИКАТА: Толку квизот е ќе биде за време на предавање? 

АНДИ Пенг: Да. Па на квизот, мислам, е 60 распределени во тој временски слот минути дека само ќе потрае во аула. Значи, вие не мора да дојде во на, како, на случаен 07:00. Сето тоа е добро. Је. Кул. 

Во ред. Па ние ќе треба да се воведе концептот на вас оваа недела дека Дејвид веќе вид на осврна и на предавање во минатата недела. Таа се вика gdb. И колку од вас, додека во текот на пишувањето на вашиот psets, да се забележи голема копчето што вели "Debug" на врвот на вашиот ИРО? ВО РЕД. Па сега ние всушност ќе добиете за да ја открие тајната на она копче што всушност го прави тоа. И јас ви гарантирам, тоа е убава, убава работа. 

Па до сега, мислам дека има се две работи студентите се обично правите кога дебагирање psets. Еден, тие или го додадете во printf () - па на секои неколку линии, тие го додадете во printf () - О, каква е оваа променлива? О, каква е оваа променлива now-- и можете вид на видите прогресијата на вашиот код како што тече. Или вториот метод деца направите е дека тие само напиши целата работа и потоа оди вака на крајот. Се надевам дека таа работи. Јас ви гарантирам, GDB е подобар од двете од овие методи. Је. Па ова ќе биде вашиот нов најдобар пријател. Затоа што тоа е една убава работа кој визуелно прикажува и она што го прави вашиот код на одредена точка како и она што на сите ваши варијабли се носи, како што се нивните вредности, во тој одреден момент. И на овој начин, навистина може да постави точки на прекин во вашиот код. Можете да ја извршите преку ред по ред. И GDB само ќе треба за вие, кои се прикажани за вас, она што на сите ваши променливи се, што прават тие, она што се случува во кодот. И на таков начин, тоа е па многу полесно да се види она што се случува, наместо на printf-ИНГ или пишување одредување на своите изјави. 

Па ние ќе се направи еден пример за тоа подоцна. Значи ова се чини дека малку апстрактен. Не се грижи, ние ќе направиме примери. И така во суштина, трите најголеми, најчесто користените функции ќе треба во GDB се Следно, се повлече во текот, во кругот на копчиња. Одам да минете во текот таму, всушност, во моментов. 

Така може да се види дека сите момци или јас треба да зумирате малку? Во задниот дел, можете да го видите ова? Треба ли да зумирате? Само малку? Добро, кул. Таму ќе одиме. ВО РЕД. 

Па имам, еве, ми имплементација за алчен. И додека многу од вас момци напишал алчен во додека јамка form-- дека е совршено прифатлив начин да се направи it-- друг начин да го направите тоа е да се едноставно поделат во modulo. Затоа што тогаш можете да имате вредност, а потоа да има вашиот остатокот. А потоа може да се само додадете сето тоа заедно. Дали логиката на она што го правам тука се направи смисла на сите, пред да почнеме? Вид на? Кул. Одлично. Тоа е прилично секси парче на код, јас би рекол. Како што реков, Давид, во предавање, по некое време, сите вие ​​ќе започнете да гледате код како нешто што е убаво. И понекогаш, кога ќе видите убава код, тоа е толку прекрасно чувство. 

Па сепак, додека овој код е многу убава, тоа не функционира како што треба. Значи, да се кандидира check50 за ова. Проверете 50 20-- OOP. 2? Е дека pset2? Је. Ох, pset1. ВО РЕД. Значи ние се кандидира check50. 

И како што вие момци можат да ја видите тука, тоа е неуспехот на неколку случаи. И за некои од вас, во курсот на водење на вашиот проблем сетови, сте како, ах, зошто не е тоа работа. Зошто е тоа да работи за некои вредности, но не и за другите? Па, GDB се случува да ви помогне да дознаам зошто тие влезни не се работи. 

ВО РЕД. Да видиме, еден од проверки ме изневерува check50 беше влезна вредност од 0,41. Па точниот одговор дека треба да се добива е 4. Но наместо тоа, она што јас сум ги отпечатите е 3-n, што не е точно. Па да се кандидира тоа рачно, само бидете сигурни дека check50 е работа. Ајде да го направиме ./greedy. Упс, морам да се направи алчен. Таму ќе одиме. Сега ./greedy. 

Колку се должи тоа? Ајде да го направиме 0.41. И да, гледаме овде дека тоа е Ставање 3 кога точниот одговор, всушност, треба да биде 4. Значи, да се влезе GDB и да видиме како ќе се може да се обратите за одредување на овој проблем. 

Така, првиот чекор во секогаш дебагирање вашиот код е да се стави точка на прекин, или точка во која ќе се сакате компјутерот или дебагерот за да почнете да барате. Значи, ако сте навистина не знаеш што е твојот проблем, обично, типичниот нешто што сакаме да направите е да се постави нашата точка на прекин на главните. Значи, ако вие момци можат да се види ова црвено копче право, таму, Да, тоа беше мене поставување точка на прекин за главната функција. Јас кликнете на тоа. 

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

Значи имаш центи, монети, n, сите прогласени за различни работи во оваа точка. Не се грижи, бидејќи не сме, всушност, ги иницијализиран на сите променливи уште. Значи во вашиот компјутер, компјутер е само да се види, ох, 32767 била последната користи функцијата на тој простор меморија во мојот компјутер. И така тоа е каде центи во моментов е. Но не и дека откако ќе се кандидира на кодот, тоа треба да стане иницијализира. 

Значи, да се оди преку, линија по линија, што се случува овде. ВО РЕД. Значи тука се трите копчиња кои јас само објасни. Имаш на претставата, или функција во бегство, копчето, имате чекор преку копче, и вие исто така имаат Чекор во копчето. И во суштина, сите тројца нив само одат преку вашиот код и да направите различни нешта. 

Па обично, кога сте дебагирање, ние не сакаме да само кликнете на игра, бидејќи играат само ќе го изврши вашиот код да на крајот од неа. И тогаш не ќе се, всушност, знаете што вашиот проблем е освен ако не поставите повеќе точки на прекин. Ако ја поставите на повеќе точки на прекин, тоа само ќе се автоматски стартувате од една точка на прекин, на следната, на следната. Но, во овој случај имаме само дека еден, бидејќи ние сакаат да работат на патот од врвот надолу кон дното. Па ние ќе треба да го игнорираме тоа копче сега за целите на оваа програма. 

Па чекор преку функцијата само чекори во текот на секоја линија и ви кажува што компјутерот го прави. Чекор во функција оди во вистинската функција што е на вашата линија код. Така на пример, како printf (), тоа е во функција, нели? Ако сакав да се физички чекор во () функцијата на printf, Јас би, всушност, оди во парче код каде printf () беше напишано и да видиме она што се случува таму. 

Но обично, да претпоставиме дека кодот кој ние ќе ви даде работи. Ние се претпостави на printf () работи. Претпоставуваме дека GetInt () е работа. Па нема потреба да се чекор во тие функции. Но, ако има функции дека ти пишувам себе што сакате да се провери од она што се случува, вие би сакале да влезете во таа функција. 

Па сега ние сме само ќе да се повлече во текот на овој дел од кодот. Ќе видиме. Ох, печати, "О хаи, како многу промени се должи тоа? " Што не се грижат. Ние знаеме дека е работа, па чекор врз неа. 

Така n, што е наша плови дека ние сме initialized-- или declared-- на врвот, ние сме сега изедначување дека за да GetFloat (). Значи, да се повлече во текот тоа. И можеме да видиме на дното тука, на програмата ме прашува да внесете вредност. Па ајде да го внесете вредност сакаме за да го тестирате тука, што е 0,41. Одлично. 

Па сега n-- вие момци се види тука, на bottom-- тоа е stored-- бидејќи ние се уште не се заоблени, тоа е чуваат во овој како џиновски плови тоа е 0,4099999996, што е доволно блиску до нашата цели, токму сега, да 0.41. А потоа ќе видиме подоцна, како што продолжи повлекува во текот на програмата, По тука, n стана заоблени и центи стана 41. Одлично. Па знаеме дека нашата работна заокружување е. Знаеме дека имаме точниот број на центи, па знаеме дека тоа е навистина не е проблем. 

Значи ние продолжуваме повлекува за во оваа програма. Одиме тука. И така, по оваа линија код, ние треба да се знае колку кругови што ги имаме. Ние се оддалечува. И ќе видите што правиме, всушност, имаат еден квартал, бидејќи ние сме одзема 25 од нашата почетна вредност од 41. И ние имаме 16 лева за нашите центи. 

Дали сите се разбере како програмата е Менувајќи и зошто центи сега стана 16 и зошто, сега, монети стана 1? Тогаш сите се по таа логика? Кул. Така што на оваа точка, програма за работа, нели? Знаеме дека тоа го прави токму она што ние го сакаме тоа да. И ние всушност не мора да го испечатите, О, што е центи во овој момент, она што е парички во овој момент. 

Ние продолжи да оди преку програмата. Се оддалечува. Кул. Ние одиме во текот dimes. Одлично. Ќе видиме дека тоа е донесена надвор 0,10 $ за скршена пара. А сега имаме две парички. Тоа е точно. 

Ние одиме во текот на пени и можеме да видиме дека ние го добивме останати центи. Хм, тоа е чудно. До тука во програмата, што требаше да го одземе мојот пени. Можеби само јас не бев го прават тоа право линија. И за жал, може да се види тука, затоа што знаеме дека се повлекува преку линии 32 и 33, тоа е местото каде нашата програма неправилно имаше променливи се кандидира. За да можеме да се погледне и да видиме, о, Јас сум тука за одземање центи, но јас не сум, всушност, додавајќи мојата монета вредност. Јас сум додавање центи. И јас не сакам да го додадете центи, сакам да го додадете во монети. Значи, ако ние го промени тоа за пари, имаме програма за работа. Јас може да работи check50. Можете само да излезете надвор од GDB право тука, а потоа работи check50 повторно. Јас само може да се направи ова. Јас треба да се направи алчен. 0.41. И тука, тоа е печатење дознаете вистинскиот одговор. 

Така што вие момци можат да се види, GDB е навистина моќна алатка за кога имаме толку многу код случува и толку многу променливи дека тоа е тешко за нас, како човек, да ги пратите. На компјутер, во GDB дебагерот, има способност да ги пратите на сè. Знам, во Visionaire, вие момци веројатно можеше да погоди некои грешки сегментација затоа што се работи надвор од границите на својата низа. Во примерот на Цезар, тоа е Токму она што го спроведува тука. 

Па јас заборавив да се провери за што ќе се случи ако јас не имаат два аргументи на командната линија. Јас едноставно не се стави во таа проверка. И така, ако јас се кандидира Debug-- јас во собата мојата точка на прекин да се во право таму. Трчам грешки. 

ВО РЕД. Је. Па, всушност, требаше GDB дека ми кажа дека беше сегментација вина таму. Јас не знам што се случува право, таму, но кога ќе го истрча, тоа е работа. Кога ќе ја стартувате линии на код преку и GDB само може да одеднаш се откажа од вас, одат нагоре и погледнете што се црвената грешка е. Тоа ќе ти кажам, еј, ти имаше дефект на сегментација, што значи дека ќе се обиде да го пристап простор во низа што не постои. Је. 

Во следниот проблем поставени на оваа недела, вие момци веројатно ќе имаат голем број на променливи лебдат наоколу. Вие нема да бидете сигурни дека она што сите тие значат во одреден момент. Па GDB навистина ќе ви помогнат во утврдувањето од она што сите тие се изедначување и да бидат во можност да се види кој визуелно. Дали некој се збунети за тоа како било од дека е работа? Кул. Во ред. Па после тоа, ние сме ќе се нурне во право во четири различни видови на сорти за оваа недела. Колкумина од вас, прво на сите, пред да почнеме, Ги прочитав целата спецификации за pset3? ВО РЕД. Горд сум на вас момци. Тоа е како половина на класа, која е значително повеќе од минатиот пат. 

Па тоа е одлично, бидејќи кога зборуваме за содржината во lecture-- или жал, во section-- Ми се допаѓа да се однесуваат многу од тоа назад на она што е pset и како сакате да го спроведе тоа во вашиот pset. Па ако дојдете има прочитате спецификации, тоа ќе да биде многу полесно за вас да се разбере она што јас го зборувам кога ќе речам, ох еј, ова може да биде навистина Добро место за спроведување на овој вид. Па оние од вас кои сте ги прочитале Спец знаеме дека, како дел од вашиот pset, ви се случува да треба да се напишете тип на сортирање. Така што ова може да биде многу корисна за многу од вас денес. 

Па ние ќе започнете со, во суштина, повеќето едноставен тип на вид, кој вид на селекција. Типичниот алгоритам за како би се обратите за ова is-- Давид отиде во текот на овие сите во предавање, па јас ќе брзо да се движат по here-- суштина, можете имаат низа на вредности. А потоа ќе се најде на Најмалата несортиран вредност и ќе трампа таа вредност со првиот несортиран вредност. И можеш само да ги повторува со остатокот од вашата листа. 

И тука е визуелна објаснување за тоа како таа ќе работи. Така на пример, ако веќе треба да почне со низа на пет елементи, индексот 0 до 4, со 3, 5, 2, 6, и 4 вредности сместени во array-- па токму сега, ние сме само ќе да се претпостави дека тие се сите несортиран затоа што ние не се тестираат на друг начин. 

Па, како еден вид селекција ќе работа е тоа дека таа прва извршена во текот на интегритет на несортиран низа. Тоа ќе одберам најмалата вредност. Во овој случај, 3, правото сега, е најмалиот. Тоа добива до 5. Не бе, 5 не е поголема than-- или ми е, не е помала than-- 3. Па минималната вредност е уште 3. И тогаш ќе дојде до 2. Компјутерот гледа, ох, 2 е помалку од 3. 2 сега мора да биде минималната вредност. И така 2 свопови со кои првата вредност. 

Па по еден поминат, ние навистина се види дека на 2 и 3 се заменети. И ние сме само ќе продолжиме да работиме ова повторно со остатокот од низата. Значи ние се случува да се кандидира само преку последните четири индекси на низата. Ќе се види дека е 3 следниот минималната вредност. Па ние ќе се разменуваат дека со 4. А потоа ние сме само ќе да се задржи работи преку сè додека на крајот, ќе дојде до низа сортирани во кои 2, 3, 4, 5 и 6 се сите подредени. Дали сите се разбере логиката за тоа како еден вид избор? 

Вие само треба некој вид на минимална вредност. Сте следење на она што е тоа. И секогаш кога ќе го најдете, вие го трампа со првата вредност во array-- или не, првиот value-- следниот вредност во низа. Кул. 

Така што вие момци вид на видов од краток поглед, ние ќе треба да pseudocode ова. Значи, ако вие момци во задниот сакате да формираат група, секој на маса може да се формира мало партнер, јас ќе одам да ви даде момци како три минути само да се зборува преку логика, на англиски јазик, за тоа како ние би можеле да бидат способни за спроведување на pseudocode да се напише еден вид селекција. И има бонбони. Ве молиме да се излезе и да се бонбони. Ако сте во грбот и се што сакате бонбони, можам да фрлаат бонбони во вас. Всушност, направи you-- кул. Извини. ВО РЕД. 

Значи, ако ние би сакале да се, како класа, пишува pseudocode за тоа како некој би можел да се пријде овој проблем, само се чувствуваат слободни. Јас само ќе одат наоколу и, со цел, да побара групи за следната линија на она што ние треба да се прави. Значи, ако вие момци сакате да започнете надвор, што е првото нешто да се направи кога ќе се обидуваш да се спроведување на начин да се реши оваа програма селективно да ги сортирате листа? Ајде само да претпоставиме имаат низа, во ред? 

ПУБЛИКАТА: Сакате да се создаде некои вид [Беззвучен] дека сте на се протега низ целата своја низа. 

АНДИ Пенг: Токму така. Па ви се случува да сакаат да iterate преку секој простор, нели? Така, одлично. Ако вие момци сакаат да ми даде Следниот line-- је, во задниот дел. 

ПУБЛИКАТА: Проверете сите за најмалите. 

АНДИ Пенг: Таму ќе одиме. Затоа сакаме да се оди преку и да се провери да се да видиме што на минималната вредност е, нели? Одам да скратите дека за да "мин." Што ви момци сакате да се направи по си нашол минималната вредност? 

ПУБЛИКАТА: [Беззвучен] АНДИ Пенг: Значи, ви се случува да сакаат да вклучете со првиот на таа низа, нели? Тоа е почетокот, јас ќе одам да се каже. Во ред. Па сега дека сте сменил првиот еден, што сакаш да се направи после тоа? Така, сега знаете дека овој овде мора да биде најмалата вредност, нели? Тогаш може да има дополнителен одмор на низата тоа е несортиран. Значи она што сакате да го направите тука, ако момци сака да ми даде следната линија? ПУБЛИКАТА: Па, тогаш ќе сакате да iterate преку остатокот од низата. АНДИ Пенг: Да. И така, што значи преку процесирањето вид на имплицира ние најверојатно ќе треба? Кој тип of-- 

ПУБЛИКАТА: Ох, дополнителна променлива? АНДИ Пенг: Веројатно друг за телефонска линија, нели? Па ние сме веројатно нема да сакате да iterate through-- одлично. А потоа ви се случува да се врати и да веројатно се провери минималните повторно, нели? И ви се случува да ги повторува ова, зашто само ќе јамки да продолжи да работи, нели? 

Така што вие момци да видите, ние само да има општа pseudocode за тоа како сакаме оваа програма да се погледне. Оваа iterate тука, она што го правиме обично треба да се напише во нашиот код ако сакаме да iterate преку низа, каков тип на структура? Мислам Christabel веќе реков тоа порано. 

ПУБЛИКАТА: А за телефонска линија. 

АНДИ Пенг: за телефонска линија? Токму така. Значи ова е веројатно ќе биде за телефонска линија. Што е чек тука ќе имплицира? Обично, ако сакате да се провери ако нешто не е нешто else-- 

ПУБЛИКАТА: Ако. 

АНДИ Пенг: Еден ако, нели? А потоа на swap тука, ние ќе одиме во текот подоцна, бидејќи Дејвид изложи дека во предавањето, како и. А потоа втората iterate implies-- 

ПУБЛИКАТА: Друг за телефонска линија. 

АНДИ Пенг: --another за телефонска линија, точно. Значи, ако ние сме во потрага во ова правилно, ние може да се види дека ние сме веројатно ќе треба за вгнездени јамка со условни изјави во таму а потоа вистински дел од кодот кој е случува да се разменуваат со вредности. Па јас сум само генерално напишан кодекс pseudocode тука. А потоа ние сме всушност ќе да се физички, како класа, се обиде да спроведе ова денес. Да се ​​вратиме во оваа ИРО. 

Ух-ах. Зошто е тоа така not-- таму е. ВО РЕД. Жал ми е, да се обидам да го зголемите малку повеќе. Таму ќе одиме. Сите правам тука е Јас направивме програма наречена "селекција / sort.c." Јас направивме низа од девет вредности, 4, 8, 2, 1, 6, 9, 7, 5, 3. Во моментов, како што можете да види, тие се подредени. n е и ќе биде оној број кој ви кажува износот на вредности имате во вашиот низа. Во овој случај, имаме девет вредности. И јас само што влегов за телефонска линија тука дека отпечатоци од несортиран низа. 

И на крајот, јас сум исто така, доби за јамка што само го отпечатоци од еднаш. Па теоретски, ако оваа програма е работи правилно, на крајот, вие треба да видите печатени за телефонска линија каде што 1, 2, 3, 4, 5, 6, 7, 8, 9 се сите правилно со цел. 

Значи имаме нашите pseudocode тука. Сака ли некој to-- Јас сум само случува да одам да побара volunteers-- ми каже точно што да напишеш ако ние сакаме да се, прво, само да iterate до почетокот на оваа низа? Што е на линија на кодот сум веројатно ќе треба тука? 

ПУБЛИКАТА: [Беззвучен] 

АНДИ Пенг: Да, се чувствувам бесплатни to-- Жалам, не треба да се застане up-- чувство слободно да се подигне вашиот глас малку. 

ПУБЛИКАТА: За int i еднаква 0-- 

АНДИ Пенг: Да, добро. 

ПУБЛИКАТА: i е помал од должината на низата. 

АНДИ Пенг: Значи имајте на ум тука, затоа што ние немаат функција што ни кажува должината на низа, ние веќе имаат вредноста која продавници тоа. Нели? Друга работа е да во mind-- во низа од девет вредности, она што се индексира? Да речеме оваа низа беше 0-3. Ќе видите дека на последните индекс е всушност 3. Тоа не е 4, иако таму четири вредности во низата. 

Па овде, ние треба да бидат многу внимателни на она што нашите услов за должина е и ќе биде. 

ПУБЛИКАТА: Зарем не би било n 1 минус? АНДИ Пенг: Тоа се случува n минус 1, точно. Дали тоа има смисла, зошто тоа е n минус 1, секој? Тоа е затоа што низите се нула-индексирани. Тие почнуваат во 0 и работи до минус 1 до n. Да, тоа е малку незгодно. ВО РЕД. И потоа-- ПУБЛИКАТА: Isnt'1 дека веќе згрижени иако, страна само не велејќи дека "помалку од или еднакво на ", а само велејќи:" помалку од? " 

АНДИ Пенг: Тоа е навистина добро прашање. Па, да. Но, исто така, на начинот на кој ние сме спроведување на правото проверка, што треба да се споредуваат две вредности. Така што всушност сакаат да напушти "на" празна. Бидејќи ако се споредат овој, не си оди имаат нешто по него да се споредуваат со, нели? Је. Па јас ++. Ајде да додадете на нашите во загради. Whoops. Одлично. Значи ние треба на почетокот од нашите надворешниот циклус. Па сега ние веројатно сакате да создаде променлива за чување песна на најмалата вредност, нели? Сака ли некој да ми даде линија на кодот кој би го направил тоа? Што ни треба, ако ние се случува да сакате да ги чувате нешто? 

Право. Можеби подобро име за таа би be-- "temp" целосно works-- можеби повеќе потполност име ќе биде, ако сакаме најмалиот value-- 

ПУБЛИКАТА: Мин. АНДИ Пенг: мин, таму ќе одиме. мин ќе биде добро. И така тука, она што го правиме сакаат да се иницијализира во моментов? Ова е малку незгодно. Бидејќи во моментов во почетокот на оваа низа, не сте се загледа во ништо, нели? Па што, автоматски, ако ние сме само на з еднакво на 0, она што сакаме да го иницијализирам нашиот прв минималната вредност? ПУБЛИКАТА: i. АНДИ Пенг: Јас, точно. Christabel, зошто сакаме да се иницијализира на i? 

ПУБЛИКАТА: бидејќи, сепак, ние сме почнуваат со 0. Па затоа ние немаме ништо да се споредат тоа да, минималните ќе завршат да бидат 0. 

АНДИ Пенг: Токму така. Па таа е точно во право. Бидејќи не сме, всушност, гледаше ништо сеуште, ние не знаеме што нашите минимални вредност е. Ние сакаме да се само да го иницијализирам да Јас, кој, во моментов, е во право тука. И како ќе продолжиме да движите надолу оваа низа, ќе се види дека, со секоја дополнителни поминам, постепено. И така во тој момент, Јас веројатно, ќе сака да сака да биде на минимум, затоа што тоа се случува да биде што и е почеток на несортиран низа. Кул. 

Така, сега сакате да го додадете за телефонска линија тука тоа е ќе iterate преку несортиран, или остатокот од оваа низа. Сака ли некој да ми даде линија на кодот кој би го направил тоа? Hint-- што ни треба тука? Она што се случува да одат во овој за телефонска линија? Је. ПУБЛИКАТА: Значи, ние би сакале да го имаат различен број, бидејќи ние сме трчање низ остатокот на низата наместо з, па можеби ѕ. 

АНДИ Пенг: Да, ѕ звучи добро за мене. Е еднакво? 

ПУБЛИКАТА: Така ќе биде ли плус 1, бидејќи сте веќе од следната вредност. А потоа и до end-- па повторно, j е помалку од n минус 1, а потоа и j ++. АНДИ Пенг: Велики. 

А потоа и во тука, ние се случува да сакаат за да се провери да се види дали нашите услов е исполнет, нели? Затоа што сакате да промена на минималната вредност ако тоа е всушност помала од она ти си тоа во споредба со, нели? Значи она што сме ние ќе сакате во оваа ситуација? Проверете за да видите. Каков вид на изјава ние сме веројатно нема ти сакаш да се користи ако се сакате да се провери нешто? 

ПУБЛИКАТА: Еден ако соопштението. 

АНДИ Пенг: Еден ако соопштението. If-- така и она што се случува да биде услов ние сакаме во внатрешноста на нашите ако изјава? 

ПУБЛИКАТА: Ако вредноста на ј е помал од вредноста на i-- 

АНДИ Пенг: Токму така. If-- па така оваа низа е наречен "низа." Одлично. Па ако array-- што беше тоа? Кажам дека повторно. 

ПУБЛИКАТА: Ако низата-ѕ е помал од Низа-и, тогаш ние ќе го промени мин. Па мин ќе биде ѕ. 

АНДИ Пенг: Дали тоа има смисла? ВО РЕД. И сега овде, ние всушност сакате да се спроведе на swap, нели? Па се сеќавам, во предавањето, дека Давид, кога тој се обидува да the-- она ​​што беше трампа it-- сок од портокал и milk-- 

ПУБЛИКАТА: Тоа беше бруто. 

АНДИ Пенг: Да, тоа беше вид на бруто. Но, тоа беше прилично добар Концептот покажувајќи време. Значи мислам на вашите вредности тука. Имаш низа мин, низа од I, или што и се обидувавме да се разменуваат тука. И најверојатно нема да ги става во едни со други, во исто време, нели? Значи она што ќе се дојде да треба да се создаде тука со цел да се разменуваат вредностите правилно? 

ПУБЛИКАТА: Привремен променлива. 

АНДИ Пенг: Привремен променлива. Значи, да се направи int Temp. Види, тоа ќе биде подобро време to-- Леле, што беше тоа? ВО РЕД. Така што ова ќе беше подобро време за името на променливата "темп." Значи, да се направи int Temp. Што ќе се дојде до постави temp еднаква тука? ПУБЛИКАТА: мин? АНДИ Пенг: Тоа е малку незгодно. Тоа всушност не е важно на крајот. Тоа не е важно она што цел ке го одберете да се разменуваат со додека си прави сигурни дека сте следење на она што го менуваат. 

ПУБЛИКАТА: Тоа може да биде низа-i. 

АНДИ Пенг: Да, ајде да направиме низа-i. И тогаш што е следната линија на код сакаме да имаме тука? ПУБЛИКАТА: Низа-и еднакво низа-ѕ. АНДИ Пенг: И на крај? ПУБЛИКАТА: Низа-ѕ еднаква низа-i. ПУБЛИКАТА: Или низа-ѕ еднаквите низа-temp-- или, темп. 

АНДИ Пенг: Во ред. Значи, да се кандидира и да се види ова ако тоа се случува да се работи. Каде што се што се случува? Ох, тоа е проблем. Види, на линија 40, ние сме обидуваат да го користите низа-ѕ? Но, каде ѕ постојат само во? 

ПУБЛИКАТА: Во за телефонска линија. АНДИ Пенг: Токму така. Значи она што сме ние ќе треба да се направи? 

ПУБЛИКАТА: Дефинирајте го надвор the-- ПУБЛИКАТА: Да, претпоставувам имате да се користи друг ако изјава, нели? Па како, ако minimum-- сите права, дозволете ми да мислам. 

АНДИ Пенг: Дечки, се обиде да ги погледне Ајде да видиме, што е нешто што може да се направи во оваа ситуација? 

ПУБЛИКАТА: Во ред. Значи, ако минималната не е еднакво на j-- па ако на минимум е сеуште i-- тогаш не би требало да се разменуваат. 

АНДИ Пенг: Дали тоа еднакви ли? Што сакате да се каже во оваа ситуација? 

ПУБЛИКАТА: Или да, ако минимум не е еднакво јас, да. АНДИ Пенг: Во ред. И кој го решава, вид на, нашите проблеми. Но дека се уште не се реши проблемот на она што се случува ако j-- бидејќи ѕ не постои надвор од него, она што дали ние сакаме да се направи со неа? Ја прогласи за надвор? Ајде да се обидеме да ја управува таа. Ух-ах. Нашиот вид не е работа. 

Како што можете да видите, нашата првична Низа имале тие вредности. По што таа треба да има е во 1, 2, 3, 4, 5, 6, 7, 8, 9. Тоа не е работа. Ahh. Што ќе правиме? ПУБЛИКАТА: грешки. АНДИ Пенг: Во ред, можеме да се обидеме тоа. Можеме да debug. Одзумирате малку. Ајде да се постави нашата точка на прекин. Ајде да одиме like-- ОК. 

Па затоа што веќе знаете дека овие редови, од 15 до 22, се working-- бидејќи сите го правам е само преку процесирањето и printing-- Јас може да оди напред и да го прескокнете тој. Ајде да започне на линијата 25. OOP, дозволете ми да се ослободи од тоа. 

ПУБЛИКАТА: Значи на прекин на каде дебагирање почнува? АНДИ Пенг: Или запира. ПУБЛИКАТА: Или запира. АНДИ Пенг: Да. Можете да го поставите на повеќе точки на прекин и тоа само може да скокаат од една до друга. Но, во овој случај ние не знаеме каде што грешка се случува. Па ние само сакаме да да почне од врвот надолу. Да. ВО РЕД. 

Па оваа линија, тука, ние може да стапи во акција. Можете да ја видите овде долу, имаме низа. Тоа се вредностите кои се во низа. Дали ви се види дека, како индекс 0, тоа одговара на value-- ох, Одам да се обиде да го зголемите. За жал, тоа е навистина тешко да see-- на индекс низа 0, имаме вредност од 4 и тогаш така натаму и така натаму. Имаме нашите локални променливи. Сега јас е еднаква на 0, што ние сакаме да биде. 

И па ајде да ги задржи Менувајќи. Нашата минимум е еднаков на 0, која ние исто така сакаме да биде. А потоа можеме да влезат во нашиот втор за јамка, во низа-ѕ е помалку од низа-I, што тоа не беше. Толку си се види како дека прескокнат во текот тоа? 

ПУБЛИКАТА: Значи, ако треба на минимум, сите that-- дека не треба да биде внатре во првата за телефонска линија? АНДИ Пенг: Не, затоа што се уште сакаш да се тестираат. Што сакате да направите споредба на секои време, дури и откако ќе поминува низ него. Вие не само што сакаат да го прават на првиот премин преку. Сакате да го направи тоа со повторно секој дополнителен премин. Значи сакате да се провери за Вашата состојба внатре. Значи, ние сме само ќе продолжи да работи низ овде. Јас ќе ви даде момци навестување. Тоа има врска со фактот дека кога сте одјавувањето вашиот условена, вие не сте проверка за правилно индекс. Па сега сте одјавувањето за низа индекс на J е помалку од низа Индекс на i. Но, она што ви се прави во на почетокот на за телефонска линија? Зарем не сте поставување ѕ еднаква јас? 

Да, па ние всушност може да излезете дебагерот тука. Па ајде да ги разгледаме во нашата pseudocode. For-- ние ќе треба да со почеток во з изнесува 0. Ние ќе треба да се оди до n 1 минус. Ајде да се провери, дали имаме тоа право? Да, тоа е во право. 

Па потоа внатре тука, ние сме случува да се создаде минималната вредност и да го поставите еднаква на i. Го правиме тоа? Да, го сторија тоа. Сега во нашата внатрешна за телефонска линија, ние сме случува да се направи з ѕ еднаква на n 1 минус. Го правиме тоа? Навистина, ние го сторивме тоа. 

Па сепак, она што сме ние споредување тука? 

ПУБЛИКАТА: ѕ плус 1. АНДИ Пенг: Токму така. А потоа ви се случува да сакаат да се постави минимум вашиот еднаква ѕ плус 1, како и. Па отидов преку тоа навистина брзо. Дали ви момци се разбере зошто тоа е ѕ плус 1? ВО РЕД. 

Значи во вашиот низа, во Прв пат си помине, Вашиот за телефонска линија, за int Јас еднакво на 0, ајде само се претпостави дека тоа се уште не е променет. Имаме низа, во целост, само четири несортиран елементи, нели? Значи, ние сакаме да се иницијализира з еднаков на 0. И јас се случува да се само поминува низ овој циклус. И така во првото поминување, ние ќе да се иницијализира со променлива наречена "мин" кои, исто така, е еднаква јас, затоа немаме минимална вредност. Па тоа е во моментов еднаква на 0, како и. И тогаш ние ќе треба да поминат низ. И ние сакаме да iterate повторно. Сега дека ние сме го најдовте тоа што нашите минимални е, ние сакаме да iterate преку повторно за да се види дали тоа е споредување, нели? Па ј, тука, се случува за да се еднакви i, која е 0. А потоа ако низа з ѕ плус, кој е оној кој е следниот над, како помалку од она што вашата актуелна минимум вредност е, сакате да се разменуваат. 

Па да речеме имаме доби, како, 2, 5, 1, 8. Токму сега, јас е еднаква на 0, а ѕ е еднаков на 0. И тоа е нашиот минималната вредност. Ако низата-ѕ плус i-- па ако на едно тоа е по една ние барате е поголем од оној пред тоа, тоа се случува да стане минимум. 

Па еве гледаме дека 5 е не помалку од тоа. Значи тоа се случува да биде 5. Гледаме дека 1 е помалку од 2, нели? Така, сега знаете дека нашата минимум е ќе биде вредноста на индексот на 0, 1, 2. Да? И тогаш кога се фаќате тука, можете да го трампа точни вредности. 

Па кога ќе момци беа само имаат ѕ пред, вие не се гледа во еден по него. Што го барате во со иста вредност, која Затоа само не прави ништо. Дали тоа има смисла за сите, Зошто ни е потребно дека плус 1 таму? ВО РЕД. Сега ајде да се поминува низ него да се направи сигурни дека остатокот од кодот е точна. Зошто е тоа да се случи? Ах, тоа е мин во право тука. Дека споредуваме погрешна вредност. О не. 

Oh yeah, овде бевме Замена на погрешни вредности, како и. Бидејќи бевме во потрага на i и j. Тие се оние што бевме проверка. Ние всушност сакате да се разменуваат со минимум, сегашниот минимум, со она што е надвор е. И како што вие момци можат да се види по тука, ние имаме сортирана низа. Тоа едноставно мораше да го направи со фактот дека кога бевме проверка на вредности дека споредуваме, ние не беа во потрага на вистинските вредности. Бевме во потрага по истиот тука, всушност, не ја менуваат. Што треба да се погледне во еден следната за него, а потоа можете да го трампа. Значи, тоа беше вид на bugging нашиот код порано. И она што го направив тука е сè дебагерот можеше да направи за вас Јас само тоа го правеше на одбор, бидејќи тоа е полесно за да ја видите, наместо обидот за да зумирате на дебагерот. Дали тоа има смисла за секого? Кул. 

Во ред. Можеме да се движат за да се зборува за асимптотска нотација, што е само фенси начин да се каже на runtimes на сите од овие видови. Па знам Давид, во предавањето, начнавте runtimes. И тој отиде во текот на целата формула за тоа како да се пресмета runtimes. Не се грижи за тоа. Ако сте навистина љубопитни за тоа како таа работи, се чувствуваат слободни да разговара со мене по дел. Можеме да одиме преку формулите заедно. Но сите вие ​​момци мора навистина знаеме е дека n квадрат повеќе од 2 е истото што и N на квадрат. Бидејќи најголемиот број, експонент, расте најмногу. И така за нашите цели, сите ние се грижиме за е дека гигант број, кој постојано расте. 

Значи она што е најдобар случај траење на селекција кој вид? Ако си оди за да се има да iterate преку листа а потоа iterate преку остатокот од таа листа, колку пати се ви се случува да веројатно, во најлош case-- во најдобар случај, sorry-- извршите преку? Можеби подобро прашање е да прашам, што е најлош случај траење на селекција кој вид. ПУБЛИКАТА: n квадрат. АНДИ Пенг: Тоа е n квадрат, во право. Така е одличен начин да се размислува за ова е како, секое време имате два за вгнездени јамки, тоа се случува да биде N на квадрат. Бидејќи не само што сте се протега низ уште еднаш, ќе мора да се врати наоколу и да поминува низ него уште еднаш во внатрешноста за секој вредност. Па во тој случај, си работи n Времето n квадрат, што is-- ми е, n n пати, што е еднакво n квадрат. 

Вид и е исто така малку уникатен, во смисла дека тоа не е важно дали овие вредности, веќе се во ред. Сè уште нема да ја извршите преку онака. Да речеме ова е 1, 2, 3, 4. Без оглед на тоа дали е или не е во цел, тоа сепак ќе се трчаше низ и се уште се проверува на минималната вредност. Тоа ќе се направи на Ист број на проверки секој пат, дури и ако тоа всушност не ги допирајте ништо. 

Па во таков случај, најдобро и најлошо runtimes се всушност еквивалентни. Толку очекуваното траење на селекција вид, кои ние ги именуваат со симболот на тета, тета, во овој случај, исто така, ќе биде n квадрат. Сите три од овие ќе биде n квадрат. Е јасно на сите зошто на траење е N на квадрат? 

Во ред. Па јас сум само ќе брзо да се кандидира па сè до крајот на сорти. Алгоритамот за меур sort-- сеќавам, ова беше првиот Давид отиде во текот на предавањето. Во суштина, ќе влезете низ целата листа а вие сте само swap-- споредба на две во исто време. И ако некој е поголема, отколку едноставно ги трампа. Значи, ако тие се поголеми, ќе се разменуваат. Јас имам официјален во право тука. 

Па да речеме сте имале 8, 6, 4, 2. Што би се споредат 8 и 6. Ќе треба да ги трампа. Сакаш да се споредат 8 и 4. Ќе треба да ги трампа. Ако имаш да се разменуваат со 8 и 2, промена на нив, како и. Па во таква смисла, може да се види, играа во текот на долг временски период, како вредности на видот на балон за да се на краевите, која е причината зошто ние го нарекуваме меур вид. 

Ние само ќе ја извршите преку повторно на нашата втора помине, и нашиот трет обид, и нашите четвртиот помине. Во суштина, меур вид само работи се додека не се направи повеќе свопови. Па во таа смисла, ова е само општата pseudocode за тоа. Не се грижи, тие сите ќе бидат на интернет. Ние не треба да се, всушност, оди во текот на овој. 

Ние само се иницијализира контранапад променлива која започнува од 0. И ние iterate преку целата низа. И ако една вредност is-- ако ова вредноста е поголема од таа вредност, си оди за да ги трампа. И тогаш ти си само ќе се одржи во живот. И ви се случува да се брои. А вие сте само ќе продолжиме да го правиме ова додека бројачот е поголема од 0, што значи дека секој пат кога ќе треба да се разменуваат, знаете што сакате да одите назад и проверете уште еднаш. Сакате да се задржи проверка додека не знаете што вие не мора да се разменуваат повеќе. 

Значи она што се најдобрите и најлошите случај runtimes за меур вид? Hint-- и ова е всушност различни од селекцијата вид во смисла дека овие два одговори не се исти. Размислете за тоа што ќе се случи во случај ако тоа е веќе сортирана. И да размислува за она што ќе се случи ако тоа беше во случај кога тоа не беше подредени. И може да се вид на работи преку зошто тоа се случува. Јас ќе ви даде момци, како, 30 секунди да се размислува за тоа. 

ВО РЕД. Дали некој има погоди во тоа што го најлош случај траење на меур вид е тоа? Је. 

ПУБЛИКАТА: Дали тоа ќе биде, како, n пати n 1 минус или нешто слично? Како, секој пат кога тоа ќе трае, тоа е само, како, една трампа помалку дека што и да беше. 

АНДИ Пенг: Да, па ти си сосема во право. И ова е случај во кој вашите Одговорот е, всушност, повеќе комплекс од оној што ние треба да се даде. Значи тоа се случува да run-- сум ќе ги избрише сите овој овде. Е секој добар? Може ли да се избрише овој? ВО РЕД. Ви се случува да се кандидира до n пати прв пат, право? И тие се случува да се кандидира преку n 1 минус втор пат, нели? А потоа ви се случува да се задржи случува, н рудник 2, итн. Давид го направи ова на час, каде што, ако се додаде на сите оние вредности, ќе добиете нешто што е like-- yeah-- повеќе од 2, што во суштина само се намалува надолу до n квадрат. Си оди за да се добие чудни дел во таму. И така само знам дека на n квадрат секогаш има приоритет над дел. И така во овој случај, на најлошото траење ќе биде n квадрат. Ако тоа беше во опаѓачки ред, мислам, треба да се направи трампа секој време. 

Што ќе биде, потенцијално, најдобар случај траење? Да речеме, ако на листата веќе беше со цел, што ќе биде на траење? 

ПУБЛИКАТА: n. АНДИ Пенг: Тоа е n, точно. И зошто тоа е n? ПУБЛИКАТА: Затоа што само мора да се провери за секој еднаш. АНДИ Пенг: Токму така. Така на најдобар можен траење, Ако оваа листа веќе беше sorted-- да речеме 1, 2, 3, 4-- вас само ќе се оди преку, ќе се провери, ќе ја видиш, о, сите тие пан надвор. Јас не треба да се разменуваат. Готов сум. Па во тој случај, тоа е само n или бројот на чекори што само мораше да се провери во првата листа. 

И после тоа, ние сега се погоди вметнување вид, каде што алгоритмот е суштински да се подели тоа во сортирани и несортиран дел. А потоа еден по еден, на несортиран вредности се вметната во нивните соодветни позиции во почетокот на листата. 

Така на пример, имаме листа на 3, 5, 2, 6, 4 повторно. Ние знаеме дека тоа е во моментов несортиран бидејќи ние сме само почна да гледа во него. Ги погледнеме и знаеме дека првата вредност е сортирана, нели? Ако сте само гледајќи во низа големина, знаете дека тоа се подредени. 

Па тогаш знаеме дека другите четири се несортиран. Ние одиме преку и гледаме дека вредност. Ајде да се вратиме. Види дека вредноста на 5? Ние ги погледне во него. Ние го споредуваат со 3. Ние знаеме дека тоа е поголема од 3, за да знаеме дека тоа е сортирана. Значи, ние сега знаеме дека првите две се подредени и последните три не се. 

Ние да ги разгледаме во 2. Ние прво го провериш со 5. Дали е помалку од 5? Не е. Значи ние треба да ги бараме надолу. Тогаш треба да се провери 2 исклучување 3. Дали е помалку од? Бр Па да знаете на 2 мора да биде вметната во предниот и 3 и 5 и мора да се турка надвор. Направите ова повторно со 6 и 4. А ние само се задржи проверка суштина, каде што ние едноставно проверете, чек, чек. И додека не е во право позиција, ние вид на само вметнете ја во право позиција, каде што е името на е дојден. 

Па тоа е само алгоритам, pseudocode по себе, вид, за тоа како ние ќе се имплементираат вметнување вид. Pseudocode е тука. Тоа е за сите на интернет. Не се грижи, ако вие момци се обидувајќи се да ја ископирате оваа надолу. Значи уште еднаш, она што исто question-- ќе биде најдобро и најлошо runtimes за вметнување вид? Тоа е многу сличен на последното прашање. Јас ќе ви даде момци, како, 30 секунди да се размислува за тоа како добро. 

Добро Сака ли некој да дај ми најлошите траење? Је. 

ПУБЛИКАТА: n квадрат. 

АНДИ Пенг: Тоа е n квадрат. И зошто е тоа n квадрат? 

ПУБЛИКАТА: Затоа што во обратен редослед, имаш да се оди преку n n пати, што is-- АНДИ Пенг: Да, точно. Па истото како во вид на меур. Ако оваа листа е во опаѓачки редослед, ти си ќе треба да се провери прво еднаш. А потоа со секој дополнителна вредност, ти си ќе треба да се провери тоа против секоја вредност, нели? И така целосно, си оди за да се направи на пати n помине уште n помине, која е N на квадрат. Што е со најдобар случај? Је. 

ПУБЛИКАТА: N минус 1, бидејќи Првиот е веќе на квадрат. 

АНДИ Пенг: Значи, во близина. Одговорот е всушност n. Бидејќи додека првата е подредени, тоа не може да го actually-- ние само lucked надвор, во дека на пример, дека 2 се случи да биде најмалиот број. Но, тоа не е секогаш случај. 2 ако е веќе сортирана на почетокот но ќе се погледне и има 1 тука, 1 ќе се судрат. И тоа се случува да се стави крај Регистрација се bumped онака. 

Значи, во најдобар случај, тоа е всушност само ќе биде n. Ако имаш 1, 2, 3, 4, 5, 6, 7, 8, ти си случува да се кандидира преку дека целата листа еднаш за да се провери да се види дали се е во ред. Е јасно на сите работи Времето на селекција, како? Знам дека јас ќе одам преку овие навистина брзо. Но, само знам дека ако знаете општите концепти, треба да биде добро. ВО РЕД. Па јас само ќе ви даде момци можеби, како, една минута за да разговарате со вашите соседи за тоа што се само некои од главните разлики меѓу овие видови на сорти. Ние ќе одиме во текот тоа наскоро. ПУБЛИКАТА: Ох, ОК. АНДИ Пенг: Да. ВО РЕД. Кул, да свикува нови повторно како класа. ВО РЕД. Така што ова е вид на отворена прашање во смисла дека има многу одговори на нив. И ние ќе одиме во текот на некои од нив на кратко. Сакав само да ви се момци размислување за она што се разликува сите три видови на сорти. И чув, исто така, во голема question-- она ​​што не спојуваат вид направам? Големо прашање, бидејќи тоа е она што ние сме ги опфаќа следните. 

Па се спојат вид е еден вид, кој функционира многу различно од другите видови. Како вие момци можат да see-- Давид го направи тоа демо каде што тој ги имаше сите кул звуци на видат колку се спојат вид трчаше, како, бесконечно побрзо од другите два типа? ВО РЕД. Значи, тоа е затоа што се спојуваат вид спроведува таа поделеност и освојување концептот дека ние сме Зборувавме за многу во предавањето. Во таа смисла дека ние сакале да работат попаметно и полесно, кога ќе се подели и освојување на проблеми, и ги скрши надолу, а потоа ги стави заедно, добри нешта секогаш се случи. 

Па начинот на кој се спојуваат вид во суштина работи е тоа што таа ја дели несортиран низа на половина. И тогаш не е двете половини на низи. И тоа само оние кои се подредува на две половини. Тоа само продолжува дели на половина, во половина, на половина додека сè е сортирана а потоа рекурзивно го става сите заедно. 

Значи тоа е навистина апстрактна. Значи ова е само малку pseudocode. Дали тоа има смисла во начинот на кој се работи? Па да речеме дека имате низа од n елементи, нели? Ако n е помалку од 2, може да се врати. Затоа што знаете дека ако има само едно нешто, тоа мора да се решат. Друго, ќе се најде решение за левата половина, а потоа ќе се најде решение за десната половина, а потоа ќе се спојат. 

Па така додека таа изгледа навистина лесно, во реалноста, размислувам за тоа е вид на тешко. Зашто си како, Па, тоа е вид на работи на себе. Нели? Тоа е водење на себе. Па во таа смисла, Дејвид допре по рекурзија во класата. И тоа е концепт ние ќе разговараме за повеќе. Тоа е дека ова, овие две линии тука, всушност, е само програма тоа го кажувам за да се кандидира со различни влез. Така, наместо да се кандидира со целината на n елементи, можете да го срушат во левата половина и десната половина а потоа се кандидира повторно. 

А потоа ние ќе се погледне во тоа визуелно, бидејќи јас сум визуелно ученик. Таа работи подобро за мене. Па ние ќе се погледне во визуелен пример тука. 

Да речеме дека имаме низа, шест елементи, 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-- не сте во потрага по нив како одделни елементи, а не како целина? АНДИ Пенг: Да. Значи она што се случува е дека во основа се создава сосема нов низа. Па да знаете дека, овде, имам две низи со големина 3, нели? Па да знаете дека мојот низа сортирани треба да има шест елементи. Така да треба само да се создаде нова количина на меморија. Па ти си вид на како се непотребното на меморијата, но тоа не е важно бидејќи тоа е толку мал. Така ќе се погледне на 1 и ќе се погледне на 2. И знаеш дека на 1 е помалку од 2. Па да знаете дека треба да оди во 1 на почетокот на сите од нив. 

Вие дури и не треба да се се погледне на 3 и 5. Па да знаете 1 оди таму. Тогаш вие во основа се исецка исклучите 1. Тоа е, како, мртвите за нас. Тогаш ние само треба 2, 3, 5, а потоа и 4 и 6. И тогаш знаете дека, вие споредба на 4 и 2, о, 2 треба да оди таму. Па да паднала од 2 надолу, го исецка исклучи. Па, тогаш едноставно треба 3 и 5 во 4 и 6. А вие само го чува секое отсечено додека не ги стави во низа. 

ПУБЛИКАТА: Па ти си само секогаш споредување на [Беззвучен]? 

АНДИ Пенг: Токму така. Па во таа смисла, ти си само споредување, во суштина, број еден против друг број. И бидејќи знаете дека тоа е сортирана, можете не мора да се погледне преку сите на броеви. Вие само треба да се погледне на првиот. И можеш само да паднала ги надолу, бидејќи знаете тие припаѓаат таму каде што треба да припаѓаат. Је. Добро прашање. 

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

ВО РЕД. Така Давид исто така отиде во текот на оваа лекција. Кои се најдобрите случај runtimes, најлош случај runtimes, и очекуваните runtimes на спојување вид? А неколку секунди да се размислува. Ова е прилично тешко, но вид на интуитивен, ако мислите дека за тоа. Во ред. 

ПУБЛИКАТА: е најлош случај n log n? АНДИ Пенг: Токму така. И зошто е тоа n log n. 

ПУБЛИКАТА: Зарем тоа не е поради тоа што станува експоненцијално побрзо, па тоа е како функција од кои наместо само едноставно да се биде н квадрат или нешто? АНДИ Пенг: Токму така. Па заради тоа траење на оваа е n најавите n е because-- што си прави во сите овие чекори? Ти си само тоа сечкање на половина, нели? И така, кога ние го работиме на логирате, сето она што таа го прави е делење на проблемот на половина, на половина, на половина, во повеќе половини. И во таа смисла, може да се вид елиминирање на линеарниот модел дека ние сме биле користење. Затоа што кога ќе се исецка работите на половина, тоа е се логирате. Тоа е само математичка начин на кои е претставена. 

А потоа, конечно, на крајот, ти си само да направите една последна проследување да се стави сите од нив со цел, нели? И така, ако вие само треба да проверете една работа, тоа е n. И така ти си вид на множење на двете заедно. Па тоа е како ќе го добивме тоа конечна проверете за N овде долу со најавите на n до тука. И ако се размножуваат нив, тоа е n log n. 

И така на најдобар случај и најлош случај и се очекува сите n log n. Тоа е, исто така, како и друг вид. Тоа е како избор вид во смисла дека тоа не е важно она што вашата Листата е, тоа е само ќе за да го прават истото секој време. ВО РЕД. Така што вие момци можат да се види, иако видовите кои што ние сме го through-- n квадрат, тоа не е многу ефикасен. Па дури и овој n log n е не најефикасен. Ако вие момци се љубопитни, таму е вид механизми кои се толку ефикасни што тие се речиси суштина е рамен во траење. 

Имаш некои најавите n е. Имаш некои Дневник н е. Ние не ги допре нив во оваа класа, токму сега. Но, ако вие момци се љубопитни, се чувствуваат слободни да google, што е најефикасен сортирање механизми. Не знам, не постојат некои навистина смешни оние, like-- има некои навистина смешни оние кои луѓе прават. И се прашувате како тие некогаш сте размислувале за тоа. Па Google, ако имате некои резервни време, на, она што се некои смешни начини дека people-- како и ефикасен ways-- луѓе сме биле во можност да се спроведе сорти. ВО РЕД. И тука е само корисна малку шема. Знам дека сите од вас, пред тоа квиз 0, ќе биде во вашата соба, веројатно во обид да запаметат дека. Така што е убаво во таму за вас момци. Само не заборавајте логиката дека made-- зошто тие бројки се случуваат. Ако си секогаш изгубени, само бидете Дали сте сигурни дека знаете што се видови. И можете да ја извршите преку нив во твојот ум да дознаам зошто оние одговори се тие одговори. 

Во ред. Па ние ќе треба да се движи за, конечно, да го барате. Бидејќи, како оние од вас кои ја прочитале pset, пребарување е исто така дел од Проблемот оваа недела поставува. Ќе ви биде побарано да се имплементира два типа на пребарувања. Една од нив е и линеарно пребарување еден е бинарно пребарување. 

Па линеарно пребарување е прилично лесно. Вие само сакате да пребарувате елемент на листа за да видите дали ќе го добие. Вие само треба да iterate преку. И ако тоа е еднакво на нешто, можете само да го врати, нели? Но она што ние сме најмногу заинтересирани за зборува за е бинарна пребарување, право, кое е подели па владеј механизам кој Давид се демонстрираат во предавањето. 

Се сеќавам пример телефонот книга дека тој не продолжи со формирањето, онаа што тој вид на мачеше малку на минатата година, каде што ќе се подели на проблемот на половина, на половина, на половина, повторно и повторно, се додека не се најде она што го барате? И имаш траење на тоа како добро. И што можете да видите, тоа е значително поефикасен од било кој друг тип на пребарување. 

Па начинот на кој ние би се обратите за спроведување на бинарни пребарување е, ако имавме низа, индекс од 0 до 6, седум елементи, можеме да погледнеме во средината, right-- Жал ми е, ако нашето прашање first-- ако сакаме да го поставиме прашањето за тоа, дали низата содржи елемент на 7, очигледно, се луѓе, а кои имаат толку мал низа, тоа е лесно за нас да се каже да. Но на начин да се спроведе бинарен пребарување ќе биде да се погледне во средината. 

Ние знаеме дека индексот 3 е средината, затоа што ние Знаеме дека постојат седум елементи. Она 7 поделено со 2? Можете да се исецка надвор тој дополнителен 1. Имаш 3 во средината. Така е низа од 3 еднаква на 7? Тоа не е, нели? Но можеме да направиме неколку проверки. Е низа од 3 или помалку од 7 е низа од 3 поголем од 7? 

И знаеме дека тоа е помалку од 7. Па знаеме дека, ох, тоа мора да не биде во левата половина. Ние знаеме дека тоа мора да биде на десната половина, нели? Па ние само може да се исецка надвор половина на низата. Ние дури и не мора да се погледне во него повеќе. Затоа што знаеме дека половина од нашите problem-- ние знаеме дека одговорот е во на десната половина на нашиот проблем. Па ние само погледнете во тоа сега. 

Па сега ние се погледне на средината на она што остана. Тој индекс 5. Да го стори истото се провери повторно и гледаме дека тоа е помала. Па ние со нетрпение од лево на тоа. А потоа ќе видиме дека чек. Е вредност на низата на индекс 4 еднаква на 7? Е. За да можеме да се вратат точно, затоа што најдовме вредност во нашата листа. Дали начинот Отидов преку тоа има смисла за секого? ВО РЕД. Јас ќе ви даде момци можеби, како, три, четири минути да дознаам како да pseudocode ова. 

Па замисли Те прашав да се напише функција наречена пребарување (), кој се вратил вредност, Булова вредност, тоа беше вистина или false-- како, точно ако се најде на вредност, неточна ако не сте. А потоа ќе се донесен во вредноста што барате во вредности, кои е array-- ох, јас дефинитивно се стави дека во погрешно место. ВО РЕД. Относнотова, кои треба да имаат бил на правото на вредности. И тогаш int n е број на елементите во таа низа. Како ќе одат за обидот да pseudocode тој проблем во? Јас ќе ви даде момци како три минути да се направи тоа. Не, јас мислам дека има only-- Да, има едно право тука. ПУБЛИКАТА: Може ли? АНДИ Пенг: Да, јас го добив. Е тоа што работи? Добро, кул. 

ВО РЕД. Ред момци, ние сме случува да го стават под контрола. ВО РЕД. Така претпоставуваат имаме оваа прекрасна малку низа со n вредности во него. Јас не се подготви линии. Но, како ќе одиме за се обидувам да напишам ова? Сака ли некој да дај ми на првата линија? Ако сакате да ми даде првата линија на овој pseudocode. 

ПУБЛИКАТА: [Беззвучен] Публика: Вие би сакале да iterate through-- ПУБЛИКАТА: Само уште еден за телефонска линија? ПУБЛИКАТА: --for. 

АНДИ Пенг: Па ова ми е малку незгодно. Мислам about-- сакате да продолжи да работи овој циклус одново и одново, до кога? 

ПУБЛИКАТА: До [Беззвучен] вредноста е еднаква на таа вредност. АНДИ Пенг: Токму така. За да можете да всушност само write-- ние дури и може да го поедностави повеќе. Ние само може да се направи додека јамка, нели? Така што само може да има loop-- ние знаеме дека тоа е некое време. Но за сега, јас ќе одам да се каже "циклус" - со што? Јамка until-- она ​​што е нашите завршува состојба? Мислам дека го слушнале. Слушнав некој велат дека тоа. 

ПУБЛИКАТА: Вредности еднаква на средината на теренот. АНДИ Пенг: го кажам уште еднаш. ПУБЛИКАТА: Или, до вредноста сте во потрага за е еднаква на средната вредност. 

АНДИ Пенг: Што ако тоа не е таму? Што ако вредноста сте во потрага поради тоа што не е, всушност, во оваа низа? ПУБЛИКАТА: Се враќате назад 1. 

АНДИ Пенг: Но, она што ние сакаме да го јамка се додека ако имаме состојба? Је. 

ПУБЛИКАТА: До има само една вредност? АНДИ Пенг: Можете јамка until--, па да знаете дека сте случува да имаат вредност макс, нели? И знаеш дека си оди да има вредност мин, нели? Затоа што, исто така, тоа е нешто Јас заборавив да кажам пред, дека нешто што е критични за бинарни пребарување е тоа што вашиот низа е веќе сортирана. Бидејќи не постои начин да се направи ова, ако тие се само случајни вредности. Ти не знаеш, ако еден е поголеми од другите, нели? 

Па да знаете дека вашиот максимум и твојот минути сме тука, нели? Ако си оди за да биде адаптација вашиот максимум во твојот минути и mid-- ајде да се претпостави вашиот средна вредност е во право here-- си оди за да се основа јамка се додека минималните права е за иста како вашата макс, десно, или ако вашиот максимум не е иста како вашата мин. Нели? Затоа што кога ќе се случи тоа, да знаеш дека ти на крајот го погоди иста вредност. Па сакате да јамка до вашиот мин е помалку од или еднакво to-- Упс, не помалку од или еднакво на, на друг начин around-- максимумот изнесува. 

Дали тоа има смисла? Зедов неколку обиди да се добие тоа право. Но јамка додека вашиот максимум вредност во суштина е речиси помалку од или еднакво на минимум, нели? Тоа е кога знаеш дека сте обединети. ПУБЛИКАТА: Кога ќе се вашиот максимум вредност да биде помал од минималниот? АНДИ Пенг: Ако се задржи прилагодување, која е она што се случува што треба да се прави во овој. Дали тоа има смисла? Минимум и максимум се само цели броеви кои ние сме веројатно случува да сакаат да се создаде за да се задржи пратите на местото каде што го барате. Бидејќи постои низа без оглед на она што го правиме. Како, ние не сме всушност физички секое отсечено низа, нели? Ние сме само прилагодување каде што го барате. Дали тоа има смисла? 

ПУБЛИКАТА: Да. 

АНДИ Пенг: Во ред. Па ако тоа е услов за нашата телефонска линија, она што сакаме во внатрешноста на овој циклус? Што ќе се сакаат да се направи? Значи, токму сега, ние го добивме максимум и мин, десно, најверојатно создадени се тука некаде. Ние ќе треба да веројатно сакате да се најде средина, нели? Како ќе се дојде да биде способни да се најде на средината? Што е mathematical-- ПУБЛИКАТА: Макс плус поделено со 2 мин. АНДИ Пенг: Токму така. Дали тоа има смисла? А дали вие момци се види зошто ние не само use-- зошто ние го направи ова наместо да го прават само n поделено со 2? Тоа е затоа што n е вредност кој ќе остане иста. Нели? Но како што ние ги прилагодуваме нашите минимални и максималните вредности, тие се случува да се промени. И како резултат на тоа, нашата средина Ќе се промени премногу. Па тоа е причината зошто ние сакаме да го направите ова, токму тука. ВО РЕД. 

И тогаш, сега кога ние Наидовме our-- је. 

ПУБЛИКАТА: Само брзо question-- кога ќе се каже мин и макс, ние се претпостави дека тоа е веќе сортирана? 

АНДИ Пенг: Да, тоа е, всушност, предуслов за бинарна пребарување, кои што треба да знаеш дека се подредени. Која е причината зошто тој вид, ќе напишете во вашиот проблем во собата пред вашиот бинарни пребарување. ВО РЕД. Па сега дека знаеме каде нашата средина е, она што сакате да го направите тука? 

ПУБЛИКАТА: Ние сакаме да се споредат дека на другиот. АНДИ Пенг: Токму така. Така си оди за да се споредат средината до вредност, нели? И она што не го кажа тоа ни кога ќе ги споредиме? Што сакаме да се направи потоа? 

ПУБЛИКАТА: Ако вредноста е поголема од средината, сакаме да ја отсече. АНДИ Пенг: Токму така. Па ако вредноста е поголема од средината, ние сме случува да сакаат да се променат овие минимум и maxes, нели? Што сакаме да се промени? Значи, ако знаеме вредноста е некаде овде, она што го правите ние да се промени? Ние сакаме да ги промениме нашите минимум да биде во средината, така? А потоа и на друго место, ако тоа е во овој половина, она што сакаме да се промени? 

ПУБЛИКАТА: Твоето максимум. АНДИ Пенг: Да. И тогаш ти си само ќе да се задржи looping, нели? Затоа што сега, по едно повторување преку, имаш макс тука. А потоа можете да рекалкулиране на средината. А потоа може да се споредуваат. И ви се случува да се насочи до мин и maxes се обединети во суштина. И тоа е кога знаеш дека сте го погоди на крајот од неа. И или сте ја најдов или ако не сте во тој момент. 

Дали ова има смисла за секого? ВО РЕД. Ова е многу важно, затоа што ќе имаат да се напише ова во вашиот код вечерва. Но вие момци имаат доста добра смисла на она што треба да се прави, што е добро. ВО РЕД. Значи имаме околу седум минути до крајот секција. Па ние ќе се зборува за оваа pset дека ние ќе се прави. Па pset е поделена на две половини. Првата половина вклучува спроведување на наоѓалиштето во која ќе се пишуваат линеарно пребарување, бинарни пребарување и сортирање алгоритам. 

Така што ова е прв време во pset каде ние ќе бидеме во кои ви даваат момци она што се нарекува код за дистрибуција, што е код кои ги имаат пред-напишани, но само остави некои парчиња надвор за да се стави крај на пишување. Па вие момци, кога ќе се погледне на овој код, може да добие навистина исплашена. Ако сте само се допаѓа, ahh, јас не знам што тој го прави, Не знам, како, што се чини дека толку комплицирано, Ahh, да се релаксираат. Во ред е. Читање на спец. Спец ќе да ви објаснам што точно она што сите од овие програми се прави. 

На пример, generate.c е програма што ќе дојде со вашиот pset. Вие не всушност треба да го допрат, но што треба да се разбере она што таа го прави. И generate.c, сите тоа го прави е или генерирање на случајни броеви или може да им даде на тоа семе, како подредено на тоа што е потребно, и таа ги генерира повеќе броеви. Значи има специфичен начин да се спроведување generate.c во кои вие само може да се направи еден куп на броеви за да ги тестираат вашите други методи за тоа. 

Значи, ако си сакал да, за На пример, ги тестираат вашите откритие, вие би сакале да се кандидира generate.c, генерира еден куп на броеви, а потоа се кандидира на вашиот помагачи функција. Вашиот помагачи функција е местото каде што си всушност физички пишување на код. И мислам на помагачи како библиотека датотека си пишува дека откритието е повик. И тоа во рок од helpers.c, ќе направите пребарување и подредување. 

А потоа ви се случува да во суштина само да ги стави сите заедно. Спец ќе ви кажам како да се стави тоа на командната линија. И ќе бидете во можност да се тестира дали или не вашиот сортирање и пребарување се работи. Кул. Веќе почна никого и се сретнал проблеми или прашања тие имаат право сега со ова? ВО РЕД. 

ПУБЛИКАТА: Чекај. Имам прашање. 

АНДИ Пенг: Да. 

ПУБЛИКАТА: Така почнав да прави пребарување линеарна во helpers.c и тоа не е навистина работат. Но потоа подоцна дознав ние само мора да го избришете и го направи бинарни пребарување. Така е важно, ако тоа не функционира? 

АНДИ Пенг: кратко одговорот е не. Но, бидејќи ние сме not-- ПУБЛИКАТА: Но, никој не е всушност проверка. АНДИ Пенг: Ние никогаш не сме случува да се види тоа. Но, веројатно ќе сакате да се направи сигурни дека вашето пребарување е работа. Затоа што ако вашиот линеарна пребарување не работи, тогаш шансите се вашиот бинарни пребарување не е оди на работа, како и. Затоа што имаат слични логика во двата од нив. И не, тоа не е важно. Така што само оние што ќе се сврти во се вид и бинарни пребарување. Је. 

И, исто така, многу деца беа се обидува да ги собере helpers.c. Вие не сте всушност е дозволено да го направи тоа, затоа што helpers.c не имаат главната функција. И за да можете само треба да биде всушност составувањето генерира и да се најде, бидејќи се најде повици helpers.c и функции во рамките на тоа. Така што го прави дебагирање болка во газот. Но, тоа е она што ние треба да направите. ПУБЛИКАТА: Може само да се направи сите, нели? АНДИ Пенг: Вие само може да направи на сите, како и, да. ВО РЕД. Така што тоа е во однос на она што на pset моли сите да го направите. Ако имате било какви прашања, се чувствувам Слободно можете да ме прашате по дел. Јас ќе бидам тука, како, на 20 минути. 

И да, за pset е навистина не е толку лош. Вие момци треба да биде во ред. Овие, само следете ги упатствата. Вид на имаат чувство на, логично, што треба да се случува и ќе биде во ред. Не се премногу исплашени. Има многу код веќе напишано таму. Не се премногу исплашени ако не се разбере она што сето тоа значи. Ако тоа е многу, тоа е сосема во ред. И да дојде до работното време. Ние ќе ви помогнеме да ја погледнете. 

ПУБЛИКАТА: Со дополнителна функции, ги гледаме оние нагоре? 

АНДИ Пенг: Да, тие се во кодот. Во играта на 15, од кои половината тоа е веќе напишано за вас. Па оние функции се веќе во кодот. Да. Во ред. Па, најдоброто од среќа. Тоа е одвратно ден. Па се надевам дека вие момци не се чувствуваат премногу лошо за останување во внатрешноста и кодирање.