[Мусиц плаиинг] 

Анди Пенг: Добродошли у недељу 3. члана. Хвала, момци, за све долази на овај раније време данас старт. Имамо леп, мало интимна група данас. Дакле, надам се да ћемо доћи до финиш, можда, раније, мало раније данас. Тако брзо, само су неки најаве за дневни ред данас. Пре него што почнемо, да смо да само прећи неколико кратких логистичка питања, псет питања, дебрифинга, такве ствари. А онда ћемо ронити право у. Ми ћемо користити за отклањање грешака под називом ГДБ да старт раскринкавање наш код, што Дејвид објашњено у предавању пре неки дан. Идемо преко четири врсте сорти. Идемо преко њих врло брзо јер су прилично интензивна. Али знам да су сви слајдови и изворни код су увек на мрежи. Дакле, слободно, на вашем увиду, да вратимо и да погледамо то. 

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

И на крају, по вашим секција повратне информације, заправо лево око 15 минута на крај само да одем логистику псет3, било каква питања, можда мало смерница, ако хоћете, пре него што почнемо програмирање. Дакле, хајде да покушамо да се кроз материјал прилично брзо. И онда можемо да проведемо неко време узимајући више питања за псет. ОК. 

Брзо, тако да само неколико најаве пре него што почнемо данас. Прво, велцоме то што то је преко два ваших псетс. Узео сам погледамо твој-- Да, идемо добили аплауз за то. Заправо, био сам стварно, заиста импресиониран. Ја оцењују први псет за вас прошле недеље и ви урадили невероватно. 

Стил је био на месту Поред неколико коментара. Побрините се да увек Коментаришући свој код. Али твоји псетс су били на месту. И кееп ит уп. И то је добро за гредер да видим да сте се ставља как много напора у вашем стилу и ваш дизајн у вашем коду да желимо да видите. Тако сам пролазио моје захвалности за остале Тас. 

Међутим постоје Неколико брифинге питања Само желим да одем да како би мој живот и много другог ТАС 'живи мало лакше. Прво сам приметио ово Недељу прошлост колико вас су ради цхецк50 на Ваш број пред вама поднесе? ОК. Дакле, свако треба да ради цхецк50, јер-- А Ве тајна-- ствари рун цхецк50 као део нашег исправности скрипте за тестирање свој код. Дакле, ако ваш код пропада цхецк50, по свој прилици, вероватно је да ће фаил нашу чек као добро. Понекад момци има праве одговоре. Као, у похлепан, неке од имате праве бројеве, само одштампате неке додатне ствари. И то екстра ствари заправо не чек, јер рачунар не знам шта је то тражио. И тако да ће само проћи кроз, види да ваш излаз не одговара оно што ми очекујемо одговор да буде, и означите је погрешно. 

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

Осим тога, псетс су због петком у подне. Мислим да је седам минута касног периода милост која ми вам дати. По Харвард време, они дозвољено да бити седам минута касније на све. Дакле, овде на Јејлу, ми ћемо придржавају и то. Али прилично, у 12:07, Ако ваш псет није у, то ће бити означен као касно. И тако док је означен као касни, ТА-- сам и даље ће бити оцењивање своје псетс. Дакле, и даље ћете видети разред појавити. Међутим, знамо да је на крај семестра, све заостале псетс ће само бити аутоматски зероед компјутер. 

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

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

ПУБЛИКА: Да ли сте Кажемо може пасти један од псетс? 

Анди Пенг: Да. Дакле, ту је девет псетс укупни у току семестра. А ако имате обим поинтс-- тако да обим је само, прилично, да ли покушавају Проблем, стављаш на време, ти показује да сте показали сте прочитали спец. То је прилично много простора. А ако се испуњавају Обим бодова, ми може пасти најниже један од пуног опсега. Дакле, то је у своју предност на завршити и покушајте сваки псет. 

Чак и ако нико од уплоад-- да раде, уплоад их све. И онда надам се моћи да да ти дам неке од тих тачака назад. Кул. Има ли још питања? Велики. 

Друго, канцеларија хоурс-- неколико брзе белешке о радног времена. Дакле, прво, доћи рано у недељу. Нико није икада у Радно време понедељком. Цхристабел дошао Радно време прошле ноћи. Да, Цхристабел. И шта имамо у канцеларији сати синоћ, Цхристабел? 

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

Анди Пенг: Дакле, то је у реду, имали смо сладолед на радног времена синоћ. Иако не могу да вам обећам да имаћемо сладолед на радног времена сваке недеље, шта могу да вам обећам је да ће бити знатно боље студент ТА однос. Као легално, то је као три према један. Док Упоредите то са Четвртак, имаш око 150 Заиста је нагласио децу и не сладолед. И то је само није продуктивно за кога. Дакле, поука ове приче је, доћи рано да радног времена и добрих ствари ће се десити. 

Такође, долази спреман да постављају питања. Знате? Без обзира шта Тас, ја Мислим, да је рекао, смо се неколико ученика који долазе у четвртак у, као, 10:50 не што прочитате спец биће као помози ми, помози ми. Нажалост, у том тренутку, ту је не можемо много да урадимо да ти помогнем. Зато молим те рано у недељу. Дођи рано за радног времена. Дођите спремни да постављају питања. Уверите се да вас, као студент, где су морате тако да буде ТАС могу вас водити заједно, што је оно што радно време Треба одвојити за. 

Друго, тако да знам професоре воле да нас изненади са тестовима. Имао сам професора оне као, јо, узгред буди речено, сећам се тог испит имате следећег понедељка. Да, нисам знао за тај испит. Зато ћу бити тај ТА да вас подсети све то квиз 0-- јер, знате, ми смо ЦС. Сада када смо урадили низова, добијате зашто је квиз 0, не Куиз 1, а? ОК. Ох, имам неке цхуцклес на тај један. ОК. 

Дакле, квиз 0 ће бити 14. октобар, ако ти си у понедељак-среда секције и 15. октобар ако сте у Уторак-Четвртак секција. Ово не важи за оне на Харварду ко-- Мислим да ће све бити узимајући своје квизове 14.. 

Тако да, следеће недеље, ако Дејвид, у предавању, иде, Да, тако о томе квиз следеће недеље, сви неће бити шокиран, јер сте дошли у одељку и знате да ваш Квиз 0 је за две недеље. А ми ћемо имати преглед сесије и све. Значи нема бриге око се уплашио за то. Сва питања пре-- било каквих питања на свим погледу логистичких питања, норматив, радно време, профили? Да. 

ПУБЛИКА: Дакле, квиз је ће бити у току предавања? 

Анди Пенг: Да. Тако квизу, мислим да је 60 минута додељена у том термину који сте управо ћу у амфитеатру. Дакле, не морате да дође у о, као, случајним 7:00 пм. Све је добро. Да. Кул. 

