СПЕАКЕР 1: Хеи еверионе! Добро дошли назад у одељак. Драго ми је да видим да многи од вас обоје овде, и свако ко гледа на мрежи. Дакле, као што је то уобичајено добродошли назад. Надам се да сте сви имали диван викенд, пун одмора, релаксације. Било је прелепо јуче. Дакле, надам се да сте уживали у природи. 

Дакле, прво неколико саопштења. Градинг. Дакле, већина би требало да имате стечен емаил од мене о свом Сцратцх Псет, као и оцењивање за Псет 1. Дакле, само пар ствари. Будите сигурни да користите цхецк50 у стиле50. Они су требале средства за вас, да се уверите да сте добијање онолико бодова колико можете без непотребног губљења их. Дакле, ствари стилу су веома важни. Ми ћемо да скинем за њу. Неки од вас можда већ приметили да из Псет. И цхецк50 је само стварно једноставан начин да се уверите да смо заправо враћа оно што треба да се врати у корисник, и да је све то ради правилно. 

На другом напомену, уверите се да уплоад ствари до одговарајућег фолдера. То чини мој живот само мало теже Ако отпремите Псет 2 у Псет 1 јер кад сам преузети ствари, они не преузети исправно. И знам да је мало несигуран у систему да се навикнем, али само било супер опрезни, ако је само за мене, тако да када постајеш е-пошту у као 2 сати пре подне и ја сам класирање. Ако не проузрокује морам да погледам широм за ваш Псет. Цоол. 

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

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

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

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

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

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

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

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

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

Испис мало променљиву. Дакле, ако имате кључ као у Цезара, који ћемо погледати. Можете рећи Принт тастер у било ком тренутку. То ће вам рећи шта је вредност тако да, можда негде успут, Ви овервроте кључ. Можете заправо рећи јер заправо може се приметити да вредност. 

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

Дакле, са тим, идемо да видим како то иде. Ја ћу покушати и прекидач код мене уређаја. Видим да ли могу да урадим ово. Све. Ми ћемо то огледало. Нема ничег луд на мој лаптоп ионако. У реду. То мора да буде ова. То је тако мали. Хајде да видимо да ли можемо да урадимо ово. 

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

Оно што је важније је терминални овде. И овде имамо Зашто је тако мали? Подешавања. Ох. Труе Ике. Како је ово? Одатле. Да ли је то боље за све? ОК ,. Цоол. 

Знаш кад си у ЦС техничке потешкоће цласс су врста део до-- Дакле, хајде да јасно ово. У реду. Дакле, овде у секцији, које смо овде имали. Цезар је извршна датотека. Па сам направио га. Дакле, једна ствар да схвате са ГДБ је да ради само на извршним фајловима. Дакле, не можете да га покренете на ДОТСИ. Мораш да заиста направи сигурни да ваш код саставља, и да заиста може да се покрене. 

Дакле, уверите се да ако се то не деси састави, да се да се састави, тако да можете некако покренути кроз њега. Дакле, да почне ГДБ, све што урадите, Глориа типа ГДБ, а онда само филе који желите. Увек мисспелл ​​Цезара. Али желите да се уверите јер је извршна, Ти Дот блиц, тако да значи идеш покренути ЦСИ ћеш извршити Ова датотека или са дебагером. У реду. Дакле, ти то, ти Ова врста глупости. То је само све ствари о дебуггер. Ти стварно не морају да бринути о томе сада. И као што видите, имамо ово Отворене паренс, БДП, цлосе паренс, и некако изгледа као наша командна линија, зар не? 

Дакле, оно што желимо да урадиш-- --Со, Прва ствар је желимо да изаберете место да га сломи. Дакле, постоји један буг У овом програму Цаесар да представим, да ћемо сазнати. Он Шта је то што је потребно је улаз Барфоо у свим капе, а из неког разлога то не мења А. Управо оставља она сама, Да ли је све остало тачно, али друго слово Остаје непромењен. Дакле, ми ћемо покушати да схватим зашто је то. Дакле, прво сте ствар обично Желим да радим кад год почнете на ГДБ је схватити где да га сломи. 

Дакле, Цезар је прилично кратак програм. Ми само једну функцију, зар не? Оно што је наша функција у Цезара? Постоји само једна функција, Главни зар не? Главни је функција за све ваше програме. Ако нисте имали Маин, могао бих да мало забринут сада, али надам се да сви имали Главно тамо. Дакле, шта можемо да урадимо да се можемо Само бреак Маин, баш тако. Дакле, пише, у реду. Сет смо БРЕАКПОИНТ једног тамо. 

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

Дакле, ако сте овде, имамо Ако РЦ није једнака 2. Дакле, ако ви сви имате да фајл који сам послао горе видећете да је то као Прва линија наш главни функција, зар не? То проверава да видимо да ли имамо тачан број аргумената. Дакле, ако се питате ако РЦ је тачно, можете да урадите нешто баш као Принт РЦ. РЦ је две, које је оно што смо очекивали, зар не? 