У реду. Тако ћемо увести концепт да вам ове недеље да Давид има већ некако од дотакао у предавању прошле недеље. То се зове ГДБ. А колико вас, док је у ток писања своје псетс, Приметио велики дугме на коме пише "Дебуг" на врху ИДЕ? ОК. Дакле, сада смо заиста ћу да ископају мистерија шта то дугме реално ради. И гарантујем ти, то је лепа, лепа ствар. 

Дакле, до сада, мислим дошло је до две ствари студенти су обично били радили када дебуггинг псетс. Један, они или додати у принтф () - тако да сваких неколико редова, они додају у принтф () - Ох, шта је ово променљива? Ох, шта је ово променљива сада-- а ви врста видите напредовање вашег кода док ради. Или други начин деца то је да они само напишите целу ствар и онда овако на крају. Надам се да ради. Ја вам гарантујем, ГДБ је боље од оба ова метода. Да. Тако ће ово бити ваш нови најбољи пријатељ. Зато што је то дивна ствар који визуелно приказује и шта је твој број ради у специфичној тачки као и шта све ваше варијабле носе, као што су њихове вредности, у том одређене тачке. И на овај начин, можете стварно сет бреакпоинт у вашем коду. Можете да покренете кроз линију по линију. И ГДБ ће само имати за ви, приказан за вас, ста све ваше варијабли су, шта раде, шта се дешава у коду. И на такав начин, то је много лакше да видим шта се дешава, уместо од принтф-инг или записивао своје изјаве. 

Тако ћемо урадити један пример касније. Дакле, ово изгледа помало апстрактно. Без бриге, урадићемо примере. И тако у суштини, три највећа, највише коришћене функције мораћете ГДБ су Даље, Степ преко, и корак у тастера. Идем над главом ту, у ствари, сада. 

Дакле, да ли ви све видите да или да зоом ин мало? У позадини, можете ли то видите? Да ли зоом ин? Само мало? OK kul. Ево га. ОК. 

Па ја имам, овде, моја имплементација за похлепан. И док многи од вас написао похлепни у вхиле петље форм-- да је савршено прихватљив начин да урадите То-- други начин да то урадите је да једноставно поделити у модуло. Јер, онда можете имати свој вредност и онда имати свој остатак. И онда једноставно не могу додати све заједно. Да ли логику онога што радим Овде има смисла за све, пре него што почнемо? Врста? Кул. Велики. То је прилично секси комад кода, рекао бих. Као што сам рекао, Дејвид, у предавања, после неког времена, сви ви ћете почети видети код као нешто што је прелепо. И понекад када видите лепа код, то је тако дивно осећање. 

Па ипак, док овај код је веома лепа, она не ради исправно. Дакле, хајде да цхецк50 на ово. Проверите 50 20-- ооп. 2? Да ли је то псет2? Да. О, псет1. ОК. Дакле, трчимо цхецк50. 

И као што ви можете да видите овде, то је зато што није неколико случајева. А за неке од вас, у Наравно да ради свој проблем сетова, ти си као, ах, зашто не ради. Зашто је то ради за неке Вредности али не и за друге? Па, ГДБ ће помоћи да схватите зашто ти улази нису радили. 

ОК. Па да видимо, један од чекови сам због недостатка цхецк50 је улаз вредност 0.41. Тако је тачан одговор који требало би да се је 4. Али уместо оно што ја штампање је 3-Н, што није тачно. Дакле, хајде да ради ручно, само уверите се да цхецк50 ради. Хајде да урадимо ./грееди. Упс, морам да похлепни. Ево га. Сада ./грееди. 

Колико дугује? Хајде да урадимо 0.41. И Да, видимо овде да је оутпуттинг 3 када је тачан одговор, у ствари, треба да буде 4. Дакле, хајде да уђе ГДБ и видимо како ћемо може ићи око причвршћивање овај проблем. 

Дакле, први корак у Увек отклањање грешака код је да поставите тачку прекида, или тачка у којој сте Желим рачунара или дебуггер да почнемо да тражимо у. Дакле, ако заиста не Знаш шта је твој проблем, Обично, типичан ствар коју желимо да урадите је да поставимо тачку прекида на главни. Дакле, ако ви можете видети ово црвено дугме тамо, Да, то ми је подешавању Бреакпоинт за главну функцију. Кликнем то. 

И онда могу да одем до мог дугме Дебуг. Ударио сам то дугме. Дозволите ми да зоом напоље ако могу. Ево га. Тако имамо овде, панел са десне стране. Жао ми је, момци у леђа, ви не видим јако добро. Али у суштини, све ово право панел ради је праћење и истакнути линија, која је линија кода да ли је рачунар тренутно ради, као и све ваше варијабли овде. 

Дакле, имаш центи, кованице, н све прогласио за различите ствари у овом тренутку. Без бриге, јер немамо ствари инитиализед их на било варијабли још. Дакле, у рачунару, компјутер је само видети, Ох, 32767 био последњи половни функција те меморије у мом компјутеру. И то је где центи тренутно је. Али не да када једном покренете код, оно треба да постане покренут. 

Дакле, идемо кроз, линију по линија, шта се овде дешава. ОК. Дакле, овде су три дугмад коју сам управо објаснио. Имате представе, или Рун функцију, дугме, имате Корак преко дугмета, а имате и корак у дугмету. И у суштини, све три их само проћи кроз кода и раде различите ствари. 

Тако типично, када отклањање грешака, не желимо да само притисните Плаи, јер Игра ће само покренути Ваш код на крају. А онда нећете заправо Знаш шта је твој проблем је осим ако нисте подесили више бреакпоинт. Ако сте поставили више Бреакпоинтс, само ће се аутоматски бежи од једног бреакпоинт, да следећи, да следећи. Али у овом случају имамо само да је један, зато што ми желе да раде свој пут од врха на доле до дна. Дакле, ми ћемо игнорисати то дугме сада за потребе овог програма. 

Тако Корак преко функције само кораци преко сваког линије и говори вам шта рачунар ради. Корак у функцију иде у стварни функцију то је на линију кода. Тако на пример, као принтф (), то је функција, зар не? Да сам хтео да се физички корак у принтф () функцију, Ја бих ићи у комаду Код где је написао и види иф () шта се тамо дешава. 

Али обично, претпостављамо да код које смо вам дати ради. Претпостављамо да принтф () ради. Претпостављамо да Затамњена () ради. Дакле, нема потребе да се корак у те функције. Али, ако постоји функције да се напише који желите да проверите шта се дешава, бисте желели да корак у ту функцију. 

Дакле, сада ми ћемо само на корак над овим делом кода. Па да видимо. О, штампа, "ох хаи, како много промена се дугује? " Ми не занима. Знамо да ради, тако да смо корак преко њега. 

Тако Н, који је наш пливајући да имамо инитиализед-- или децларед-- горе у врху, сада смо једнак то ГетФлоат (). Дакле, хајде да корак преко тога. И ми видимо на дно овде, програм ме је навело да улаз вредност. Дакле, хајде да унесете вредности желимо за тестирање овде, што је 0,41. Велики. 