Дакле, можемо да идемо даље, и наставите путем. Дакле, имамо неке кључне тамо. И можемо да штампамо наш кључ да се уверите да је то тачно. Занимљиво. Није баш оно што смо очекивали. Дакле, једна ствар да схвате са ГДБ такође, је да није док не стварно ударио Следеће, да је линија коју сте управо видели заправо извршава. Дакле, у овом случају Кеи још није додељен. Дакле, кључ је нека вредност смеће да видите на дну тамо. Негативан $ 120-- --ИТ је милијарду и нешто чудно ствари зар не? Није кључ који смо очекивали. Али, ако ударимо Даље, а онда покушати Принт тастер, то је три. 

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

Звучник 2: Кад Рандом Бројеви шта то значи? 

СПЕАКЕР 1: То је само случајни. То је само за смеће. То је само нешто што твој рачунар ће насумично доделити. Цоол. Дакле, сада можемо да пређемо преко, и тако сада имамо ову обичан текст ГетСтринг. Дакле, дозволите ми да представим шта ће се десити када смо ударили Нект овде. Наш ГДБ врста нестане, зар не? То је зато што ГетСтринг сада извршава, зар не? Дакле, када смо видели обичан текст једнако ГетСтринг, отворене паренс и паренс, и ми ударио Даље, то је заправо извршена одмах. Дакле, то је чекао да улазни нешто. 

Дакле, идемо да унесете храну која је оно то што није као што сам вам рекао и то само каже да је то завршио извршавање, то затворен носач значи да је изласка из те петље. Дакле, можемо да удари Даље, а сада, као што сам Сигурно сте упознати са Цезара, Ово је, како је ова линија урадити. То је за инт једнако 0, н једнако Стрлен, обичан текст, а затим Ја је мање од Н, ја, плус, плус. Шта је ово петље да уради? Отворите поруку. Цоол. Дакле, хајде да почнемо да радимо то. 

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

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

И ми имамо овај чек. И Ова провера треба да раде, зар не? То је О Треба промењен три слова напред. Али ако приметите, ми нешто другачије. Дакле, у овом случају овде, она ухватила то, па ова линија погубљени, која модификовани наш Б. Међутим, у овом случају овде, имамо да само то га прескачу, и отишао у [? Л Сифф. ?] Дакле, нешто се дешава тамо. Шта да вам кажем је да, знамо да треба да ухвати овде, али то није. Може ли неко види шта је наш Проблем је у тој линији? То је веома минут ствар. Такође сте да погледате кода. Такође је лине-- заборавити шта је линија тамо-- али је у [неразумљиво]. Да? 

СПЕАКЕР 4: То је на већи од страна, ако сте то прочитали у књизи. СПЕАКЕР 1: Тачно. Дакле, дебагер није могао рећи Ви то, али дебуггер да те доле на линију да знате не функционише. А понекад, кад нарочито касније у семестру, када је имате посла са стотина, а сто неколико линија кода, и ви Не знам где је то што није, Ово је одличан начин да се то уради. Дакле, нашли смо нашу грешку. Можете га поправити у вашој датотеци, а онда можете да га покренете поново, и све ће радити савршено. А највећа ствар Ово може да изгледа као, у реду. Да. Цоол. Знао си шта тражиш. Дакле, Ви сте знали шта да урадите. 

ГДБ може бити супер корисна јер вас може одштампати све те ствари које сте не би. То је много више користи него принтф. Колико користите као принтф изјавама да схватим где је буба, зар не? Дакле, са овим, ти не да се стално враћамо, и лике коментарисање у Принтф, или коментарисање напоље, и схватим шта треба да штампате. То заправо само вам омогућава да корак кроз, исписати ствари како идете кроз, тако, можете посматрају како се мењају у реалном времену, као ваш програм је покренут. 

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

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

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

Дакле, ако се вратимо на наш ПоверПоинт. Ће ово да ради? Авх. Да. У реду. Дакле, ако сте икада требати од они опет, ту је списак. Дакле бинарно претраживање, који сви памти велики спектакл Давидов копирања телефонске књиге на пола. Ја стварно не да телефонски именици Аниморе, јер као где и ти Узмите телефонске књиге ових дана? Ја стварно не знам. Бинарни Претрага. Да ли се ико сећа како Бинарни Сеарцх радови? Свако уопште? Да? СПЕАКЕР 5: Знате кад погледате којих је половина било би у, на основу тога, и уклоните другу половину. 