Дакле, сада н-- урадите ви видите Овде, на боттом-- је сторед-- јер ми још увек није заокружена, то је складиштити у овом попут гиганта пловак који је 0,4099999996, што је довољно близу да наше сврхе, сада, на 0.41. И онда ћемо видети касније, како смо наставити гази преко програма, после овде, Н је постало заобљене и центи постао 41. Велики. Дакле, знамо да наше заокруживања ради. Знамо да имамо тачан број центи, тако да знамо да је то Не баш проблем. 

Дакле, ми настављамо степпинг у овој програму. Идемо овде. И тако након ове линије кода, можемо треба да знају колико четвртине имамо. Ми прекорачити. А видиш да не, у ствари, имам једну квартал јер смо одузме 25 из наше почетне вредности од 41. И имамо 16 остало за наше центи. 

Да ли сви разумеју како Програм се повлачи кроз и зашто центи је сада постао 16 и зашто, сада, ковани новац је постао 1? Да ли је свако следеће ту логику? Кул. Дакле, од овог тренутка, Радна програма, зар не? Знамо да ради тачно оно што је хтео. И нисмо у ствари треба да одштампате, каква је центи у овом тренутку, оно што је кованица у овом тренутку. 

Ми и даље пролази кроз програм. Искорачи. Кул. Идемо преко ситниш. Велики. Видимо да је узео Офф $ 0.10 за центи. И сада имамо два новчића. Тако је. 

Идемо преко пенија и видимо да ми је остало преко центи. Хмм, то је чудно. Овде у програму, ја сам требао да одузима моје паре. Можда ја једноставно није било раде то право линије. И нажалост, можете видети овде, јер знамо да смо степпинг преко линија 32 и 33, ту наш програм непрописно имао променљиве покренути. Дакле, можемо да погледамо и видимо, о, Ја одузимањем центи овде, али нисам стварно додајући да моје вредност новчића. Ја сам додао да центи. И не желим да додам да центи, желим да додам да кованица. Дакле, ако променимо то новца, имамо програм рада. Ја могу покренути цхецк50. Треба само да изађете из ГДБ права овде и затим поново покрените цхецк50. Само могу ово да урадим. Морам да похлепни. 0.41. И ево, то је штампање од правог одговора. 

Дакле, као ви можете да видите, ГДБ је стварно моћан алат када имамо толико код дешава и толико променљивих да је тешко за нас, као људски, да пратите. Рачунар, у ГДБ отклањање грешака, има способност да прате све. Знам, у висионаире, вероватно момци можда погодио неке грешке сегментације зато што су трчали изван граница свог поља. У примеру Цезара, који је управо оно што сам овде спроводи. 

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

ОК. Да. Уствари, ГДБ је требало да ми је речено је сегментација грешка тамо. Ја не знам шта се дешава тамо, али кад сам га водио, то је радио. Када покренете линија кода путем и ГДБ може одједном престати на тебе, иди и види ста је црвено грешка. То ће вам рећи, хеј, хвала имао сегментације грешку, што значи да сте покушали да приступите простор у низу који није постојао. Да. 

Дакле, у следећем проблему сет ове недеље, момци вероватно ће имати много променљиве лебди. Нећеш бити сигурни шта сви они значе у одређеном тренутку. Тако ГДБ ће заиста помоћи у откривању вас шта сви они су изједначавање и бити у стању да види да визуелно. Да ли је неко збуњен како ништа од тога ради? Кул. У реду. Дакле, након што смо да зарони у праву у су четири различита врсте сорти за ову недељу. Колико вас прво свега, пре него што почнемо, Прочитао сам цео спец за псет3? ОК. Ја сам поносан на вас. То је као половини класе, која је знатно више него прошли пут. 

Дакле, то је сјајно, јер кад говоримо о садржају у лецтуре-- или је, у сецтион-- Свиђа ми се да се односи много тога назад на оно што је псет и како желите да спровести то у псет. Дакле, ако дођете да прочитајте спец, то ће бити много лакше да разумете оно што ја говорим кад кажем, Ох хеј, ово може бити стварно добро место за спровођење ове врсте. Дакле, они од вас који су прочитали Спец знају да, као део вашег псет, ти ћеш морати да напише неку врсту врсту. Дакле, ово може бити од велике помоћи за многе од вас данас. 

Дакле, ми ћемо кренути са, у суштини, најједноставнији тип од врста, избор врста. Типичан алгоритам за како бих о томе је-- Дејвид прошла кроз ово све у предавање, тако да брзо прећи заједно овде-- је у суштини, ви има низ вредности. И онда наћи Најмања вредност мусиц а ви мењате ту вредност са први мусиц вредност. И онда само понављају са остатком ваше листе. 

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

Како избор врста би Рад је да је прво би пролазе кроз целини од неразврстан низа. То би издвојити најмању вредност. У овом случају, 3, зар не Сада је најмањи. Постаје до 5. Не, 5 није већа тхан-- или је, није мање тхан-- 3. Дакле, минимална вредност је увек 3. И онда дођете до 2. Рачунар види, ох 2 је мање од 3. 2 сада мора бити минимална вредност. И тако 2 свопови са тог првог вредности. 

Дакле, после једном пролазу, ми заиста видимо да су 2 и 3 се замењивати. И ми ћемо само да наставимо да радимо то опет са остатком низа. Дакле, ми ћемо само пролазе кроз последња четири индекси низа. Видећемо да је 3 следећа минимална вредност. Дакле, идемо да замени то са 4. И онда ћемо само да задржи пролази кроз све, на крају, ви дођете до сортираном низу у којој 2, 3, 4, 5, и 6 су сви сортирани. Да ли сви разумеју логику како избор врста ради? 

Само има неку врсту минималне вредност. Ти праћење шта је то. И кад год га наћи, ти замени са првим вредност во арраи-- или, није први валуе-- следећи вредност у низу. Кул. 

Дакле, као што вама врста Видела из кратак поглед, ћемо псеудокоду ово. Дакле, ако сте у леђа желите да формирају групу, сви за столом може формирати мало партнера, идем да вам дам као три минута само говорити кроз логика, на енглеском језику, како бисмо могли да спроведу Псеудокод да напише избор врсту. А ту је и бомбоне. Молимо вас да се попнем и да слаткише. Ако сте у леђима и желите Цанди, могу бацити бомбоне на тебе. Заправо, да ли ти- цоол. Ох, извините. ОК. 

Дакле, ако желимо да, као класа, писање Псеудокод колико би се могло приступити Овај проблем, само слободно. Само идем около и, како, питајте групе за следећу линију Шта би требало да радимо. Дакле, ако ви желите да покренете искључен, шта је прва ствар да урадите када покушавате да спроведе начин да реши овај програм да селективно сортирали листу? Хајде да претпоставимо имају низ, у реду? 