СПЕАКЕР 1 Тачно. Дакле, бинарно претраживање, некако је од је-- --ве волим да зовем га завади па владај. Дакле, оно што ћемо урадити је ћете изгледати у средини, и видећете да се подудара оно што тражите. А ако се то не деси, онда покушајте да схватити, да ли ће да остане пола или десна половина. Дакле, ово може да буде ако тражите на нешто што је по абецеди, видиш, ох. Да ли Алисон долази раније М? Да. Дакле, идемо у погледај првом полувремену. 

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

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

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

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

Дакле, прва ствар коју радимо је погледај у средини, зар не? И ти ћеш бити кодирање Бинари Претрага за секунд. Дакле, то ће бити забавно. Тако да гледамо у средњи мали низови 3. Да ли 3 једнаке 7? Не. То је шест. Дакле, да ли је мање од или више од седам? Мање од. Да. Нице јоб момци. Осећам као да треба Имам слаткише јер сам Желим да га бацим у двориштима. То је оно што ћу да урадим следеће недеље. То ће вас држати момци Схарп. 

Дакле, ми бацити да Прво полувреме, зар не? било је мање од. знамо да је све на тој лијевој страни ће бити мање него што Ми смо у ствари тражимо. Дакле, нема потребе да се обратите пажњу на то. Заборави на то. Дакле, сада гледамо наше десне стране, и гледамо на средини тамо, а сада је девет. Дакле, 9 је-- --Еверионе? Већи него што смо тражи, зар не? Дакле, идемо бацити далеко све на десно. Лике то. Сада, све смо остало је једно. Тако да проверите, је ли ово једна оно тражимо? је. Пронашли смо оно што смо хтели. Дакле, ми смо урадили. Билинеарно Претрага. 

А ако приметите, ми имао седам улаза тамо. Било нас је само узео као три пута, али ако радите као милијарду, ви знате колико корака би предузети ако смо имали четири милијарде ствари? Ани нагађања? То је 32. 32 корака до наћи нешто у четири милијарде елеменат низ због овлашћења два. Дакле, два је 32, је на четири милијарде. 

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

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

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

Хм? 

СТУДЕНТ: [неразумљиво]? Инструктор: Да. Било је нешто наћи у средини. 

СТУДЕНТ: Дакле, можемо да искористимо. У реду. 

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

СТУДЕНТ: Да. н преко 2? Инструктор: Па н преко 2. Дакле, једна ствар на уму је да горњи и доњи границе мењају. Стално цонстрицтинг део низа гледамо у. Дакле, н преко 2 ће само радити за прву ствар коју радимо. Дакле, узимајући горње и доње обзир, како да се тај средњи елемент? Јер желимо у средину између горње и доње, зар не? Хм? 

СТУДЕНТ: [неразумљиво]. 

Инструктор: Дакле, имамо неку средину. И то ће бити горња плус мала преко 2. Страва. Ту идемо. Једну линију доле. Ви сте на путу. Дакле, сада имамо наше Миддле, шта желимо да урадимо? Само уопште. Не мораш да га кодирања. Да. СТУДЕНТ: [неразумљиво]? Инструктор: Значи плус, јер си проналажење просек између два њих. Дакле, ако мислите о њима као врсте повећања у са стране, размислите о томе како се приближавате средњи, хоћеш тако. Дакле, ако сте били на обе стране средње, а ми имамо око 5 и 7. Када их додате Заједно гет 12, поделите са 2, 6 је. 

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

СТУДЕНТ: [неразумљиво] тачно у средини ако су имали слуцај има много мањих бројева и као један велики број? 

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

СТУДЕНТ: Цомпаре. Инструктор: упоредите. Дакле, упоредите средина валуе_вантед. Цоол. Па видиш овде имамо Ова вредност желимо овде. Запамтите ово је низ. Тако средњи односи на индексу. Дакле, желимо да урадимо вредности средину. Не заборавите, ако желите Поређења ради, дупле Резултат. Радиш Сингле једнако си само да га распоредити, и онда, наравно, то је ће бити вредност коју желите. Дакле, не ради то. 

Дакле, идемо да видимо да ли вредности на средини је једнака вредности желимо. Не заборавите протезу. Дропбок треба отићи. Дакле, шта да радимо у овом случају? Ако је то оно што желимо да се врати? Ми покушавамо да кажемо. 

СТУДЕНТ: Одштампајте. 

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

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

Дакле, ако имамо маин () и овако нешто. А имате ли је горња неких инпута и ти пита да ли можете да урадите овако нешто? Зар не? СТУДЕНТ: Ја сам покушавао да уради [неразумљиво]. Јер ако је-- Инструктор: Добро. Дакле, желите да ово буде лажна, зар не? СТУДЕНТ: Да. Инструктор: Дакле, у том случају Желим да то изврши, ако то није истина. Тако кул ствар коју урадите је ово. Дакле, запамтите Екцламатион Поинт негира ствари? Каже [неразумљиво] не значи. Дакле, ако погледамо само овај део овде, ти би кажу да процењује да лажно као што желите да. Није лажно је истина која знаци ово би извршити. Да ли то има смисла? СТУДЕНТ: Да. Инструктор: Авесоме. У реду. Тако да бисмо могли да се врате истина у овом случају. Тако да сада имамо два друга предмета у овом случају. Које су две наши други случајеви? Хајде само да на овај начин. Почнимо са другом Ако вредности на средини је мања од вредности желимо. Дакле, наша вредност у средини мање од вредности које траћимо. 

Дакле, који се везао и ти Мислим да желите да ажурирате? Горњи или доњи? Горња? Дакле, са које стране низа ћемо да гледамо? 

СТУДЕНТ: ниже. 

Инструктор: Ми идемо да се гледа са леве стране. Дакле, иф мало вредност мања. Дакле, ваш Средња вредност овде је мање од онога што желимо. Дакле, желимо да десна страна нашег низа. Дакле, идемо у упдате наша доња граница. Тако да ћемо распоредити наше ниже. И шта мислите би требало да буде мања? СТУДЕНТ: средња вредност? Инструктор: Дакле, Миддле валуе-- СТУДЕНТ: Плус 1. Инструктор: --плус 1. Може ли ми неко рећи зашто имамо да плус 1? 

СТУДЕНТ: [? Но вредност?] више једнако томе. 

Инструктор: Добро. Јер већ знамо да је наша средња вредност није једнака то и желимо да га искључити од свих каснијих претрагама. Ако сте заборавили да је, плус 1, ово допасти неограничено петље. И ви цете бити ухваћен у Инфините Лооп и онда ћеш Сегфаулт и ствари иду лоше. Дакле, увек проверите да нисте укључујући и вредност коју сте управо погледао. Тако да смо се побринути за то са плус 1. 

Тако да сада имамо наш последњи услов који сам увек за безбедност ради можете да проверите овде, још ако је вредност у средина је већа од вредности желимо. То значи да желимо лева рука пола. Дакле, који је један ћемо да ажурирате? Горњи. А шта је ово ће једнаке? Средњи минус 1, јер, Наравно, желимо бити сигурни да нисмо гледајући тај средња вредност поново. И онда смо га. Тако је. То је све бинарни претрагу је. Није то лоше, зар не? То је као 10 линија Код са белим простором. Дакле, врло моћан, веома корисно, хоћеш да га користите у једном од ваших каснијих псетс. Можда не овај, али касније. Тако научити. Лове ит. То ће вас третирати добро. Дакле, да ли неко има било који Питања о бинарном претрагу? Да. 

СТУДЕНТ: Да ли је битно да ли је ваш н чак или непаран? 

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

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

СТУДЕНТ: [неразумљиво] фирст-- Инструктор: Тако је средњи Први елемент који смо дошли, зар не? Дакле, било низ једног или год тражимо само случајно кокање у средини. Дакле, то је наш најбољи случај. Уђете у реалним проблемима, вероватно не ће доћи до [неразумљиво] тако често. Шта је са нашим најгорем слуцају? Наш најгори случај је Лог н. Као и да има везе са целини овлашћења два ствари које сам говорио. 

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

Ако сте имали тај Јумблед торбу бројева и ви кажете, У реду, ја ћу да проверим средину број и број тражим је мање од тога, ја ћу да произвољно избацити једну половину. Ви не знате да ли би ваш Бројеви у тој другој половини. Ваша листа мора бити сортирана. Такође, ово може да буде иде напред мало, али морате да имате случајан приступ. Морате бити у стању да само иди на тај средњи елемент. Ако имате да пролазе кроз нешто или ти треба додатне кораке да се на тај средњи елемент, није лог н више јер ви додавањем још посла у њу. И то ће учинити мало више смисла за две недеље, али сам некако хтео да увод, да вам момци идеју о томе шта је то да дође. Али они су двојица важне претпоставке што вам је потребно за бинарни листу. Уверите се да је сортирано. То је велико за ви сада. И на то можемо да идемо у остатак наших врста. Дакле, четири сортс-- балон, Инсертион, селекција, и спајање. Они су сви некако кул. Ако ви одлучите да ЦС 124, ћете научити о свим врстама врста. И ако си ккцд фан, тамо је стварно кул стрип о као стварно неефикасних сорти, које сам препоручујемо ћеш погледати. Један од њих је као панике Сорт, који је као, ох не, врати рандом арраи. Схутдовн система. Оставите. Дакле Гееки хумор је увек добро. 

Дакле, да ли се ико сећа врсте на само као опште идеје како балон Сортирај дела. Сећаш се? 

СТУДЕНТ: Да. 

Инструктор: Иди за њу. 

СТУДЕНТ: Значи идеш кроз и ако је већи, онда замените два. 

Инструктор: Аха. Екацтли. Дакле, само поновити кроз. Ти провери два броја. Ако неко раније већи од оног после тога, само их мењате, тако да је у На овај начин све већем броју Буббле Уп крајем листе и све нижи бројеви буббле доле. 

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

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

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

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