ПУБЛИКА: Ви желите да направите неки врста [неразумљиво] које сте пролази кроз читав свој низ. 

Анди Пенг: Тако је. Тако ћеш желети да поновити кроз сваки простор, зар не? Тако велики. Ако хоћете да ми дају поред лине-- да, у леђа. 

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

Анди Пенг: Идемо. Дакле, желимо да прођу и проверите да видим шта је минимална вредност, зар не? Ја ћу да скратим то "мин". Шта ви желите да урадите после сте пронашли минималну вредност? 

ПУБЛИКА: [неразумљиво] Анди Пенг: Дакле, ви хтети да укључите га са првим тог низа, jel tako? То је почетак, ја ћу да кажем. У реду. Дакле, сада када сте заменили први један, шта желите да урадите после тога? Дакле, сада знамо да је ова овде мора да је најмања вредност, зар не? Онда имате додатни одмор од низа који је мусиц. Дакле, шта желите да урадите овде, ако вас момци желе да ми дају следећу линију? ПУБЛИКА: Онда желите да поновити кроз остатак низа. Анди Пенг: Да. И тако шта итератинг кроз врста подразумева вероватно ћемо морати? Који тип од-- 

ПУБЛИКА: О, додатна променљива? Анди Пенг: Вероватно други за петљу, зар не? Дакле, вероватно ћемо хтети да прелазили тхроугх-- сјајно. А онда ћеш да се вратим и Вероватно проверите поново минимум, jel tako? И ти ћеш понављати ово, јер су петље тек тако да настави са радом, зар не? 

Дакле, као ви можете да видите, само општи Псеудокод како желимо овај програм да гледам. Ово Итерате овде, шта радимо обично треба да напише у нашем коду ако желимо да поновити путем Арраи, који тип структуре? Мислим да је Цхристабел већ раније рекао. 

ПУБЛИКА: А за петљу. 

Анди Пенг: А за петљу? Baš tako. Дакле, ово је вероватно Биће то за петљу. Шта је провера овде да значи? Обично, ако желите да проверите ако је нешто нешто елсе-- 

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

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

ПУБЛИКА: Још једна фор петља. 

Анди Пенг: --анотхер за петљу, тачно. Дакле, ако гледамо ово тачно, ми видим да смо вероватно Требаће угњеждени за петљу са условни исказ у ту и онда стварни део кода који је да мењате вредности. Зато сам само генерално написано Псеудокод код овде. И онда ми заправо догађа физички, као класа, покушати да ово данас спроводе. Вратимо се у овом ИДЕ. 

Uh Oh. Зашто је то није-- то је то. ОК. Жао нам је, дозволите ми да покушам да зумира мало више. Ево га. Све што радим овде је сам створио програм под називом "Избор / сорт.ц." Ја сам створио низ од девет вредности, 4, 8, 2, 1, 6, 9, 7, 5, 3. Тренутно, као што можете види, они су нередоследна. Н ће бити број који каже да износ од вредности имате у низу. У том случају, имамо девет вредности. И управо имам за петљу овде који исписује на неразврстан низ. 

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

Дакле, имамо нашу Псеудокод овде. Да ли неко жели да-- Ја сам само ићи тражити волунтеерс-- Реци ми тачно шта да куцате ако желимо да, прво, само поновити кроз почетку овог низа? Која је линија кода сам Вероватно ће требати овде? 

ПУБЛИКА: [неразумљиво] 

Анди Пенг: Да, осећам слободан да-- Жао нам је, не морају да стоје их-- осећај Слободно Раисе Иоур Воице мало. 

ПУБЛИКА: За инт и једнако 0-- 

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

ПУБЛИКА: Ја је мање од дужине низа. 

Анди Пенг: Зато водите смета овдје, јер смо ми немају функцију која нам говори дужина низа, Већ имамо вредност која чува то. Jel tako? Још једна ствар коју треба имати ин минд-- у низу од девет вредности, које су индекси? Рецимо овај низ је 0 до 3. Видиш да је последњи индекс је заправо 3. Није 4, иако постоји Четири вредности у низу. 

Дакле овде, морамо бити врло опрезни од чега наше услов за дужину Biće. 

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

Анди Пенг: То је Стварно добро питање. Дакле, да. Али, такође, начин на који смо спровођење провере право, морате да упоредите две вредности. Дакле, ви заправо желите да оставите "да" празна. Јер, ако упоредите ово, ти не идеш има све после тога за поређење, зар не? Да. Тако и ++. Додајмо наше заграде у. Упс. Велики. Дакле, имамо почетак нашег спољњег петље. Тако да сада вероватно желите да створити променљиву за чување стаза од најмањих вредности, зар не? Да ли неко жели да ми дају линија кода који би то урадио? Шта нам је потребно да идемо да желите да сачувате нешто? 

Jel tako. Можда боље име за то би бити-- "темп" потпуно воркс-- можда више пригодно назван би, ако желимо најмању валуе-- 

ПУБЛИКА: мин. Анди Пенг: мин, идемо. мин би било добро. И ево, шта радимо Желим да га иницијализирати да? Ово је мало незгодно. Јер, управо сада у почетком овог низа, нисте гледали било шта, зар не? Па шта, аутоматски, ако ми смо само он и једнако 0, шта желимо да се покрене наша прва вредност на минимум? ПУБЛИКА: Ја. Анди Пенг: Ја тачно. Цхристабел је, зашто желимо то инитиализе до и? 

ПУБЛИКА: Јер, па, почињемо са 0. Зато што немамо ништа да упореде да да, минимални ће завршити као 0. 

Анди Пенг: Управо тако. Дакле, она је потпуно у праву. Зато што немамо заправо погледао шта још, ми не знамо шта је наш минимум је вредност. Желимо да само иницијализирати да И, што је, тренутно, је овде. И као што смо и даље померите овај низ, видећемо да је, са сваким Додатни додавање, ја повећава. И тако у том тренутку, Ја ће вероватно да желе да буду минимални, јер ће бити било шта је почетак неразврстан низа. Кул. 

Тако да сада желите да додате фор петљу овде је то ће поновити кроз мусиц, односно остатак ове низа. Да ли неко жели да ми дају линија кода који би то урадио? Хинт-- шта нам је потребно овде доле? Шта ће се ићи у ово петљу? Да. ПУБЛИКА: Тако да би желео да имају другачији цео број, јер ми пролази кроз остатак од низа уместо И, па можда ј. 

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

ПУБЛИКА: Тако бих ја био, плус 1, јер сте са почетком у наредном вредности. А онда у енд-- Дакле, опет, ј мање од н минус 1, а затим ј ++. Анди Пенг: Одлично. 