Дакле, онда проверава стање и она каже, у реду је бројач већа од нуле. Ако је, то опет. Желите да тако да када ресет проћи, бројач је једнака нули. Ако идете кроз Сортед Арраи, ништа се не мијења, ово не успе, а ви врати сортирана листа. Да ли то има смисла? СТУДЕНТ: Може у мало. Инструктор: У реду. Ако постоји било који други Питање које се појављује. Да. 

СТУДЕНТ: Шта би функција бити за замјене елемената? 

Инструктор: Тако да заправо може да напише да ако ћемо сад десно. Цоол. Дакле, у том смислу, Алисон иде да се вратите на апарат. То ће бити забавно. И ми имамо наше лепе балон врста ствар овде. Тако да сам већ урадио бициклизма кроз низ. Ми имамо наше своп да једнаки нули. Дакле, желимо да заменимо поред Елементи ако су из реда. Дакле, прва ствар коју треба да Не се поновити кроз нашу низ. 

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

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

Тако да не морају да брину о њима. Да ли то има смисла за све? Да кул мали трик? Дакле, у том случају, ако је смо итератинг кроз, знамо да желите да проверите да ли Арраи н и Н плус 1 су у реду. У реду. Дакле, ево Псеудокод. Ми желимо да проверите да ли низ н и н плус 1 су у реду. Дакле, шта би смо тамо имамо? То ће бити нека условна. Биће ако. 

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

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

А онда можемо да урадимо је да одемо напред и прераспоренује низ Н плус 1, јер ми знамо има ту вредност ускладиштене. То је такође један од великих ствари-- Не знам да ли је неко од вас имао проблема где Ако пребаците два линија кода изненада ствари радио. Поредак је веома важно у ЦС. Дакле, проверите да ли сте дијаграм ствари ако је могуће о томе шта се стварно дешава. Дакле, сада ћемо пренесете низа Н плус 1, јер ми знамо има ту вредност ускладиштене. 

И можемо доделити то арраи н или у овом случају низ сам. Превише варијабли. У реду. Дакле, сада смо прекомандован низ Јесам плус 1 до једнака шта је у низу И. А сада можемо да се вратимо и доделити низ сам да шта? Анионе? 

СТУДЕНТ: 10. 

Инструктор: 10. Екацтли. И још једна ствар. Ако смо га заменили сада, шта треба да радимо? Шта је једна ствар који ће нам рећи Ако смо икада да раскине овај програм? Оно што нам говори да смо имају сортирана листа? Ако не обављају никакве размене, зар не? Ако своп једнака зеро крајем ове. Дакле, кад год извршите замену, као што смо Управо јесам овде, желимо да ажурирате своп. И знам да је било питање раније Абоут Можете користите нула или један уместо истине и лажи. И то је оно што овај ради овде. Дакле, ово каже, ако не своп. Дакле, ако Свапс нула, што сам увек је-- гет моје истине и моји фалсес помешао. Ми желимо да процени труе а то није. Дакле, ако је нула, онда је лажна. Ако га негирају у [? банг?] постаје истина. Онда ова линија извршава. 

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

СТУДЕНТ: Шта пауза радим? 

Инструктор: Бреак само разбија те из петље. Дакле, у овом случају то би баш као прекинули програм а ви би само Имам листу сортирају. СТУДЕНТ: Невероватно. Инструктор: Жао ми је? СТУДЕНТ: Зато што смо претходно усед писана 1 Овер написао нула да представи да ако који ће радити или не. 

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

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

СТУДЕНТ: [неразумљиво] инт маин обично. Да ли имати то за ово? 

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

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

СТУДЕНТ Н минус 1. Инструктор: Н минус 1. Тако да значи да постоје Н минус 1 поређења. Дакле, једна ствар је да схвате да је првог итерацији, идемо кроз, упоредимо ови два-- тако да је 1. Ове две, три, четири. Дакле, после једне итерације смо већ имају четири поређења. Када говорим о рунтиме и н. Н представља број поређења као функција колико елемената имамо. У реду? 

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

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

У реду. Дакле, шта сад је најбољи случај рунтиме? СТУДЕНТ: Нула? Или 1? 

Инструктор: Тако би 1 бити једна упоређивање. У праву. 

СТУДЕНТ Н минус 1? 

Инструктор: Па, да. Дакле н минус 1. Кад год имате концепт као Н минус 1, склони смо да једноставно оставим а ми само рећи н зато што имате то цомпаре сваки тхесе-- сваког пара. Било би н минус 1, што смо Ми само бих је отприлике н. Када имате посла са рунтиме, све је у приближан. Докле год експонент је тачно, ти си добар. 

Тако смо се са тим. Тако да је најбољи случај Н, који значи да је листа већ сортирана, и све што урадите је да покренете кроз и проверите да то сређено. Цоол. У реду. Дакле, као што видите овде, ми само још неке графиконе. Тако н квадрат. Забава. Много горе него н као што видимо, и много, много горе него дневника 2н. А онда и ући дневника трупаца. А ти узети 124, добијате у попут дневника звезда, која је као луд. Дакле, ако сте заинтересовани, ИП адресу Лог звезда. То је врста забаве. Дакле, имамо овај велики графикон. Само главе горе, ово дивно графикон да за ваш средњи рок, јер смо дуго да вас питам те Тхинс. Дакле, само главе горе, имати то на својој Средњорочни на лепом Цхеат Схеет тамо. Па смо гледали буббле врсте. У најгорем случају, Н на квадрат, најбољем случају, н. И ми ћемо да погледате друге. 

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

СТУДЕНТ: основи проћи налог и направите нову листу. И баш као што ви стављајући елементе у, ставите их на правом месту у новом листи. 

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

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

Сортед део који само остави на миру. Хм? 

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

Ово је твој најмањи, распоредити га на вредности. И ви ћете бити много срећнији када идемо кроз кода. Па смо проћи, ми га заменимо, па онда погледамо овај неразврстан делу. Дакле, идемо да изаберете три од. Ми ћемо га ставити на на крај нашег сортиран дела. И ми ћемо само да радимо да, то ради, и ради то. Дакле, ово је наша врста псеудокоду овде. Ми ћемо их кодира овде у секунди. Али само нешто да хода преко на високом нивоу. Ти ћеш да иде од И једнако 0 за н минус 2. То је још једна оптимизација. Не брините превише о томе. Дакле, као што сте рекли. Јацоб је говорио, како ми то радимо пратити шта је наш минимум? Како знамо? Морамо да упоредите све у нашем листу. 

Дакле, минимално износи сам. То је само кажем у овом случају индекс наше минималне вредности. Онда ће то поновити кроз и иде од Ј једнак И плус 1. Дакле, већ знамо да је То је наш први елемент. Ми не треба да се упореди са себе. Тако да почнемо да га пореде са следећа један због чега је и плус 1 до Н минус 1, што је крај низа тамо. А рекли смо ако низ у ј је мање од Арраи мин, онда пренесете где Наш минимални индекси је. 

А ако мин није једнак И, као у којој смо се вратили овамо. Дакле, као кад смо први пут урадили ово. У овом случају, она ће почети у нула, то би завршити као два. СО Мин не би једнако сам на крају. То нам омогућава да знамо да је морамо да их замене. Осећам се као конкретан пример ће помоћи много више од тога. Зато ћу кодирају ово са вама сада и мислим да ће бити боље. 

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

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

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

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

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

И ми желимо к у овом случају већ величина чувају овде, тако да можемо да користимо величину. Величина је величина низа. И ми само желимо да Упдате К по један сваки пут. Цоол. Тако да сада морамо да нађемо Најмањи елемент овде. Дакле, ако смо кроз поновити, ми Желим да кажем, ако је низ у К је мање од наших најмањих валуе-- Ово је место где смо заправо праћење шта је Најмањи овдје-- онда желимо да преносите шта је наш најмања вредност. 

То значи да, ох, ми смо итератинг овуда. Шта год вредност је ту је није наша најмања ствар. Ми не желимо. Ми желимо да га распоредити. Дакле, ако смо га пренамене, шта мислиш можда у овом код овде? Желимо да преносите Најмањи и положај. Дакле, оно што је сада најмањи? СТУДЕНТ: Арраи К. Инструктор: Арраи К. И шта је сад ситуација? Шта је Индекси наша најмања вредност? То је само к. Дакле низа к, к, они поклапају. Па смо желели да преносите то. А онда након што се наш најмањи, тако да је на крају ово петље Овде смо пронашли оно што је наш најмањи вредност, тако да само замијенити. У овом случају, као што кажу људи најмања вредност је овде. Ово је наша најмања вриједност. 

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

СТУДЕНТ: За величину, никад Стварно га дефинишу или промените га, Како то зна? 

Инструктор: Па једна ствар приметити овде је величина Инт. Дакле, говоримо у овој врсти сорт-- је функција у овом цасе-- је Избор врста, то је прошло с функцији. Дакле, ако није донет у, ти би нешто као са дужином низа или би поновити кроз наћи дужину. Већ зато што је прошло у, можемо да га користимо. Само претпоставити да корисник Дао сам ти исправну величину која заправо представља величина вашег низа. Цоол? 

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

СТУДЕНТ: Хоћете да кажете величина је претходно дефинисано? Инструктор: Да. Величина је претходно дефинисано горе Овде у декларацији функције. Тако да претпостављам да је то био донет од стране корисника, а за име једноставности је, ћемо да претпоставимо да корисник нам је дао одговарајућу величину. Цоол. Дакле, то је избор врста. Момци, ја знам да смо данас уче много. То је густа података за секцији. Дакле са тим, идемо да иде у уметања врсте. 