А онда овде, ми ћемо желети да проверите да ли нам је испуњен услов, jel tako? Зато што желите да промените минималну вредност ако је стварно мањи од оног ви га пореде, зар не? Дакле, шта ћемо да желим овде? Проверите да види. Коју врсту изјава се вероватно дешава Ти желите да користите ако желите да проверите нешто? 

ПУБЛИКА Ан ако изјави. 

Анди Пенг Ан ако изјава. Дакле, ако-- и шта ће бити услов који желимо унутра нашег иф? 

ПУБЛИКА: Ако је вредност ј је мања од вредности Ја 

Анди Пенг: Управо тако. Дакле, ако-- тако да низ се зове "низ." Велики. Дакле, ако арраи-- шта је то? Поновите. 

ПУБЛИКА: Ако низ-ј мање од низ-ја, онда ће променити мин. Дакле, минимална би било Ј. 

Анди Пенг: Има ли то смисла? ОК. А сада овде, ми заправо Желим да спроведе свап, зар не? Тако се сећате, у предавању, Давид, када Он је покушавао да до-- оно што је заменити то-- сок од поморанџе и милк-- 

ПУБЛИКА: То је одвратно. 

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

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

Анди Пенг: Привремена променљива. Па хајде да урадимо инт темп. Видите, то би бити бољи време да-- вау, шта је то? ОК. Дакле, ово би био бољи Време је да име променљиве "Темп". Па хајде да урадимо инт темп. Шта ћемо сет темп једнак довде? ПУБЛИКА: мин Анди Пенг: Мало је незгодно. То заправо није битно на крају. Није битно шта би да изаберете да мењате у док правите сигуран да си праћење шта замене. 

ПУБЛИКА: Могло би да буде низ-ја. 

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

Анди Пенг: У реду. Дакле, хајде да то и видим ако се иде на посао. Где је то дешава? Ох, то је проблем. Видите, он лине 40 смо Покушавам да користите арраи-ј? Али одакле Ј постоје само у? 

ПУБЛИКА: У фор петље. Анди Пенг: Тако је. Дакле, шта ћемо морати да урадимо? 

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

Анди Пенг: Момци, пробајте да погледате Хајде да види, шта можемо да урадимо нешто овде? 

ПУБЛИКА: У реду. Дакле, ако је минимална није једнако ј-- па ако је минимална још и-- онда не би морали да мењате. 

Анди Пенг: Да ли то сам равноправни? Шта желите да кажем? 

ПУБЛИКА: Или да, ако Минимална не једнак И, да. Анди Пенг: У реду. Па то решава, врста, наши проблеми. Али то и даље не решава проблем шта се дешава ако ј-- од ј не постоји изван ње, што да ли желимо да радимо са њим? Објавите га напољу? Хајде да пробамо ово ради. Uh Oh. Наша врста не ради. 

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

Зато што већ знамо да ове линије, 15 до 22, су воркинг-- јер све што радим је Само итератинг кроз и принтинг-- Ја могу ићи напријед и да прескочите. Почнимо на линији 25. Ооп, дозволите ми да се отарасим тога. 

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

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

И тако наставимо степпинг кроз. Наш минимални једнак 0, што ми такође желимо да буде. И онда ући у нашу секунди за петља, ако низ-ј мање од низа-И, која није. Дакле, да ли сте видели како да прескочили то? 

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

Да, па можемо да излазак из дебуггер овде. Дакле, хајде да погледамо наш псеудокоду. За-- ћемо крећу Ја износи 0. Ми ћемо ићи до н минус 1. Хајде да проверимо, да ли ми имамо то право? Да, то је у реду. 

Дакле унутра, ми смо да створи минимална вредност и подесите да једнак и. Да ли смо то урадили? Да, урадио. Сада у нашој унутрашњи за петљу, ми смо урадити ј једнака сам до н минус 1. Да ли смо то урадили? Заиста, то смо урадили. 

Па ипак, шта ми овде пореде? 

ПУБЛИКА: Ј плус 1. Анди Пенг: Управо тако. А онда ћеш да желите да поставите Ваша минимална једнака ј плус 1, као. Отишао сам кроз то јако брзо. Да ли ви разумете Зато је Ј плус 1? ОК. 

Дакле, по вашем низу, у ваша прва пролазе кроз, Ваш за петље, за инт И једнако 0, хајде да Претпостављам да још није променила. Имамо низ, у потпуности, само четири унсортед елементи, зар не? Дакле, желимо да покрене сам једнак 0. И ја се иде само да пролазе кроз ову петљу. И тако у првом пролазу, идемо да покрене променљиву названу "МИН" да сам и ја једнако, јер немамо минималну вредност. Дакле, то је тренутно једнака 0, као добро. А онда ћемо да прођем. И ми желимо да опет поновити. Сада када смо пронашли оно што наш минимум је, желимо да поновити путем поново да видим да ли је у односу, зар не? Тако ј овде, иде на једнаку И који је 0. А онда, ако низ Ј плус ја, који је онај који је поред готово, као мање него што ваш тренутни минимум вредност, желите да мењате. 

Дакле, хајде да кажем да смо има, као, 2, 5, 1, 8. Сада, ја је једнак 0 и ј је једнак 0. И то је наша минимална вредност. Ако арраи-Ј плус Ја тако да ако један То је након оног што гледамо је већи од оног пре њега, то ће постати минимум. 

Дакле овде видимо да 5 није мање од тога. Дакле, то ће бити не 5. Видимо да је мање од 1 2, зар не? Дакле, сада знамо да је наш минимум је ће бити вредност индекса на 0, 1, 2. Да? И онда кад дођеш овде, можете заменити исправним вредностима. 

Дакле, када су момци само имају ј пре, ниси гледао у једном након тога. Ви сте гледали исте вредности, која Због тога једноставно не ради ништа. Да ли то има смисла за све, Зато нам је потребна да плус 1 тамо? ОК. Сада ћемо само пролазе кроз то да Сигурно је остатак код је тачна. Зашто се то дешава? Ах, то је минимална овде. Ми смо у односу на погрешну вредност. О, не. 

Ох, да, овде смо били замјене погрешне вредности као добро. Зато што смо гледали и и ј. То су они за које смо проверавали. Ми заправо желе да мењате минимална, тренутна минимална, са свим што она ван је. И као што ви можете видети доле Овде имамо сортирану низ. Само су имали везе са чињеница да када смо Провера Вредности су нас пореде, нисмо гледали правим вредностима. Тражили смо на истом једном овде, не заправо замене. Морате да погледате један поред до њега и онда можете заменити. Дакле, то је оно што је било некако мучи наш код раније. И шта сам урадио овде је све Дебагер могао да уради за вас Управо сам то урадио на плоча, јер је лакше да видим уместо да да бисте увећали на дебагером. Да ли то има смисла свима? Кул. 