У реду. Дакле, пре него што морамо да урадимо наш Рунтиме анализа овде. Дакле, у најбољем случају, одобрена јер сам вам показао табела Већ врста је одало. Али најбољи случај Рунтиме, шта мислимо? Све сортирано. Н квадрат. Свако има објашњење зашто мислиш? 

СТУДЕНТ: си упоређивањем тхроугх-- Инструктор: Добро. Ти поређења кроз. На сваком итерација, чак, иако смо децрементинг ово један, Ви још увек претраживања све да пронађу најмањи. Дакле, чак и ако ваш најмања вредност је овде на почетку, Ви још увек га пореде против свега да се уверите да је то најмања ствар. Тако да ћете завршити пролази кроз око н квадрат пута. У реду. А шта је најгори случај? Такође, Н на квадрат јер идете да радите ту исту процедуру. Дакле, у овом случају, избор Сортирај има нешто да смо и зовемо очекивало Рунтиме. Дакле, у другима, ми само знамо горњи и доњи граница. У зависности од тога како је луд наше листа или како Унсортед је, они варирају између Н или Н квадрат. Ми не знамо. 

Већ зато што избор врста има исти најгори и најбољи случај, који нам каже да без обзира на тип уноса смо имају, да ли се потпуно то сортирано или потпуно реверсе сортирано, то је Биће потребно исту количину времена. Дакле, у том случају, ако је запамти из наше табеле, заправо имао вредност која ова два врсте немају, што је очекивано Рунтиме. Тако да знамо да кад год трчимо избор врсту, то гарантовано покренете н квадрат време. Постоји варијабилност ту. То је само очекује. И, опет, ако желите да сазнате више, узми ЦС 124 у пролеће. У реду. Видели смо ово. Цоол. Тако Сортирање уметањем. И вероватно ћу да блазе кроз ово. Нећу да те момци кодирања. Само ћемо проћи кроз њу. Дакле убацивање сорта је љубазан на сличан избор Сорт у да имамо обоје Унсортед и сортиране део низа. 

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

Зато што сте у листи сами, ти су сортиране. Честитамо екипи Први елемент у овом низу. Сте већ сортиране све сами. Дакле, сада смо сортиране и Унсортед низ. Тако да сада узмемо први. Шта се дешава између овде И овде је да кажемо, У реду, ми ћемо да погледамо Прва вредност нашег несортираног низа и ми ћемо га улаз у својој тачно место у сортиран низ. 

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

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

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

Дакле, у основи за сам је једнако 0 до Н минус 1, то је само дужина нашег низа. Ми имамо неке елементе који је једнак први низ или први индекси. Поставили смо ј једнак на то. И док ј је већи од нула и низ, Ј минус 1 је већи од елеменат, тако да све што ради је пазећи да Ваш ј заиста представља Унсортед део низа. 

Дакле, док још има ствари сортирање и ј минус један је-- шта је елемент она? Ј никада није овде дефинисан. То је врста нервира. У реду. Ионако. Дакле, Ј минус 1, да ли проверавате елемент пред њим. Кажеш да, у реду, је елемент пре него што где год сам ја-- немојмо заправо извући ово. Рецимо да је ово као на нашем другом пролазу. Тако да ће бити једнака 1, што је овде. 

Тако да ће бити једнако 1. То би 2, 4, 5, 6, 7. У реду. Дакле, наш елеменат у овом случају ће бити једнака 4. И ми имамо неку ј да је ће бити једнака 1. Ох, Ј је децрементинг. То је оно што је. Дакле, ј је једнак И, па шта је ово изрека је да док се крећемо напред, Ми само правимо сигурни да нисмо више индексира Овако када покушавамо да убаците ствари у нашу сортиране листе. 

Дакле, када ј једнак 1 у овом предмету и Арраи Ј минус --виберите-- тако низ Ј минус 1 је 2 у овој цасе-- ако је то већа од елемента, онда све ово ради помјера ствари доле. Дакле, у овом случају, низ Ј минус један би арраи нула, што је 2. 2 није већа од 4, тако да ово не извршава. Тако да смена не помера надоле. Шта ово ради овде је само померате сортирану низ доле. У овом случају, у ствари, ми могао урадиш-- Нека ово буде 3. Дакле, ако смо да хода кроз с овај пример, сада смо овде. Ово је сортирано. Ово је Унсортед. Цоол? Дакле, и је једнак 2, тако наш елемент је једнака 3. А наша ј је једнако 2. Тако да погледамо кроз и и ми кажу, у реду, је низ Ј минус један већа од елемента да гледамо? А одговор је да, зар не? 4 је већи од 3 и ј је 2, тако да овај код извршава. 