У реду. Можемо прећи на говори о асимптотско нотација, која је само фенси начин да се каже Рунтимес свих ових врста. Тако да знам Давида, у предавању, дотакао рунтимес. И он је кроз читав формули како да израчунају рунтимес. Без бриге о томе. Ако сте заиста занима како то ради, слободно да разговара са мном након делу. Можемо да ходају кроз формуле заједно. Али сви ви морате да стварно Знам само да је н квадрат преко 2 је иста ствар као н на квадрат. Зато што у највећем броју, експонент, расте највише. И тако за наше потребе, све нам је стало је да гигант број који расте. 

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

И врста је такође мало јединствен у смислу да није битно да ли ови Вредности су већ у реду. То је и даље тећи кроз ионако. Рецимо да је ово 1, 2, 3, 4. Без обзира да ли или није било у поредак, ипак би побегао кроз и још увек проверава минималну вредност. То би учинили исти број чекова сваки пут, чак и ако није заправо ништа дирати. 

Дакле, у том случају, најбоље и најгоре Рунтимес су заправо еквивалент. Тако је очекивани рунтиме од селекције врсте, које смо одређивања симболом оф тета, тета, у овом случају, ће такође бити н квадрат. Сва три од њих ће се н на квадрат. Да ли је свима јасно зашто извршни је н квадрат? 

У реду. Дакле, само ћу брзо покретање кроз осталих врста. Алгоритам за балон сорт-- запамтите, ово је био први Дејвид отишао у предавању. У суштини, ви корак кроз цео списак а ти си само свап-- Упореди две у исто време. А ако неко је већи, него ти их само замијенити. Дакле, ако су већи, требало би да замените. Имам званични овде. 

Дакле, хајде да кажете да сте имали 8, 6, 4, 2. Ти би упоредити 8 и 6. Ти би треба да их замене. Ти би упоредити 8 и 4. Ти би треба да их замене. Ако морате да замените је 8 и је 2, промените их као добро. Дакле, у том смислу, можете видети, одиграва током дугог временског периода, како вредности врста балона на крајеви, због чега га зовемо балон врста. 

Само би кроз поново наш други пролаз, а наш трећи додавање, и наш четврти додавање. У суштини, мехур врста само ради док не правити више свопови. Дакле, у том смислу, ово је само општи Псеудокод за то. Без бриге, то ће све бити онлине. Не морамо да заправо ићи преко тога. 

Само инитиализе контра варијабла која почиње у 0. И ми смо прелазили преко целог низа. А ако неко вредност је- ако је ово вредност већа од те вриједности, ћеш да их замене. И онда ти си само да настави. И ти ћеш да рачунају. И само ћеш да наставиш да радиш ово док је бројач већа од 0, што значи да сваки пут морате да мењате, знате ли желиш да идеш назад и проверите поново. Ви желите да задржите проверу док не знате да не морају више да мењате. 

Дакле, шта су најбоље и најгоре Случај Рунтимес за буббле сорт? И хинт-- ово је заправо другачији од одабира врсте у смислу да су ова два одговора нису исти. Размислите о томе шта ће се десити у случај ако је већ поредани. И размислите о томе шта ће се десити ако је У случају у којим није сортиране. И можете некако покренути кроз зашто је то дешава. Даћу ти момци, као, 30 секунди да размислим о томе. 

ОК. Да ли неко има нагађати шта у најгорем случају Рунтиме од балон врсте је? Да. 

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

Анди Пенг: Да, тако Потпуно си у праву. И ово је случај у којем ваш одговор је заправо сложенија од оне треба да дају. Тако да ће рун-- сам ће избрисати све ово овде. Јесу ли сви добро? Могу ли обрисати ово? ОК. Ти ћеш проћи кроз н пута први пут, зар не? И они ће трајати до Н минус 1 други пут, зар не? А онда ћеш задржати иде н моја 2, и тако даље. Дејвид је то урадио на предавању, где ако сте додали све оне вредности, добијате нешто што је као-- Да-- преко 2, који у суштини само смањује до н на квадрат. Ти ћеш добити чудно фракција унутра. И тако, само знам да Н квадрат увек има предност у односу на фракције. И тако у овом случају, најгори Рунтиме би се н на квадрат. Ако је у опадајућем поредак, мислим, ти морати да свап сваки пут. 

Шта би било, потенцијално, у најбољем случају рунтиме? Рецимо, ако је већ била листа како, шта би рунтиме бити? 

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

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

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

Онда знамо да је Остала четворица су мусиц. Идемо кроз и видимо ту вредност. Хајде да се вратимо. Видиш ону вредност 5? Узимамо погледам. Ми смо га упоредимо са 3. Знамо да је већи од 3, тако да знамо да је то решено. Дакле, сада знамо да се прва два су поредани а последња три нису. 

Ми погледамо 2. Први смо да проверимо са 5. Да ли је то мање од 5? То није. Дакле, морамо да гледа. Онда проверите 2 офф 3. Да ли је то мање од? Ne. Дакле, знате на 2 мора да се убаци у предњем и 3 и 5 оба морају бити истиснути. Да ли ово опет са 6 и 4. И управо смо стално проверава у суштини, где смо само да проверим, проверите, проверите. И док је у праву положај, смо некако само убаците га у исправан положај, који је место где име је дошао. 

Дакле, то је само алгоритам, Псеудокод по себи, некако, како бисмо спровести уметање врста. Псеудокод је овде. Све је на мрежи. Без бриге, ако сте ви момци Покушавам да копирате ово. Дакле, још једном, исто оно куестион-- би било најбоље и најгоре рунтимес за убацивање врсту? То је врло слично на последње питање. Даћу ти момци, као, 30 секунди да мислим о томе као добро. 

У реду Да ли неко жели да дај ми најгору рунтиме? Да. 

ПУБЛИКА н на квадрат. 

Анди Пенг: То је н квадрат. А зашто је то Н квадрат? 

ПУБЛИКА: Јер у обрнутим редоследом, имате проћи кроз н пута н који је- Анди Пенг: Да, управо тако. Дакле, иста ствар као у балон врсте. Ако је ово листа у опадајућем редоследу, ти си морати да проверим прво једном. И онда са сваким додатна вредност, ти си ће морати да проверим против свака појединачна вредност, зар не? И тако све заједно, ти ћеш направити ан н пасс пута другу н прође, која је н квадрат. Шта најбољем случају? Да. 

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

Анди Пенг: Па, у непосредној близини. Одговор је заправо бр. Јер, док прва је поредани, не могу да га стварно-- смо среће, у тај пример, да 2 Десило се да је најмањи број. Али то неће увек бити случај. Ако се 2 већ сортирана на почетку али изгледаш и ту је 1 овде, од 1 ће то бумп. И то ће се завршити до које налетео ионако. 

Дакле, у најбољем случају, то је заправо само ће бити бр. Уколико имате 1, 2, 3, 4, 5, 6, 7, 8, ти си ће трајати до Једном је цела листа да проверите да ли је све у реду. Да ли је свима јасно о вођењу пута селекције, као? Знам да ћу кроз ово врло брзо. Али, само знам да ако знате општи појмови, требало би да буде добар. ОК. Дакле, ја ћу вам дати момци можда, као, минут да разговарам са својим комшијама на шта су само неки од главних разлика између ових типова сорти. Идемо преко тога ускоро. ПУБЛИКА: Ох, у реду. Анди Пенг: Да. ОК. Супер, хајде да се састанемо као класа. ОК. Дакле, то је нека врста отворено питање у смислу да има пуно одговора на њих. И ми ћемо ићи преко неке од њих кратко. Само сам хтео да ти момци размишљам о томе шта разликовати све три врсте сорти. И чуо сам, такође, велики куестион-- шта стапања врста уради? Велики питање, јер је то шта ћемо покрива следеће. 

Дакле, спајање врста је једна врста која функционише веома различито од других врста. Као момци могу видим-- нисам Дејвид уради то демо где је имао сву цоол звуци како спојити виде врста ран, као, бескрајно брже него друге две врсте? ОК. Дакле, то је зато што стапања Сорт спроводи да поделе па владај концепт који смо говорио о много у предавању. У том смислу, да смо желели да радимо паметније, не теже, када поделите и освоји проблеме, и разбити их доле, а затим их заједно, добре ствари увек дешавају. 

Дакле, начин на који спојити Сорт суштини ради је да дели мусиц низ на пола. И онда има две половине низова. И то само сортира те две половине. Само држи подели на пола, у пола, на пола док се све не поредани и онда рекурсивно ставља све заједно. 

Дакле, то је стварно апстрактно. Дакле, ово је само мало псеудокоду. Да ли то смисла у начин на који то ради? Дакле, хајде да кажем ли имате низ од н елемената, зар не? Ако је н мање од 2, можете се вратити. Зато што знамо да ако постоји Само једна ствар, она мора бити сортирани. Иначе, сортирање левој половини, и онда сортирање десној половини, и онда спојити. 

Дакле, иако то изгледа стварно лако, у стварности, мислећи о томе је врста тешко. Јер си као, Па, то је некако ради на себи. Jel tako? То је ради на себи. Дакле, у том смислу, Дејвид додирнуо по рекурзије у класи. И то је концепт ћемо разговарати о више. То је да ово, ове две линије овде, у ствари је само програм то говори да се ради са различитим улаз. Дакле, уместо да се ради са укупност н елемената, можете га сломити доле у Лева половина и десна половина а затим га поново покрените. 

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

Рецимо да имамо низ, шест елементи, 3, 5, 2, 6, 4, 1, нису сортиране. Добро, има пуно на овој страници. Дакле, ако ви можете да погледамо фирст степ хере, 3, 5, 2, 6, 4, 1, можете га поделите на пола. Имате 3, 5, 2, 6, 4, 1. Знате да су вам арен'т-- не знам да ли сортиране или не, тако да стално разбијање их, на пола, на пола, на пола, све док на крају, имате само једног елемента. И један елемент је увек поредани, зар не? 

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

Не треба ни да погледајте 3. и групи 5. Па знате 1 иде тамо. Онда основи одсећи за 1. То је, као, мртва за нас. Онда имамо само 2, 3, 5, а затим 4 и 6. И онда знате да вас упореди 4 и 2, ох, 2 треба да иде тамо. Дакле, плоп на 2 Довн, ти га одсећи. Дакле, онда само треба да 3 а 5 у 4 и 6. А ви само наставите сецкање га док их у низу. 

ПУБЛИКА: Дакле, ви сте само увек упоређивањем [неразумљиво]? 

Анди Пенг: Управо тако. Дакле, у том смислу, ти си само у односу, у суштини, један број у односу на други број. И зато знате да је то решено, те не морам да гледам кроз све бројеве. Потребно је само да погледате први. И онда само да бућ их, јер знаш они припадају тамо где треба да припадају. Да. Добро питање. 

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

ОК. Тако Давид и отишао ово предавање. Који су најбољи случај Рунтимес, најгори случај Рунтимес, и очекивани Рунтимес од стапања врсте? Пар секунди да размислим. Ово је прилично тешко, али некако интуитиван, ако мислите о томе. У реду. 

ПУБЛИКА: Да ли је најгори случај н лог н? Анди Пенг: Управо тако. А зашто је то н лог н. 

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

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

И тако у најбољем случају и најгори случај и очекује се све н лог н. Такође је као друга врста. То је као избор врсте у смислу да Није битно шта је ваш Списак је, само иде да раде исту ствар сваки пут. ОК. Дакле, као ви можете видети, иако Врсте које смо отишли ​​тхроугх-- н квадрат, то није врло ефикасан. Па чак и овај број дневника н Не најефикаснији. Ако сте радознали, Постоји врста механизми које су тако ефикасна да су Скоро у суштини стан у рунтиме. 

Имаш неки лог Н-ове. Имаш неки лог лог н 'с. Ми не дотичу њих у овој класи сада. Али ако ви момци су радознали, слободно гоогле, шта је Механизми Најефикаснији сортирање. Не знам, постоје неки заиста фунни оне, као-- је једна заиста фунни оне које људи чине. И питате се како су икад размишљала о томе. Дакле, гоогле, ако имате неке резервне време, на, шта су неке чудне начине да људи, као и ефикасни ваис-- људи били у стању да спроведе врсте. ОК. И овде је само згодно мало графикон. Знам све о теби, пре тог квиза 0, ће бити у вашој соби, вероватно покушавајући да запамти то. Дакле, то је лепо тамо за вас. Само не заборавите логику да маде-- Зато те бројке су се јавља. Ако сте увек изгубљен, само да Сигурно знате шта су врсте су. И можете покренути кроз им ин иоур минд да схватим зашто они одговори су ти одговори. 

У реду. Дакле, идемо да се креће на крају, у трагању. Јер као оне од вас који су прочитали псет, претраживање је такође део Проблем ове недеље поставља. Ти ћеш бити затражено да спроведе две врсте претраживања. Један је линеарна за претрагу и један је бинарна претрага. 

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

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

Дакле, начин на који бисмо отићи о имплементацију бинарни претрагу је, ако смо имали низ, индек 0 до 6, седам елемената, можемо погледати у средини, ригхт-- Жао ми је, ако наше питање фирст-- ако желимо да поставим питање, да ли Низ садрже елемент 7, Очигледно, као људи, и имају тако мали низ, то је лако за нас пристати. Али начин на који да се спроведе бинарни претрага би било да погледате у средини. 

Знамо да је индекс 3 је средњи, јер смо ми Знам да има седам елемената. Шта 7 подељено са 2? Можете одсећи да Ектра 1. Имате 3 у средини. Тако је низ од 3 једнака 7? То није, зар не? Али можемо да урадимо неколико чекова. Да ли је низ од 3 мање од 7 или је низ од 3 већи од 7? 

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