Дакле, шта сада радимо низ у 2, тако да овде, ми их замене. Па смо рекли, у реду, Арраи на 2 сада ће бити 3. И Ј ће износити ј минус 1, који је 1. То је страшно, али ви добијете идеју. Ј је сада једнак 1. И низ Ј је само да буде једнаку нашим елемент, који је био 4. Ја избрисао нешто што не би требало имају или мисвроте нешто, али ви добијете идеју. 

Он креће у Н. И онда би то било, то би петља опет и то би рекли, у реду, ј 1 сада. И низ Ј минус 1 је сада 2. Да ли је 2 мање од нашег елемента? Не? То значи да смо убачена овај елемент у исправном месту у нашем сортиран низу. Онда можемо узети и кажемо, У реду, наш сортиран низ је овде. И било би потребно овај број 6 и бити као, у реду, је 6 мање од овог броја? Не? Цоол. Ми смо добро. 

Уради то поново. Ми кажемо 7. Је 7 мање него крај нашег сортирано низа? Не. Дакле, ми смо добро. Дакле, ово би се сортирају. У основи све ово ради је то каже Таке Први елемент Ваша Унсортед арраи, схватити где иде у вашем сортиран низ. И то само брине свопова за то. Ти си само у основи замене док је на правом месту. Визуелна слика је да си ти креће све доле то ради. 

Дакле, то је као пола мехур сорт-Ескуе. Цхецк оут студије 50. Топло препоручујем покушавам кодирања ово сами. Уколико имате било каквих проблема или желите да види узорак кода за Сорт убацивања, молим вас да ми. Ја сам увек ту. Дакле, најгори случај Рунтиме и најбољи случај Рунтиме. Као што сам већ видио момак из табеле Показали сте, то је и н квадрат и н. 

Тако некако иде са онога што смо причали О нашим претходним врстама, најгоре Случај Рунтиме је да ако то је потпуно Унсортед, морамо упоредити све ове н пута. Ми радимо пуно поређења јер ако је то обрнутим редом, идемо да кажемо, у реду, ово је исти, ово је добро, а ово ће морати да се упоредити против првог који се вратио. И као што смо добили ка пред крај, имамо Поређења ради, упоредите и сравни против свега. 

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

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

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

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

У супротном ово сумира последњи елемент низа, а затим узима збир остатак низа. Тако да је управо то се разбије у мање и мање проблема. Скратим, рекурзија, Функција која се зове. Ако је то све што имаш од овога, то је оно што рекурзивна функција. Ако узмете 51, добићете веома, веома удобан са рекурзије. То је заиста кул. Имало је смисла у као 3 сам један излазак. И ја сам као, зашто сам никада не користим ово? 

Дакле, за стапања врсте, у основи шта ће да уради је да је ће то разбити и прекините доле док је само појединачних елемената. Појединачни елементи су лако сортирање. Видимо да. Ако имате један елемент, то је већ сматрају сортирају. Дакле, на улаз н елемената, ако је н мање од 2, вратио само зато што то значи је 0 или 1 као што смо видели. Они се сматрају сортирана елементи. 

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

Дакле, како можете мислите о стапање само уклоните мањи број сваког од под низова и само додати на појавио низ. Дакле, ако погледате овде, када имамо Ови скупови имамо 4, 6, и 1. Када желимо да спојимо ово, погледамо ове прве две и ми кажемо, у реду, 1 је мањи, иде на фронт. 4 и 6, нема ништа да се упореди то се, само означиш на крај. 

Када смо комбинују ова два, само смо узети мањи једног од ова два, тако да је 1. А сада узмемо мањи од њих двојице, СО 2. Мања од ове двојице, 3. Мања од ове две, 4, 5, 6. Дакле, ти само чупање ово. И зато што су они је сортирано претходно, Ви само једну Упоређивање сваки пут тамо. Дакле, још код овде, само репрезентација. Тако да почнете у средини и некако си лево и десно а онда само спајање тих. 

А ми немамо шифру за спајање овде. Али, опет, ако идете на проучавају 50, то ће бити тамо. У супротном дођи да разговарамо још ако си збуњен. Дакле, добра ствар је што најбољем случају, у најгорем случају, и очекује се Рунтиме су све у лог Н, који је далеко бољи него што смо видели остатак наших сорти. Видели смо н квадрат и шта смо заправо стигао је н лог н, што је одлично. 

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

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

Дакле, то је то за деоницу. До жице. Урадио сам то у року од једног минута. Али ето. И ја ћу имати крофне или слаткише. Да ли је неко алергичан на нешто, успут? Јаја и млеко. Дакле, крофне су не? У реду. У реду. Чоколада не? Старбурст. Старбурстс су добри. У реду. Ми ћемо имати Старбурст следеће недеље тада. То је оно што ћу добити. Ви имате велики недељу. Читати спец. 

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