Дакле, сада гледамо средњи онога што је остало. То индекса 5. Ми опет исто чек и видимо да је то мањи. Дакле, гледамо лево од тога. И онда видимо тај чек. Да ли је низ вредност на Индекс 4 једнак 7? To je. Тако да могу да се врате тачно, јер смо пронашли вредност у нашој листи. Да ли је начин на који сам прошао то смисла свима? ОК. Даћу ти момци можда, као, три, четири минута да схватим како псеудокоду ово. 

Замислите сам вас питао написати Функција се зове претрага () који се вратио вредност, Логичка вредност, то истина или фалсе-- слично, истина ако пронашао вредност, фалсе ако ниси. И онда си усвојен у вредности ви су у потрази за у вредности које је арраи-- ох, дефинитивно ставио да је на погрешном месту. ОК. У сваком случају, то би требало имати био десно од вредности. А онда инт н је број елемената у том низу. Како би идете о покушају да псеудокоду тај проблем у? Даћу ти момци попут три минута да то уради. Не, мислим да има само-- Да, постоји један прави овде. ПУБЛИКА: Могу ли? Анди Пенг: Да, имам те. Да ли је то радни? OK kul. 

ОК. У реду момци, ми смо да га обузда. ОК. Дакле, претпоставимо да имамо ово дивно мало низ са н вредности у њему. Нисам нацртати линије. Али, како да идемо о Покушавам да пишем ово? Да ли неко жели да дај ми прву линију? Ако желите да ми дају Прва линија овог псеудокоду. 

ПУБЛИКА: [неразумљиво] ПУБЛИКА: Ти би желите да прелазили тхроугх-- ПУБЛИКА: Само још један за петљу? ПУБЛИКА: --Фор. 

Анди Пенг: Дакле, ова је мало незгодно. Мислите о-- желите да настави са радом ове петље изнова и изнова до када? 

ПУБЛИКА: До [неразумљиво] вредност једнака том вредношћу. Анди Пенг: Управо тако. Тако да заиста могу само врите-- цак моземо да поједностави више. Ми само можемо направити вхиле петље, зар не? Дакле, можете само да имате лооп-- знамо да је то време. Али за сада, идем то саи "лооп" - кроз шта? Петља док-- шта је наш крај стање? Мислим да сам чуо. Чуо сам да га је неко рекао. 

Публика: Вредности једнака средину. Анди Пенг: Понови. ПУБЛИКА: Или, док се вредност сте у потрази јер једнак је средња вредност. 

Анди Пенг: Шта ако није тамо? Шта ако је вредност коју тражите за заправо није у овом низу? ПУБЛИКА: Враћате 1. 

Анди Пенг: Али шта желимо да петља док ако имамо стање? Да. 

ПУБЛИКА: Док постоји само једна вредност? Анди Пенг: Иоу цан петља док-- тако да знате да сте ће имати максималну вредност, зар не? И знаш да ћеш да има мин вредност, зар не? Јер, такође, да је нешто Заборавио сам да кажем пре, то нешто што је критички о бинарном сеарцх је да је ваш низ већ поредани. Зато што не постоји начин да се то ово ако су само случајне вредности. Не знам да ли је неко већи од другог, зар не? 

Дакле, ви знате да је ваш мак и Ваши минута овде, зар не? Ако ћеш да се подешавање Ваш максимално у вашим минута и мид-- хајде да претпоставимо ваше Средином вредност је у праву овде- ћеш основи петља док ти минимум отприлике исто као твој мак, десно или Ако ваш макс није исто као твој мин. Jel tako? Јер када се то деси, ви знате да ви сте коначно погодио исту вредност. Дакле, желите да петље до вашег мин мања или једнака да-- Д, не мање од или једнако, други начин ароунд-- мак је. 

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

ПУБЛИКА: Да. 

Анди Пенг: У реду. Дакле, ако је то услов за нашу петље, шта желимо унутар ове петље? Шта ћемо да жели да уради? Тако сада, имамо А Мак и мин, зар не, Вероватно је направљена овде негде. Ми ћемо вероватно желите да пронађе средину, зар не? Како ћемо бити у могућности да пронађе средину? Шта је матхематицал-- ПУБЛИКА: Мак Плус мин подељене 2. Анди Пенг: Управо тако. Да ли то има смисла? А ви момци видим зашто није само Користи, зашто смо ово урадили уместо да ради само н подељено са 2? То је зато што је н вредност који ће остати исти. Jel tako? Али, као што смо прилагодили наше минимум и максималне вредности, они ће се променити. И као резултат, нашег средњег ће да се промени. Зато желимо да радим ово овде. ОК. 

А онда, сада када смо нашли оур-- да. 

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

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

ПУБЛИКА: Желимо да упоредите то другом. Анди Пенг: Управо тако. Значи идеш за поређење Средином на вредност, зар не? А шта то реци нам када упоредимо? Шта желимо да после тога? 

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

ПУБЛИКА: Ваш максимум. Анди Пенг: Да. И онда сте тек тако да задржи петље, зар не? Јер сада, после једне итерације кроз, имаш мак овде. А онда можете поново израчунати на мид. А онда можете упоредити. А ти ћеш да наставиш све док минута и макес су у суштини обједињених. И то је када знате да ви сте погодио крај. И било да сте га нашли или нисте у том тренутку. 

Да ли то смисла свима? ОК. Ово је веома важно, јер ћеш имати написати ово у код вечерас. Али ви имате прилично добар осећај шта треба да радите, што је добро. ОК. Дакле, имамо око седам минута напустио секцију. Тако ћемо да разговарамо о ово псет да ћемо радити. Дакле, псет је подељен на два дела. Прво полувреме укључује спровођење откриће у којима пишете линеарни претраге, бинарни претрага и алгоритам за сортирање. 

Дакле, ово је први Време у псет где ми ћемо бити дајући вам момци што се зове дистрибуција код, који је код да смо унапред написан, али само стао неке делове да завршите писање. Дакле, ви момци, када погледате ово број, можда се заиста уплашио. Ако си само волео, Ахх, Не знам шта да ради, Не знам, као, то изгледа толико компликовано, ах, опусти се. У реду је. Прочитајте спец. Спец ће вам тачно објасне Оно што сви ови програми раде. 

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

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

А онда ћеш у суштини само их све заједно. Спец ће вам рећи како да ставити на командној линији. А ти ћеш моћи да испита да ли или Није твоја врста и тражење раде. Кул. Да ли је неко већ почела и наишао на проблеме или питања имају сада са овим? ОК. 

ПУБЛИКА: Чекај. Имам питање. 

Анди Пенг: Да. 

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

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

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

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

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

Анди Пенг: Да, то су у коду. У игри 15, пола од то је већ написано за вас. Дакле, те функције су већ у коду. Да. У реду. Па, све најбоље. То је одвратно дан. Дакле, надамо се ви немојте бити превише лоше да останем унутра и кодирање.