[За възпроизвеждане на музика] АНДИ Пенг: Добре дошли в 3-та седмица на раздел. Благодаря, момчета, за всичко идва към настоящия момент по-рано старт днес. Имаме хубава, малко днес интимна група. Така че да се надяваме, че ще стигнем до удар, може би, по-рано, малко по малко рано днес. Така бързо, само някои Съобщения за днес в дневния ред. Преди да започнем, ние сме просто ще отидем няколко кратки логистични проблеми, pset въпроси, разпиташ, такива неща. И тогава ние ще се потопите полето инча Ще използваме дебъгер нарича GDB да започнем развенчаването нашия код, който David обяснено в лекция на другия ден. Ще отидем през четирите видове сортове. Ще отидем над тях доста бързо тъй като те са доста интензивно. Но знам, че всички слайдове и изходния код са винаги на линия. Така че не се колебайте, при вашия прочит, за да да се върнете и да погледнем на това. Ще проверете асимптотичната нотация, която е само един луксозен начин да казва "Времето на автономна работа," където имаме голямото О, които Дейвид обясни в лекция. И ние също имаме Omega, които е по-ниска, обвързана време на работа. И ние ще говорим малко по- по-задълбочено по отношение на това как те работят. И накрая, ние ще отидем двоично търсене, защото много от вас, които вече имат Погледна към вашите psets вероятно знаете, че това е въпрос, който е във вашия pset. Така че всички ще се радваме които ние покриваме това днес. И на последно място, на вашия обратна точка, аз всъщност наляво около 15 минути при края просто да отидем логистика на pset3, на всички въпроси, може би малко на насоки, ако щете, преди да започнем програмиране. Така че нека да се опитаме да се измъкне сам материала доста бързо. И тогава можем да прекарат известно време приемате повече въпроси за pset. ДОБРЕ. Бързо, така че само няколко съобщения, преди да започнем днес. Първо, добре дошли да направи то през две от вашите psets. Взех погледнете your-- да, нека получи аплодисменти за това. Всъщност, бях наистина, наистина впечатлен. I степен първата pset за вас, момчета миналата седмица и вие, момчета направиха невероятни. Style е на точка освен няколко коментара. Уверете се, че сте винаги коментирайки кода си. Но вашите psets бяха на точка. И да я поддържа. И това е добре за грейдер да виждам, че вие, момчета са пускането в толкова усилия в твоя стил и вашия проект в кода че ние бихме искали да видиш. Така че аз съм минаваща покрай своята благодарност за останалата част от TAS. Въпреки това има Няколко разпиташ въпроси Аз просто искам да разясни, че ще направи и двете ми живот и много от друга СНС "живее малко по-лесно. Първо, аз съм забелязал това покрай week-- колко от вас са течаща check50 на Код си, преди да подадете? ДОБРЕ. Така че всеки трябва да се прави check50, because-- на secret-- ние всъщност тичам check50 като част от нашата коректност скриптове за тестване на кода си. Така че, ако си код е неуспешен check50, по всяка вероятност, Това е може би щеше да провалят нашата проверка, както добре. Понякога вие, момчета, имаме правилните отговори. Подобно, в алчни, някои от имате правилните числа, просто разпечатате някои допълнителни неща. И това допълнителни неща всъщност не успее проверката, защото компютърът не наистина знаят какво търси. И така, той просто ще преминава през, се види, че вашата продукция не съвпада какво очакваме отговора да, и отбележете, че е погрешно. И знам, че се е случило в някои от вашите случаи тази седмица. Така че аз се върнах и ръчно преокачествило код на всеки. В бъдеще обаче, моля, моля, уверете се, че сте стартирали провери 50 на вашия код. Защото това е вид болка за ТП да се наложи да се върнете назад и ръчно преокачествяване всеки един pset за всеки единично, малко изпусна инстанция. Така че аз не се свали и да било пунктове. Мисля, че може би е излетял един или два за дизайн. В бъдеще обаче, ако което при липса на check50, Ще бъдат взети точки разстояние за коректност. Освен това са psets поради петък по обяд. Мисля, че има седем минути края на гратисен период, който ние ви даваме. Per Harvard време, те ти е позволено да е седем минути края на всичко. Така че тук в Йейл, ние ще се придържат към това, както добре. Но до голяма степен, в 12:07 часа, ако вашият pset не е в, то се случва да бъдат маркирани като късно. И така, докато той е маркиран най-късно, на TA-- съм все още продължава да бъде класификация на вашите psets. Така че все пак ще виждате оценка се появи. Въпреки това, знаем, че най- В края на семестъра, всички закъснели psets просто ще бъдат автоматично нулира от компютъра. Ние правим това по две причини. One, понякога получаваме извини, като извинения на Дийн, по-късно, че аз не знам все още наоколо. Така че сме искали да се уверете, че ние сме класификация всичко за всеки случай, като, аз съм липсва извинение на Дийн. И на второ място, имайте ум, все още можете да пуснете една pset че има пълния обхват точки. И така, ние искал да клас всички ваши psets просто за да се уверите, че вашият обхват на там и можете да започнете да ги изпробвате. Така че дори и да е късно, пак ще получите кредит за обхват точки, мисля. Така че моралната от историята е, уверете че вашите psets са в по-време. И ако те не са в по-време, знаем, че това не е голяма. Да, преди да се премине, не всеки има всички въпроси по отношение на обратна връзка pset? Да. АУДИТОРИЯ: Знаете ли, ние казваме може да пуснете един от psets? АНДИ Пенг: Да. Така че има девет psets цялостната в течение на семестъра. И ако имате обхват points-- така обхват е само, доста много, да не се опитва на проблем, са ви прати във времето, са ви показва, че сте демонстрирано сте чели спец. Това е доста повече свобода на действие. И ако се изпълнява обхват точки, ние може да падне най-ниската един на пълен обхват. Така че това е в своя полза, за да завърши и се опитват всеки pset. Дори upload-- ако никой от тях работят, ги качите. И тогава ние ще се надяваме да бъде в състояние да ви дам някои от тези точки назад. Готино. Всякакви други въпроси? Страхотен. На второ място, офис hours-- малцина бързи бележки за работното време. Така че на първо място, дойде по-рано през седмицата. Никой не е някога в работно време в понеделник. Кристабел дойде офис часа снощи. Да, Кристабел. И какво имаме в офиса часа снощи, Кристабел? АУДИТОРИЯ: Имахме сладолед. АНДИ Пенг: Така че това е правилно, имахме сладолед в офис часа снощи. Макар че аз не мога да ви обещая, че ще имаме сладолед в работно време всяка седмица, това, което мога да ви обещая е, че ще има значително по-добро съотношение ученик TA да. Подобно на легитимни, това е като 12:57. Като има предвид, че с контрастни Четвъртък, имаш около 150 наистина подчерта деца и не сладолед. И това просто не е продуктивно за никого. Така Поука се, дойде по-рано до работното време и добри неща ще се случи. Също така, са подготвени да задават въпроси. Ти знаеш? Независимо от това, СНС, I мисля, са казва, ние сме били получаване на няколко студенти които идват в четвъртък при подобно, 10:50 Не след като прочетох спец е като да ми помогне, да ми помогне. За съжаление в този момент, има Не можем да направим много, за да ви помогне. Така че заповядайте в началото на седмицата. Хайде рано да работно време. Хайде готови да задават въпроси. Уверете се, че вие, като студент, където са което трябва да бъде така, че СНС може да ви води напред, което е това работно време трябва да бъдат разпределени за. На второ място, така че знам професори искали да ни изненада с тестове. Имах един професор тези, харесват, йо, между другото, не забравяйте, че средносрочната имате следващия понеделник. Да, аз не знаех за това междинен. Така че аз отивам да се окаже, че TA което ви напомня, че всички викторина 0--, защото, знаете, че сме CS. Сега, след като сме направили масиви, можете да получите защо е викторина 0, а не тест 1, а? ДОБРЕ. О, аз имам някои подсмихва за това. ДОБРЕ. Така викторина 0 ще бъде 14 октомври, ако вие сте в секцията понеделник-сряда и 15 октомври, ако сте в раздела вторник-четвъртък. Това не се отнася за тези от вас, в Харвард who-- Мисля, че всичко ще бъде като вашите викторини на 14-ти. Така че да, следващата седмица, ако Дейвид, в лекция, отива, Да, така, че за викторина следващата седмица, вие всички няма да бъде шокиран, защото ти дойде на вписванията и вие знаете, че вашето викторина 0 е след две седмици. И ще имаме мнение сесии и всичко. Така че не се притеснява за се уплаши за това. Всякакви въпроси before-- всякакви въпроси на всички по отношение на логистични проблеми, класифициране, работно време, раздели? Да. АУДИТОРИЯ: Така викторината е ще бъде по време на лекцията? АНДИ Пенг: Да. Така че теста, според мен, е 60 разпределени в това време слот минути че ще вземе само в лекционната зала. Така че не е нужно да дойде в на, като, случаен 19:00. Всичко е наред. Да. Готино. Всичко е наред. Така че ние ще въвеждане на концепцията за вас тази седмица, че Дейвид има вече вид на засегна в лекция през изминалата седмица. Тя се нарича GDB. И колко от вас, докато в хода на написването на вашите psets, са забелязали голям бутон, който казва, "Debug" в горната част на вашия IDE? ДОБРЕ. Така че сега ние всъщност ще получите да изкопае тайната на това, което бутон, който всъщност прави. И аз ви гарантирам, че е красиво, красиво нещо. Така че до сега, мисля, е имало две неща учениците са били типично прави и при дебъгването psets. One, те или се добавят в ФОРМАТ () - така че на всеки няколко линии, те добавят в ФОРМАТ () - О, каква е тази променлива? О, каква е тази променлива now-- и ти вид виж прогресията на кода си, тъй като работи. Или втория метод деца направя е че те просто напишете цялата работа и след това да отидете като тази в края. Надяваме се, че работи. Гарантирам ви, GDB е по-добре от двете от тези методи. Да. Така че това ще бъде вашият нов най-добър приятел. Защото е красиво нещо който нагледно показва и двете какъв е вашият код се справя в определен момент както и това, което всички си променливи са носещи, като това, което им стойности са, при тази конкретна точка. И по този начин, можете наистина определени точки на прекъсване в кода си. Можете да стартирате чрез ред по ред. И GDB просто ще трябва за ти, показва за вас, това, което всички ваши променливи са, какво правят те, какво се случва в кода. И по такъв начин, че е много по-лесно да се види какво се случва вместо ФОРМАТ-ING или записвам си отчети. Така че ние ще направим един пример за това по-късно. Така че това изглежда малко абстрактно. Не се тревожете, ще направя примери. И така, по същество, трите най-големи, Най-използвани функции ще трябва в GDB са следващите, Етап свърши, Стъпка в и бутони. Отивам да се над главата там, всъщност, точно сега. Така че може да ви види, че всички момчета или трябва да я увеличите малко? В гърба, може ли това? Трябва ли да я увеличите? Само мъничко? ОК готино. Ето. ДОБРЕ. Така че аз имам, тук, ми изпълнение за алчни. И докато много от вас, момчета, е написал алчни в линия, докато form-- че е напълно приемлив начин да се направи it-- друг начин да го направите е просто да разделят в по модул. Защото тогава може да има вашия стойност и след това да си остатък. И тогава можете просто всичко това се добавят заедно. Дали логиката на това, което правя тук има смисъл за всички, преди да започнем? Един вид? Готино. Страхотен. Това е доста секси парче на код, бих казал. Както казах, Дейвид, в лекция, след известно време, всички вие ще започнете да виждате код като нещо, което е красиво. И понякога, когато видите красива код, това е толкова прекрасно чувство. Така обаче, като в същото време този код е много красива, тя не работи правилно. Така че нека да тичам check50 по този въпрос. Проверете 50 20-- ООП. 2? Е, че pset2? Да. О, pset1. ДОБРЕ. Така че ние тече check50. И тъй като вие може да видите тук, това е липса на няколко случаи. А за някои от вас, в Разбира се за правене на проблемните комплекти, вие сте като, ах, защо не е тя работи. Защо е да работиш за някои ценности, но не и за другите? Е, GDB ще ви помогне да фигура защо тези входове не са работили. ДОБРЕ. Така че нека да видим, един от проверки бях успяват в check50 е входна стойност от 0,41. Така че правилният отговор, че трябва да бъдат намалени е 4. Но вместо това, което аз съм отпечатване е 3-N, която е неправилна. Така че нека просто стартирате тази ръчно, просто уверете се, че check50 работи. Нека да направим ./greedy. Ами сега, аз трябва да се направи алчни. Ето. Сега ./greedy. Колко се дължи? Нека да направим 0.41. И да, ние виждаме тук че това е извеждане 3 когато правилния отговор, Всъщност трябва да бъде 4. Така че нека да въведете GDB и да видим как можем да отидете за определяне на този проблем. Така че първата стъпка в Винаги дебъгване на кода е да се създаде точка на прекъсване, или точка, при която сте искате компютърът или дебъгер да започнат да търсят. Така че, ако наистина не знам какъв ти е проблема, Обикновено, типичната нещо, което искаме да направите, е да се създаде нашата точка на прекъсване на основното. Така че, ако вие може да видите това червения бутон, точно там, Да, това ме определя граничните стойности за основната функция. Аз кликнете върху него. И тогава мога да отида до моя бутон Debug. Ударих този бутон. Позволете ми да я увеличите обратно, ако мога. Ето. Така че ние имаме, тук, на панел в дясно. Съжалявам, момчета в гърба, можете наистина не може да види много добре. Но по същество, цялата това право панел се справя се следене на двете маркирания линия, която е на линията на код че компютърът се изпълнява в момента, както и всички ваши променливи тук долу. Така че имаш цента, монети, п, всички декларирани за различни неща в този момент. Не се тревожете, защото имаме всъщност не ги инициализира с всички променливи, все още. Така че в компютъра си, вашият компютър е просто виждам, о, 32 767 е последната използвана функция на това място в паметта на компютъра ми. И така, това е мястото, където в момента е цента. Но не, че след като стартирате кода, тя трябва да се превърне Initialized. Така че нека да преминем, ред по линия, какво се случва тук. ДОБРЕ. Така че тук са тримата бутони, че аз просто обяснено. Имате играят, или функцията Run, бутон, имате Стъпка над бутона, и вие също имате стъпка в бутона. И по същество, всичките три от тях просто проверете кода си и правя различни неща. Така че обикновено, когато сте отстраняване на грешки, ние не искаме просто да натиснете възпроизвеждане, защото Играй просто ще тече Код си до края на това. И тогава няма да всъщност знам какво ти е проблема е, освен ако не сте задали множество точки на прекъсване. Ако сте задали множество точки на прекъсване, тя просто ще автоматично тече от една точка на прекъсване, към следващата, към следващата. Но в този случай ние сме Просто една, защото ние искат да работят пътя ни от горе надолу към долната част. Така че отиваме да се игнорира този бутон точно сега за целите на тази програма. Така стъпка над функцията просто стъпки над всеки един ред и ти казва какво компютърът се прави. Стъпката в функция отива в реалното действие това е на твоя ред код. Така например, като ФОРМАТ (), че е функция, нали? Ако исках да физически стъпка в () функцията ФОРМАТ, Бих действително отиде в парчето код, където ФОРМАТ () е написана и виж какво се случва там. Но обикновено, ние предполагаме, че код, който ние ви даваме работи. Ние поеме ФОРМАТ () работи. Предполагаме, че GetInt () работи. Така че няма нужда да се стъпка в тези функции. Но ако има функции че ти пиша себе си че искате да проверите какво се случва, вие ще искате да се оттегли в тази функция. Така че сега ние просто ще да се засили през тази част от кода. Така че нека да видим. О, печат, "О Хай, как особена промяна се дължи? " Не ни пука. Ние знаем, че е работа, така че ние стъпка над него. Така че п, което е нашата плувка, че ние сме initialized-- или declared-- нагоре към върха, ние сме сега са равни на това да GetFloat (). Така че нека да прекрача това. И ние виждаме в дъното тук, програмата ме накара да въведете стойност. Така че нека да вход стойността искаме за тестване тук, което е 0.41. Страхотен. Така че сега, N- направите вие, момчета, да видят тук, в bottom-- това е stored-- защото ние все още не са закръглени, това е съхраняват в тази като гигантски плувка, че е 0.4099999996, която е достатъчно близо до нашата цели, точно сега, на 0.41. И след това ще видим по-късно, тъй като ние продължи прекрачвайки програмата, след тук, п е станал закръглена и цента е станал 41. Страхотен. Така че ние знаем, че нашата работна закръгляване на. Ние знаем, че сме в правилния брой цента, така че ние знаем, че това е Не наистина проблема. Така че ние продължаваме засилването на в тази програма. Ние отидете тук. И така след този ред код, ние Трябва да знаете, колко квартали имаме. Ние прекрача. И вие виждате ние, всъщност, има право на един кв защото сме изважда 25 от нашата първоначална стойност от 41. И ние имаме 16 ляв за нашите цента. Всички ли се разбере как програмата е чрез засилване и защо цента сега стават 16 и защо, сега, монети се превърна 1? Всеки ли след тази логика? Готино. Така че, считано от този момент, работна програма, нали? Ние знаем, че прави точно това, което ние го искам. И ние всъщност не Трябва да разпечатате, о, това, което е цента в този момент, това, което е монети по тази точка. Ние продължаваме да става чрез програмата. Стъпка свърши. Готино. Отиваме над десетки цента. Страхотен. Ние виждаме, че това е взето разстояние 0,10 $ за една стотинка. И сега имаме две монети. Това е правилното. Ние разясни жълти стотинки и ние виждаме че ние имаме останали цента. Хм, това е странно. До тук в програмата, аз трябваше да са изважда моите пари. Може би аз просто не беше правене на това право на линия. И уви, можете да видите тук, защото знаем че ние сме засилването през линии 32 и 33, това е, когато нашата програма неправилно имаше променливи работят. Така че ние можем да погледнем и да видим, о, Аз съм тук, за изваждане цента, но аз не съм в действителност добавяне към моята монета стойност. Аз съм като към цента. И аз не искам да се добави към цента, аз искате да добавите в монети. Така че, ако ние променяме, че да монетите, ние имаме работна програма. Мога да тичам check50. Ти просто да излезете от GDB полето тук и след това пуснете check50 отново. Бих могъл да направя това. Аз трябва да направя алчни. 0.41. И тук, това е печат от правилния отговор. Така че, както вие може да видите, GDB е наистина мощен инструмент защото, когато имаме толкова много код става и толкова много променливи че е трудно за нас, тъй като човек, за да следите. Компютърът, в GDB корекция на грешки, има способността , за да следите всичко. Знам, в Visionaire, вие вероятно можеше да удари някои сегментационни грешки защото вие вървяхте извън границите на масива. В примера на Цезар, това е точно това, което съм приложени тук. Така че аз забравих да проверите за какво ще се случи, ако аз не са имали два аргумента на командния ред. Аз просто не е пускал в тази проверка. И така, ако аз тичам Debug-- задам моята точка на прекъсване на дясно там. Аз тичам Debug. ДОБРЕ. Да. Така че всъщност, GDB е трябвало да са ми казвали, че Беше сегментацията на вина там. Аз не знам какво се случва точно там, но когато той се стартира, той е работил. Когато стартирате реда код и чрез GDB може просто изведнъж се откажат от вас, отиде и да погледнем какво червената Грешката е. Тя ще ви кажа, хей, ти имаше вина сегментация, което означава, че сте се опитали да достъп пространство в масив, който не съществува. Да. Така в следващия проблем установени през тази седмица, момчета Вероятно ще има много променливи витае. Ти няма да бъде сигурен какво всички те имат предвид в определен момент. Така GDB наистина ще ви помогне в фигуриращ какво те всички са равни на и е в състояние да се види, че визуално. Има ли някой объркан за това как всеки от които е работил? Готино. Всичко е наред. Така че след това, ние сме Ще се потопите полето в четири различни видове сортове за тази седмица. Колко от вас, първо от всички, преди да започнем, Прочетох цялата спец за pset3? ДОБРЕ. Гордея се с вас, момчета. Това е все едно половината от този клас, които е значително повече от миналия път. Така че това е страхотно, защото, когато говорим за съдържанието в lecture-- или съжалявам, в section-- ми харесва да се отнасят много, че обратно на това, което е pset и как искате да приложат, че във вашата pset. Така че, ако идват като Прочети спец, тя ще да бъде много по-лесно да се разбере това, което аз говоря за когато казвам, О, хей, това може да е наистина добро място за прилагане на този вид. Така че тези от вас, които са чели спец знам, че като част от вашия pset, започваш да се наложи да напиши тип сортиране. Така че това може да бъде много полезен за много от вас днес. Така че ние ще започнем с, същество, най-прост тип на сортиране, сортиране на подбор. Типичният алгоритъм за как щяхме да отида за това is-- Дейвид премина през всичко това в лекция, така че аз ще се движат по-бързо here-- е по същество, вие имаме масив от стойности. И след това да намерите най- най-малката стойност е сортиран и вие сменяте тази стойност с първата е сортиран стойност. И след това просто да повтаряме с останалата част от вашия списък. И тук е визуална обяснение за това как, че ще работи. Така например, ако бяхме да започнете с масив от пет елемента, индекс 0 до 4, с 3, 5, 2, 6 и 4 стойности поставен в array-- така точно сега, ние просто ще приемем че всички те са неразделени защото не сме тествани по друг начин. И така, как един вид подбор ще работата е, че тя би първата тече през цялата на сортиран масив. Тя ще избирам най-малката стойност. В този случай, 3, нали сега, е най-малката. Той получава до 5. Не, не е по-голяма 5 than-- или съжалявам, е не по-малко than-- 3. Така че минималната стойност е все още 3. И тогава ще стигнем до 2. Компютърът вижда, о, 2 е по-малко от 3. 2 сега трябва да е минималната стойност. И така 2 суапове с тази първа стойност. Така след един пас, ние наистина виж че на 2 и 3, се разменят. И ние просто ще продължа да правя това отново с останалата част от масива. Така че ние ще просто преминават през последните четири индекси на масива. Ще видите, че 3 е следващата минималната стойност. Така че ние ще се разменят, че с 4. И тогава ние просто ще се запази преминаващ през докато, в крайна сметка, вие стигнем до сортиран масив, в който 2, 3, 4, 5, 6 и всички са подредени. Всички ли разбере логиката за това как работи един вид селекция? Просто трябва някакъв вид на минимална стойност. Можете да започнете да следите какво е това. И всеки път, когато го намерите, можете да го сменяте с първата стойност в array-- или не първи value-- следващата стойност в масива. Готино. Така че, както вие вид Видях от един кратък поглед, ние ще Псевдокод това. Така че, ако вие в гърба искат да образуване на група, всички на една маса може да се образува малко партньор, аз ще съм да ви дам хора като три минути да говорим само чрез логиката, на английски език, за това, как може да сме в състояние да приложи Псевдокод да напише нещо като селекция. А има и бонбони. Моля, излезе и да получите бонбони. Ако сте в гърба и искате бонбони, мога да хвърлят бонбони на вас. Всъщност, направете you-- готино. О, съжалявам. ДОБРЕ. Така че, ако ние бихме искали да, тъй като клас, пиши Псевдокод за това как човек може да се обърне този проблем, просто се чувстват свободни. Аз просто ще обикалят и, с цел, да зададете групи за следващия ред на това, което ние трябва да се прави. Така че, ако вие искате да започнете разстояние, какво е първото нещо, да направя, когато се опитвате да приложат начин за решаване на тази програма селективно да сортирате списък? Нека просто да приемем, имаме масив, нали? АУДИТОРИЯ: Вие искате да се създаде някаква сортирай [недоловим], че вие ​​сте на преминаващ през цялата си гама. АНДИ Пенг: Точно така. Така че ти започваш да искаш да превъртите през всяко пространство, нали? Така че, страхотно. Ако вие искате да ми дадете Следващата line-- да, в гърба. АУДИТОРИЯ: Проверете ги всички за най-малките. АНДИ Пенг: Ето. Така че ние искаме да мине през и проверете видим какво минималната стойност е, нали? Отивам да се съкрати, че да "мин." Какво ви момчета искам да правя след намерили минималната стойност? АУДИТОРИЯ: [недоловим] АНДИ Пенг: Значи ти започваш да искаш да го включите с първото от които масив, нали? Това е началото, аз отивам да се каже. Всичко е наред. Така че сега, че сте замениха първите един, какво искаш да направя след това? Така че сега ние знаем, че този тук трябва да е най-малката стойност, нали? След това имате допълнителна почивка на масива, който е сортиран. Така че това, което искам да направя тук, ако сте момчета искат да ми даде следващия ред? АУДИТОРИЯ: Така че след това искате да превъртите през остатъка от масива. АНДИ Пенг: Да. И така, какво означава итерации през вид предполага ние вероятно ще трябва? Какъв тип of-- АУДИТОРИЯ: О, допълнителна променлива? АНДИ Пенг: Вероятно друг за цикъл, нали? Така че ние сме най-вероятно ще искате да превъртите through-- страхотно. И тогава започваш да се върна и да Вероятно провери минималната отново, нали? И ти започваш да продължават да повтарят това, защото примките просто отиваш да продължи да работи, нали? Така че, както вие може да видите, ние Просто има общо Псевдокод за това как искаме да изглежда тази програма. Това обхождане тук, това, което правим обикновено трябва да напишете в нашия код ако искаме да превъртите през масив, какъв тип структура? Мисля, че Кристабел Вече казах това преди. АУДИТОРИЯ: A за контур. АНДИ Пенг: A за цикъл? Точно. Така че това е може би ще бъде за контур. Какво е чек тук ще означава? Обикновено, ако искате да проверите ако нещо е нещо else-- АУДИТОРИЯ: Ако. АНДИ Пенг: An ако, нали? И тогава суапа тук, ние ще разясни по-късно, тъй като David премина през който в лекция, както добре. И тогава вторият ITERATE implies-- АУДИТОРИЯ: Друго за контур. АНДИ Пенг: --another за линия, точно. Така че, ако ние не търсим при това правилно, ние да видим, че ние сме най-вероятно ще се нуждаят от вложените за контур с условен израз там и след това действително част от код, който е Ще сменяте стойностите. Така че аз съм просто обикновено написани код Псевдокод тук. И тогава ние всъщност ще физически, като клас, се опита да приложи това днес. Нека се върнем в тази IDE. Охо. Защо е така not-- то е там. ДОБРЕ. Съжаляваме, нека се опитам да я увеличите малко повече. Ето. Всичко, което правя тук, е че съм създал една програма, наречена "избор / sort.c." Аз създадох масив от девет стойности, 4, 8, 2, 1, 6, 9, 7, 5, 3. В момента, колкото можете виж, те са неподреден. п ще бъде броят, че ти казва размера на ценности имате в масив. В този случай, ние имаме девет стойности. И аз току-що получих за контур тук че отпечатва сортиран масив. И в крайна сметка, аз също имам един за линия, която просто го отпечатва отново. Така теоретично, ако тази програма работи правилно, в края, трябва да видите отпечатан за контур в който 1, 2, 3, 4, 5, 6, 7, 8, 9 всички са правилно в ред. Така че ние имаме нашата Псевдокод тук. Някой иска to-- Аз съм просто щеше да отиде да поиска volunteers-- да ми каже точно какво да напишете, ако ние искаме да, на първо място, просто обхождане чрез началото на масив? Каква е ред на кода съм вероятно ще се нуждаят от тук? АУДИТОРИЯ: [недоловим] АНДИ Пенг: Да, чувствам безплатно to-- Съжалявам, вие не трябва да стоят up-- усещане свободни да повишаваш тон малко. АУДИТОРИЯ: За инт аз се равнява 0-- АНДИ Пенг: Да, добре. АУДИТОРИЯ: аз е по-малко от дължината масив. АНДИ Пенг: Така че имайте интересуваме тук, защото ние не разполагат с функция, която ни казва, дължината на масив, вече имаме стойност, която съхранява, че. Нали така? Друго нещо, което да се запази в mind-- в масив от девет стойности, какви са индексите? Нека просто кажем, този масив е 0-3. Вие виждате, че последният Индексът е всъщност 3. Това не е 4, въпреки че има четири стойности в масива. Така че тук, ние трябва да бъдем много внимателни от това, което ни състояние за дължината ще бъде. АУДИТОРИЯ: Няма ли да е п минус 1? АНДИ Пенг: Това ще п минус 1, точно. Това прави ли смисъл, защо това е п минус 1, всеки? Това е така, защото масиви са нулеви индексира. Те започват от 0 и тичам до п минус 1. Да, това е доста труден. ДОБРЕ. И тогава-- АУДИТОРИЯ: Isnt'1 че вече се погрижа за него все пак, чрез просто не казва "по-малка или равно на "и просто казвам" по-малко от? " АНДИ Пенг: Това е наистина добър въпрос. Така че, да. Но също така, начинът, по който сме прилагане на правото проверка, което трябва да се сравнят две стойности. Така че всъщност искате да напусне "да", когато е празна. Защото ако се сравни това, че няма има нещо, след като да се сравни с, нали? Да. Така че аз ++. Нека добавим нашите скоби инча Опа. Страхотен. Така че ние имаме началото на нашия външен контур. Така че сега ние вероятно искате да създадете променлива за водене следите на най-малката стойност, нали? Някой иска ли да ми дадеш ред код, който би направил това? Какво ни е нужно, ако отиваме да искате да съхраните нещо? Право. Може би по-добро име за това ще be-- "температура" напълно works-- Може би по-уместно наречена би било, ако искаме най-малката value-- АУДИТОРИЯ: Мин. АНДИ Пенг: мин, там да отидем. мин би било добре. И така тук, това, което правим искам да го инициализира да? Това е доста труден. Защото точно сега в началото на този масив, не сте погледна нещо, нали? И какво от това, автоматично, ако ние сме само на аз равна на 0, какво искаме да се инициализира първата ни минимална стойност да? АУДИТОРИЯ: аз. АНДИ Пенг: аз, точно. Кристабел, защо ние искаме да го инициализира да съм? АУДИТОРИЯ: Защото, добре, започваме с 0. Така че, тъй като ние нямаме нищо за сравнение да, минималните ще останат 0. АНДИ Пенг: Точно така. Така че тя е точно така. Защото ние имаме всъщност не погледна нищо все още, ние не знаем какво ни е минимална стойност. Искаме просто да го инициализира да аз, който, в момента, е точно тук. И докато ние продължаваме да се движат по този масив, ще видим, че с всяка допълнителна пас, аз инкрементира. И така, в този момент, аз вероятно ще да иска да бъде минимално, защото тя ще бъде независимо е началото на сортиран масив. Готино. Така че сега ние искаме да добавим а за цикъл тук това е ще превъртите през анализатора сортиран, или останалата част на този масив. Някой иска ли да ми дадете ред код, който би направил това? Hint-- какво имаме нужда тук? Какво се случва да отида в тази за цикъл? Да. АУДИТОРИЯ: Така че ние ще искате да имат различно число, защото сме минава през останалата на масива вместо I, така че може би к. АНДИ Пенг: Да, й звучи добре за мен. Равно на? АУДИТОРИЯ: Така ще бъде и плюс 1, защото сте се започне по време на следващата стойност. И тогава на end-- така отново, й е по-малко от N минус 1, и след това й ++. АНДИ Пенг: Great. И тогава тук, ние ще искаме да проверите дали нашето условие е изпълнено, нали? Защото искате да промяна на минималната стойност ако това е действително по-малък от това, което сте го сравни с, нали? Така че какво ще искат тук? Проверете, за да видите. Какъв вид на декларация ние вероятно ще ти искате да използвате, ако ние искам да проверя нещо? АУДИТОРИЯ: An ако изявление. АНДИ Пенг: An ако изявление. Така if-- и какво ще бъде при условие, че ние искаме вътре на нашия ако твърдение? АУДИТОРИЯ: Ако стойността на к е по-малко от стойността на i-- АНДИ Пенг: Точно така. Така if-- така че този масив се нарича "масив." Страхотен. Така че, ако array-- какво беше това? Кажи, че отново. АУДИТОРИЯ: Ако масив-й е по-малко от масив-и, а след това ние ще се промени мин. Така минималната би й. АНДИ Пенг: Това прави ли смисъл? ДОБРЕ. И сега тук, ние всъщност искат да приложат суапа, нали? Така че си спомняте, в лекция, че Давид, когато той се опитва да the-- какво е суап it-- портокалов сок и milk-- АУДИТОРИЯ: Това беше груба. АНДИ Пенг: Да, това е вид на брутния. Но това е един доста добър концепция демонстриране време. Така че мисля за вашите ценности тук. Имаш масив на мин, масив от I, или каквото и да се опитваше да сменяте тук. И най-вероятно няма да ги излее в помежду си по едно и също време, нали? Така че какво ще да се наложи да създадете тук за да сменяте стойностите правилно? АУДИТОРИЯ: A временна променлива. АНДИ Пенг: A временна променлива. Така че нека да направим инт темп. Виж, това ще бъде по-добре време to-- чакай, какво беше това? ДОБРЕ. Така че това би бил по-добър време, за да дадете име на променлива "темп." Така че нека да направим инт темп. Какво ще се Зададена темп, равен тук? АУДИТОРИЯ: Мин? АНДИ Пенг: Това е доста труден. То всъщност не е от значение в крайна сметка. Няма значение какво За да решите да сменяте в толкова дълго, колкото можете да започнете като се уверите, че сте следене на това, което смяна. АУДИТОРИЯ: Тя може да бъде масив-и. АНДИ Пенг: Да, нека да направим масив-и. И тогава какъв е следващия ред на код искаме да имаме тук? АУДИТОРИЯ: масив-и се равнява на масив-к. АНДИ Пенг: И накрая? АУДИТОРИЯ: масив-к равнява масив-и. Публика: Or масив-к равни масив-temp-- или, темп. АНДИ Пенг: OK. Така че нека да стартирате тази и виж ако то се случва да работи. Къде е това да се случва? О, това е проблем. Виж, по линия 40, ние сме се опитва да използва масив-й? Но къде й съществува само в? АУДИТОРИЯ: В за контур. АНДИ Пенг: Точно така. Така че това, което ние ще трябва да направим? АУДИТОРИЯ: тя Дефинирайте извън the-- АУДИТОРИЯ: Да, предполагам че имате да се използва друг, ако изявление, нали? Така че, както, ако minimum-- Добре, нека да помисля. АНДИ Пенг: Момчета, опитайте да погледнете Нека виж, това, което е нещо, което ние можем да направим тук? АУДИТОРИЯ: OK. Така че, ако минималната не е равно j-- така че ако минималната е все още i-- тогава ние не би трябвало да сменяте. АНДИ Пенг: Има ли, че равният аз? Какво искаш да кажеш тук? АУДИТОРИЯ: Или да, ако Минималната не е равно аз, да. АНДИ Пенг: OK. Ами, която решава, вид, нашите проблеми. Но това все още не решава проблем от това, което се случва, ако j-- тъй к не съществува извън него, това, което искаш да искаме да правим с него? Декларирам, че навън? Нека се опитаме да стартирате този. Охо. Нашият вид не работи. Както можете да видите, нашата първоначална масив имал тези ценности. И след това тя трябва да има е 1, 2, 3, 4, 5, 6, 7, 8, 9. Не работи. Ааа. И какво ще правим? АУДИТОРИЯ: Debug. АНДИ Пенг: Добре, можем да се опитаме това. Ние можем да трасира. Намаляване малко. Нека да поставим нашия точка на прекъсване. Нека да отидем like-- OK. Така че, защото ние вече знаем, че тези редове, 15, 22, чрез са working--, защото всичко, което правя е Просто итерации през и printing-- Мога да отида напред и да го пропуснем. Да започнем от линия 25. ООП, позволете ми да се отърва от това. АУДИТОРИЯ: Така че точката на прекъсване на когато започва отстраняване на грешки? АНДИ Пенг: Or спирки. АУДИТОРИЯ: Or спирки. АНДИ Пенг: Да. Можете да настроите няколко точки на прекъсване и тя може просто да скочи от единия към другия. Но в този случай ние не знаем когато грешката се случва. Така че ние просто искаме да започнете от горе на долу. Да. ДОБРЕ. Така че тази линия тук, можем да стъпка инча Можете да видите тук долу, ние имаме масив. Това са ценностите които са в масива. Виждаш ли, че, как индекс 0, то съответства на value-- о, Аз ще се опитам да я увеличите инча Съжаляваме, това е наистина трудно да see-- в индекса масив 0, ние, имат стойност от 4 и След това така нататък и така нататък. Ние имаме нашите местни променливи. Точно сега аз се равнява на 0, което искаме да бъде. И така, нека да се запази чрез засилване. Нашата минимум е равно на 0, които ние също искаме да бъде. И тогава ние влиза втората ни за линия, ако масив-й е по-малко от масив-и, което не е. Така видя ли как че пропускани, че? АУДИТОРИЯ: Така трябва, ако минимум, всички that-- не трябва, че да бъде в рамките на първата за цикъл? АНДИ Пенг: Не, защото Все още ли искате да тествате. Искаш ли да правим съпоставка всеки време, дори и след като премине през него. Вие не просто искам да го направя на първия пропускателен. Искаш ли да го направя с отново всеки допълнителен пропуск. Значи вие искате да проверите за Вашето състояние вътре. Така че ние просто ще продължи да работи през тук. Аз ще ви дам момчета намек. Това е свързано с факта, че когато вие сте си проверявате условно, не сте проверка за правилното индекс. Така че сега можете да започнете проверка за масив индекс на й е по-малко от масив индекс на аз. Но това, което правиш най началото на за цикъл? Не те ли е създаването й, равна аз? Да, така можем действително излезете дебъгер тук. Така че нека да погледнем на нашия Псевдокод. For-- ние ще започнем аз равна на 0. Отиваме да отидете до п минус 1. Нека да се провери, дали имаме това право? Да, това е бил прав. Така че след това вътре тук, ние сме Ще създадете минимална стойност и определя, че равно на аз. Знаете го направим? Да, направих това. Сега в нашата вътрешна за цикъл, ние сме ще направим й се равнява аз да п минус 1. Знаете го направим? Всъщност, ние сме го направили. Така обаче, ние какво сравняването тук? АУДИТОРИЯ: й плюс 1. АНДИ Пенг: Точно така. И тогава започваш да искате да зададете минималната си равна на к плюс 1, както добре. Така че аз отидох чрез които наистина бързо. Мислите ли разбират защо е й плюс 1? ДОБРЕ. Така че във вашия масив, в първата си атака през, Вашата за линия, за инт аз е равна на 0, нека просто Предполагам, че това все още не е променен. Ние имаме масив от, напълно, Само за четири несортиран елементи, нали? Така че ние искаме да се инициализира и да е равна на 0. И аз ще се просто тече през този цикъл. И така в първото преминаване, отиваме да инициализира променлива, наречена "мин" че да е равен I, защото ние нямаме минимална стойност. Така че това е момента, равна на 0, както добре. И тогава ние ще преминеш. И ние искаме да превъртите отново. Сега, когато сме намерили това, което нашата минимална е, ние искаме да превъртите през отново, за да се види дали това е сравняването, нали? Така че й, тук, ще на равно и, която е 0. И тогава, ако масив й плюс аз, който е този, който е в непосредствена близост над, като по-малко от това, което вашата настояща минимум стойност е, което искате да сменяте. Така че нека просто кажем, ние сме имам подобно, 2, 5, 1, 8. Точно сега, аз се равнява на 0 и к е равно на 0. И това е нашата минимална стойност. Ако масив-к плюс i-- така че ако този, това е след този, който ние не търсим най- е по-голям от този преди него, това ще стане минимум. Така че тук ние виждаме, че 5 е не по-малко от това. Така то се случва да не бъде 5. Ние виждаме, че един е по-малко от 2, нали? Така че сега ние знаем, че нашето минимум е ще бъде стойността на индекса на 0, 1, 2. Да? И тогава, когато можете да получите тук, можете да сменяте точните стойности. Така че, когато вие просто имащи J преди, ти не гледаш този, след това. Можете гледаха същата стойност, която защо просто не се прави нищо. Това прави ли смисъл за всички, Затова е необходимо, че плюс 1 до там? ДОБРЕ. Сега нека просто преминават през него, за да уверите, останалата част от кода е правилен. Защо се случва? Ах, това е минималната точно тук. Ние сравняваме грешна стойност. О, не. О, да, тук бяхме смяна погрешни стойности, както добре. Защото ние гледахме аз и к. Това са тези, които ние се проверяват. Ние всъщност искаме да сменяте минимум текущия минимум, с каквато и да е една отвън е. И тъй като вие може да видите надолу Оттук имаме сортиран масив. Той просто трябваше да направя с факта, че когато бяхме проверка на стойности бяхме сравняващи, ние не гледаха истинските ценности. Търсехме в същата тук, всъщност не го смяна. Вие трябва да погледнете този, следващия към нея, и след това можете да сменяте. Така че това е, което е вид подслушване нашия кодекс преди. И това, което направих тук е всичко, дебъгер би могъл да направи за вас Току-що го направих относно борда, защото е по-лесно да се види, а не се опитва за да увеличите дебъгер. Това прави ли смисъл на всички? Готино. Всичко е наред. Ние можем да преминем към говорим за асимптотичната нотация, която е само един луксозен начин на казвайки на Времето на автономна работа на всички тези видове. Така че аз знам, Давид, в лекция, засегна Времето на автономна работа. И той премина през цялата формула за това как да се изчислят Runtimes. Не се тревожете за това. Ако сте наистина любопитно за това как, който работи, Чувствайте се свободни да говорят с мен, след точка. Ние можем да преминете през формули заедно. Но всички вие, момчета, трябва да наистина Знам само, че п квадрат над 2 е същото като п квадрат. Тъй като най-голям брой, експонентата, расте най-много. И така, за нашите цели, всички ние се грижим за е, че гигантски номер, който се разраства. Така че това, което е най-добрия случай по време на работа на подбор подреди? Ако ще да има да превъртите през списък и след това чрез обхождане останалата част от този списък, колко пъти са Ще вероятно, в най-лошия case-- в най-добрия случай, sorry-- тече през? Може би най-добре е въпрос да попитам, какво е най-лошия случай по време на работа на подбор на сортиране. АУДИТОРИЯ: п квадрат. АНДИ Пенг: Тя е п квадрат, нали. Така че един лесен начин да се мисли за това е като, всеки път, когато има два вложени за електрически вериги, това ще бъде п квадрат. Защото не само вие сте минава през още веднъж, вие трябва да се върна около и тече през него отново вътре за всяка стойност. Така че в този случай, че работите п пъти п квадрат, което is-- съжалявам, п п пъти, което се равнява на п квадрат. И нещо като също е малко по- уникален в смисъл че това няма значение, ако те стойности вече са в ред. Тя все още продължава да тече през всеки случай. Нека просто кажем, че това е 1, 2, 3, 4. Независимо от това дали или не е било в ред, тя все още щеше да прерови и все още се проверява минималната стойност. Той би направил същия брой проверки всеки път, дори ако това е всъщност не пипай нищо. Така че в този случай, най-доброто и най-лошото Времето на автономна работа всъщност са равностойни. Така очакваното време на работа на избор на сортиране, които определят със символа на тета, тета, в този случай, също ще бъдат п квадрат. Всички три от тях ще бъдат п квадрат. Всички ли ясно защо Времето на работа се п квадрат? Всичко е наред. Така че аз съм просто ще пресипват през останалите сортове. Алгоритъмът за балон sort-- спомням, това е първият Давид мина в лекция. По същество, в който стъпка през целия списък и вие сте просто swap-- сравни две наведнъж. И ако някой е по-голяма, отколкото можете просто да ги сменяте. Така че, ако те са по-големи, ще сменяте. Имам официален точно тук. Така че нека просто кажем, сте имали 8, 6, 4, 2. Ще сравним 8 и 6. Вие ще трябва да ги разменят. Можете да сравните 8 и 4. Вие ще трябва да ги разменят. Ако се налага да сменяте 8 и на 2, да ги промени, както добре. Така че в такъв смисъл, можете да видите, разиграва в продължение на дълъг период от време, как стойности вида на балон, за да краищата, което е защо ние го наричат метод на мехурчето. Ние просто ще минава през отново вторият ни пас, а третият ни пас, и нашето четвърто пас. По същество, метод на мехурчето просто минава докато не направите повече суапове. Така че в този смисъл, това е просто широката Псевдокод за него. Не се тревожете, те всички ще бъдат на линия. Ние не трябва да всъщност разясни това. Ние просто се инициализира брояч променлива, която започва при 0. И ние превъртите през целия масив. И ако една стойност, ако това is-- стойност е по-голяма от тази стойност, започваш да ги разменят. И тогава ти си просто ще продължи да функционира. И ти започваш да се разчита. И вие просто ще продължаваш да правиш това, докато броячът е по-голяма от 0, което означава, че всеки път, когато се наложи да сменяте, Знаете ли, че искате да отидете назад и проверете отново. Вие искате да запазите проверка, докато не разберете че не е нужно да сменяте вече. Така че това, което са най-добрите и най-лошите При Runtimes за метод на мехурчето? И hint-- това всъщност е различно от селекция подредени в смисъл, че тези две отговори не са еднакви. Помислете за това, което ще се случи в случай, ако е бил вече сортирани. И мисля за това, ще се случи, ако беше в случая, в който той не е бил сортиран. И вие можете да стартирате вид чрез защо това се случва. Аз ще ви дам момчета, като, 30 секунди, за да мислят за това. ДОБРЕ. Някой има ли предположение какво най-лошия случай по време на работа на метод на мехурчето е? Да. АУДИТОРИЯ: Би ли било, като, п пъти п минус 1 или нещо подобно? Както всеки път, когато той работи, това е просто, като, един суап-малко че каквото и да е било. АНДИ Пенг: Да, така ти си напълно прав. И това е случай, в който си Отговорът всъщност е по-сложна от тази, която трябва да дадем. Така че това ще run-- съм ще изтрие всичко това тук. Всички ли добър? Мога ли да залича това? ДОБРЕ. Ще преминете през п пъти първия път, нали? И те започват да преминават през п минус 1 втори път, нали? И тогава започваш да се запази ще, п мина 2, и така нататък. Давид стори това в лекция, в която, Ако сте добавили до всички тези ценности, можете да получите нещо, което е like-- yeah-- над 2, които по същество просто намалява до п квадрат. Вие ще получите странно фракция там. И така, просто знам, че п квадрат винаги има предимство пред фракцията. И така, в този случай, най-лошото по време на работа ще бъде п квадрат. Ако това беше в низходящ ред, мисля, вие Трябва да се направи суап всеки един момент. Какво би било, потенциално, най-добрия случай Времетраене? Нека просто кажем, ако списъкът е вече , за това, което ще бъде време на работа? АУДИТОРИЯ: п. АНДИ Пенг: Това е п, точно. И защо е п? АУДИТОРИЯ: Защото вие просто трябва да се провери за всеки един път. АНДИ Пенг: Точно така. Така че в най-добрия възможен време на работа, ако този списък вече беше sorted-- да речем 1, 2, 3, 4-- ви Просто ще преминем, ще покажат, вие ще видите, о, всички те успявам. Аз не се наложи да сменяте. Приключих. Така че в този случай, това е просто п или броя на стъпките, които просто Трябваше да се провери в първия списък. И след това, ние сега се удари сортиране чрез вмъкване, където алгоритъмът е по същество да се разделят то в сортиран и сортиран порция. И след това един по един, на несортиран стойности са вмъква в тяхната целесъобразност позиции в началото на списъка. Така например, ние имаме Списък на 3, 5, 2, 6, 4 отново. Ние знаем, че това е в момента сортиран, защото ние току-що Започнах да търся в него. Ние да разгледаме и да знаем, че първата стойност се сортира, нали? Ако сте само погледнете в масив от Размер на един, вие знаете, че това е сортирани. Така че след това ние знаем, че Другите четири са неразделени. Ние проверете и ние виждаме, че стойност. Нека се върнем. Виж, че стойността на 5? Ние да разгледаме това. Ние го сравни с 3. Ние знаем, че това е по-голямо от 3, така че ние знаем, че това е сортирани. Така че ние вече знаем, че първите две са подредени, а последните три не са. Ние да разгледаме 2. Ние първо да го проверите с 5. Дали е по-малко от 5? Не е. Така че ние трябва да продължим да гледа надолу. Тогава сте проверили 2 на разстояние 3. Дали е по-малко от? Не. Така ли, че на 2 трябва да бъде поставена в предната и 3 и 5 и двамата трябва да се избута. Направете това отново с 6 и 4. И ние просто да продължите да следите по същество, където ние просто проверете, проверка, проверка. И докато тя е в правото позиция, ние просто вид поставете го в правилната позиция, което е мястото, където името му идва от. Така че това е само алгоритъм, Псевдокод по себе си, нещо, за това как бихме приложат вмъкване на сортиране. Псевдокод е тук. Всичко е на линия. Не се тревожете, ако вие се се опитва да копира това надолу. Така че още веднъж, същото question-- какво ще бъде най-добрият и най-лошите Runtimes за сортиране чрез вмъкване? Това е много подобен на последния въпрос. Аз ще ви дам момчета, като, 30 секунди, за да мислят за това, както добре. OK Някой иска да дайте ми най-лошото време на работа? Да. АУДИТОРИЯ: п квадрат. АНДИ Пенг: Тя е п квадрат. И защо е п квадрат? АУДИТОРИЯ: Защото в обратен ред, имате да мине през п пъти п, които is-- АНДИ Пенг: Да, точно така. Така че едно и също нещо, както е в нещо като балон. Ако този списък е в низходящ ред, вие сте ще трябва да се провери първо веднъж. И след това с всеки допълнителна стойност, вие сте Ще трябва да го проверите срещу всяка една стойност, нали? И така напълно, ти започваш да се направи един пъти п мине друг п минават, които п е квадрат. Какво ще кажете за най-добрия случай? Да. АУДИТОРИЯ: п минус 1, тъй като на Първият е вече на квадрат. АНДИ Пенг: Така че, в близост. Отговорът всъщност е п. Тъй докато първият е сортирани, той не може да го actually-- ние просто късмет, в че например, че 2 се случи да бъде най-малкият брой. Но това не винаги е така. Ако вече е 2 сортирани в началото но вие изглеждате и да има едно тук, за 1 ще го избутам. И това се случва до края сметка се блъсна във всеки случай. Така че в най-добрия случай, това е всъщност просто ще бъде п. Ако имате 1, 2, 3, 4, 5, 6, 7, 8, вие сте Ще преминете през че целият списък веднъж да проверите дали всичко е наред. Всички ли ясна по бягане времена на избор, както и? Знам, че преживява те много по-бързо. Но просто знам, че ако знаете общи понятия, трябва да бъдат добри. ДОБРЕ. Така че аз просто ще ви дам момчета може би, като, една минута, за да говорите с вашите съседи от това, което са само част от основните разлики между тези видове сортове. Ние ще отидем, че скоро. АУДИТОРИЯ: О, OK. АНДИ Пенг: Да. ДОБРЕ. Cool, нека да бъдат свикани отново като класа. ДОБРЕ. Така че това е вид на отворен въпрос, в смисъл, че има много отговори на тях. И ние ще отидем някои от тях за кратко. Аз просто исках да получавате момчета мисля за това, което диференцира всичките три вида сортове. И аз чух, също Страхотен question-- какво сортиране чрез сливане направя? Голям въпрос, защото това е това, което ние, обхващащ следващата. Така сортиране чрез сливане е един вид, че функции много по-различно от останалите сортове. Както вие може да see-- Давид направи това демо където имаше всичко прохладата шумове на виждам как се слеят подреди избяга, като, безкрайно по-бързо от другите два вида? ДОБРЕ. Така че това е, защото се сливат подреди изпълнява посочената разделяй и владей концепция, която ние сме Говорихме за много в лекция. В този смисъл, че сме искали да работят по-умни, по-трудно, когато се разделят и владей проблеми, и да ги разбие надолу, а след това ги съберете заедно, добри неща винаги се случват. Така че начинът, по който се слеят подреди по същество работи е, че тя се разделя на сортиран масив на половина. И тогава тя има две половини на масиви. И тя просто сортира тези две половини. Тя просто продължава да се раздели на две, в половината, на половина, докато всичко се сортира и след това рекурсивно всичко това поставя заедно. Така че това е наистина абстрактно. Така че това е само малко Псевдокод. Това прави ли смисъл в Между другото той се движи? Така че нека просто кажем, че имате масив от наш елементи, нали? Ако п е по-малко от 2, можете да се върнете. Защото знаеш, че ако има само едно нещо, то трябва да бъдат сортирани. Else, можете сортирате лявата половина, и тогава да сортирате дясната половина, и тогава ще се слеят. Така че, докато, който изглежда много лесно, в действителност, мисля за това е вид трудно. Защото сте като, Е, това е вид работа върху себе си. Нали така? Тя работи върху себе си. Така че в този смисъл, David докосна при рекурсия в клас. И това е една концепция ние ще говорим за повече. Това е, че това, тези две линии тук, всъщност е само програмата го казвам, за да се стартира с различен вход. Така че вместо да се работи с целостта на N елементи, можете да го съборят в лявата половина и дясната половина и след това да го стартирате отново. И тогава ние ще разгледаме това визуално, защото аз съм визуален обучаем. Тя работи по-добре за мен. Така че ние ще разгледаме визуален пример тук. Да кажем, че имаме масив, шест елементи, 3, 5, 2, 6, 4, 1, не сортирани. Добре, че има много на тази страница. Така че, ако вие може да погледнете в първа стъпка тук, 3, 5, 2, 6, 4, 1, можете да го разделя на две. Имате 3, 5, 2, 6, 4, 1. Вие знаете, че тези реакции Ви aren't-- не знам дали те са подредени или не, така че можете да ги счупи, на половина, наполовина, в половината, докато накрая, имате само един елемент. И един елемент е винаги подредени, нали? Така че ние знаем, че 3, 5, 2, 4, 6, 1, сами по себе си, са подредени. И сега ние можем да ги пуснат обратно заедно. Така че ние знаем за 3, 5. Ние събрахме онези заедно. Ние знаем, че е сортиран. На 2-те години все още там. Можем да сложим на 4 и 6 заедно. Ние знаем, че това е сортирана, така че ние се сложи това заедно. И за 1 е там. И след това просто погледнете тези две половини тук. Имате 3, 5, 2, 2, 3, 5. Можете просто да се сравни започващ от всичко. Защото вие знаете, че това се сортира и вие знаете, че това е сортирани. Така че тогава вие дори не трябва да се сравни 5, просто сравнение на 3. И 2 е по-малко от 3, така че Знаете ли, че 2 трябва да отиде в края. Същото нещо там. 1 трябва да отидете тук. И тогава, когато отидеш да се сложи тези две стойности заедно, вие знаете, че това се сортира и знаете ли, че, които се сортират. Така че след това 1 и 2, за 1 е по-малко от 2. Това ви казва, че за 1 трябва да отидете на края на тази без дори да гледа 3 или 5. И тогава на 4, може просто да провери, той минава точно тук. Вие не трябва да се търси при 5. Същото е и с 6. Вие знаете, че той просто 6-- не трябва да бъдат разглеждани. И така, по този начин, вие сте Просто спестяване себе си много стъпки, когато сте се сравняват. Не е нужно да сравнявате всеки елемент срещу други елементи. Ти просто сравнение с тези, че трябва да го сравня с. Така че това е вид абстрактно понятие. Не се тревожете, ако това не е доста ви удари десния все още. Но обикновено, това е как се сливат подреди работи. Въпроси, бързи въпроса, преди да се премине? Да. АУДИТОРИЯ: Значи вие казахте, че сте приели на 1, а след това 4 и 6 и ги поставя инча Така че не сме those-- са не можете да ги погледне като отделни елементи, а не като цяла? АНДИ Пенг: Да. Така че това, което се случва е, че в общи линии създавате чисто нов масив. Така че вие ​​знаете, че, ето, аз имам два масива с размер 3, нали? Така че вие ​​знаете, че ми сортиран масив трябва да разполага с шест елемента. Така че можете просто да се създаде ново количество памет. Значи вие сте нещо като е разточителство на паметта, но това не е от значение защото това е толкова малка. Така се вгледате в 1 и се вгледате в 2. И знаете ли, че 1 е по-малко от 2. Така че вие ​​знаете, че трябва да отиде в 1 началото на всички тези. Ти дори не трябва да се Посетете 3 и 5. Така ли, че един отива там. Тогава вие основно отсечем за 1. Това е, като, мъртъв за нас. Тогава ние просто трябва 2, 3, 5, и след това 4 и 6. И тогава знаете, че можете Сравняване на 4 и 2, о, на 2 трябва да отида там. Така че можете плясване на 2 надолу, можете да го отреже. Тогава просто трябва 3 и 5 в 4 и 6. А ти само да го отсече докато не ги сложи в масива. АУДИТОРИЯ: Значи вие сте просто винаги сравняване на [недоловим]? АНДИ Пенг: Точно така. Така че в този смисъл, вие сте Просто сравняване, по същество, един брой срещу друг номер. И тъй като вие знаете че това е сортирана, можете не е нужно да търсите чрез всички номера. Ти просто трябва да погледнете на първата. И след това може просто плясване да ги надолу, защото знаеш, те принадлежат, където те трябва да принадлежат. Да. Добър въпрос. И тогава, ако някой от вас са малко амбициозни, Чувствайте се свободни да погледнете този кодекс. Това е всъщност най- физическо изпълнение за това как ние ще напише сортиране чрез сливане. И можете да видите, че е много кратък. Но идеите зад това са доста сложни. Така че, ако се чувстваш като изготвянето на този във вашата домашна работа тази вечер, не се колебайте да. ДОБРЕ. Така Давид отиде в тази лекция. Какви са най-добрия случай Времето на автономна работа, най-лошия случай Времето на автономна работа, и очакваните Runtimes на сортиране чрез сливане? Няколко секунди, за да мислят. Това е доста трудно, но вид интуитивно, ако си мислиш за него. Всичко е наред. АУДИТОРИЯ: Дали най-лошия случай п дневник п? АНДИ Пенг: Точно така. И защо е п влезте п. АУДИТОРИЯ: Не е ли защото тя експоненциално става по-бързо, така че това е като функция на това вместо просто да бъде п квадрат или нещо такова? АНДИ Пенг: Точно така. Така че причината, поради която по време на работа по този въпрос е п дневник п е because-- това, което са прави във всички тези стъпки? Вие просто го кълцане на половина, нали? И така, когато Правим влезте, всичко, което го прави се раздели проблем на половина, наполовина, в половината, в повече половини. И в този смисъл, можете да вид на премахване на линеен модел че ние сме били използвате. Защото, когато посегнат неща в половината, това е дневник. Това е само математическата начин да го представлява. И накрая, в края, ти си просто направи едно последно атака през да постави всички от тях, с цел, нали? И така, ако сте просто трябва да проверите едно нещо, това е п. И така, вие сте вид умножаване двете заедно. Така че това е като да имаш, че окончателното проверите за п тук долу с дневника на п тук. И ако се размножават тях, която е п влезте п. И така най-добрия случай и най-лошото случай и очаква всички са п влезте п. То също е като друг вид. Това е като избор на сортиране в смисъл, че Няма значение какъв е вашият списък е, тя просто ще да направи същото нещо всеки път. ДОБРЕ. Така че, както вие може да видите, въпреки че сортовете, че сме отишли ​​through-- п квадрат, това не е много ефективен. И дори това п дневник п е не най-ефективно. Ако вие, момчета са любопитни, там е един вид механизми които са толкова ефективна, че те са почти основно жилище в изпълнение. Имаш някои дневник п е. Имаш някои дневник дневник п е. Ние не се докоснете до тях в този клас в момента. Но ако вие са любопитни, Чувствайте се свободни да Google, това, което е най-ефективните сортиране механизми. Аз не знам, има някои наистина смешни такива, like-- има някои наистина смешни тези, които хората правят. И ти се чудя как те някога мисълта за това. Така Google, ако имате някои резервни време, за това, което са някои забавни начини че people-- както и ефикасни ways-- хората са били в състояние да приложат различни. ДОБРЕ. И тук е просто удобен малък диаграма. Знам, че всички от вас, преди тази викторина 0, ще бъде в стаята си, вероятно опитвайки да запомня това. Така че това е хубаво там за вас, момчета. Само не забравяйте, че логиката made-- защо тези номера бяха срещащи. Ако винаги сте загубили, просто се сигурни, че знаете какво сортовете са. И вие можете да преминете през ги в ума си да разбера защо тези, отговори са тези отговори. Всичко е наред. Така че ние ще се движат на последно място, да се търсене. Тъй като тези от вас, които са чели pset, търсене също е част от проблем тази седмица задава. Вие ще бъдете помолени да приложи два вида търсения. Един от тях е линеен търсене и един е двоичен търсене. Така че линейната търсенето е сравнително лесно. Вие просто искате да търсите елемент на списък, за да видите дали можете да го получи. Просто трябва да превъртите през. И ако това се равнява на нещо, може просто да го върне, нали? Но този, който ние сме най- интересуват от говорим за е двоично търсене, полето, което е най- разделяй и владей механизъм, който Дейвид се демонстрира в лекция. Не забравяйте примера на телефонния указател че той продължава отглеждането, този, който той вид бореше малко по последната година, където можете да раздели проблема на половина, на половина, на половина, отново и отново, докато не намерите това, което търсите? И имаш време на изпълнение на това, както добре. И можете да видите, че е значително по-ефективно от всеки друг вид търсене. Така че начинът, по който ние ще отида за прилагане двоичен търсене е, ако имахме масив, индекс от 0 до 6, седем елементи, ние можем да погледнем в средата, right-- Съжалявам, ако ни въпрос first-- ако искаме да зададем въпроса на, прави масива съдържа елемент 7, Очевидно е, че са хора, и като такъв малък масив, това е лесно за нас да се каже, да. Но начинът за прилагане на двоичен търсене е да се погледне в центъра. Ние знаем, че индексът е 3 средата, защото ние знаем, че има седем елемента. Какво 7 разделена на 2? Можете да отсечем, че допълнително 1. Имаш 3 в средата. Така че е набор от 3 равна на 7? Не е правилно? Но ние можем да направим няколко проверки. Е набор от 3 или по-малко от 7 е масив от 3-голяма от 7? И ние знаем, че това е по-малко от 7. Така че ние знаем, че, о, тя трябва не е в лявата половина. Ние знаем, че тя трябва да бъде в дясната половина, нали? Така че ние можем просто да отреже половината от масива. Ние дори не трябва да се гледам на него вече. Защото ние знаем, че половината от нашия problem-- ние знаем, че отговорът е в дясната половина на нашия проблем. Така че ние просто погледнете това сега. Така че сега погледнем средата на това, което е останало. Това индекс 5. Ние правим едно и също проверката отново и ние виждаме, че това е по-малък. Така че ние с нетърпение в ляво от това. И тогава ние виждаме, че проверка. Е стойността на масив в индекс 4, равен на 7? То е. Така че можем да се върнем вярно, защото ние открихме, че стойността в нашия списък. Дали начинът, минах през които имат смисъл за всички? ДОБРЕ. Аз ще ви дам момчета може би, като, три, четири минути, за да разбера как да Псевдокод този инча Така че представете си те помолих да напише функция, наречена търсене (), който се завръща на стойност, булева стойност, това беше вярно или false-- харесват, вярно, ако сте намерили стойност, невярно, ако не го направи. И тогава бяхте преминали в стойността, която търсите в стойности, които е array-- о, аз определено сложи че на грешното място. ДОБРЕ. Както и да е, че трябва да има бил в правото на ценности. След това междинно съединение п е броя на елементи в тази масив. Как бихте отишли ​​за опитват да Псевдокод, че проблем в? Аз ще ви дам хора като три минути, за да направите това. Не, аз мисля, че има only-- Да, има един чак до тук. АУДИТОРИЯ: Мога ли? АНДИ Пенг: Да, имам теб. Е, че работната? ОК готино. ДОБРЕ. Добре момчета, ние сме ще го обуздае инча ДОБРЕ. Така се предположи, че имаме тази прекрасна Малко масив с п ценности в него. Аз не направил линиите. Но как ще отида за опитвайки се да напиша това? Някой иска да дай ми на първия ред? Ако искате да ми дадете първа линия на този Псевдокод. АУДИТОРИЯ: [недоловим] АУДИТОРИЯ: Вие ще искате да превъртите through-- АУДИТОРИЯ: Просто още за цикъл? АУДИТОРИЯ: --for. АНДИ Пенг: Така че това е един доста труден. Помислете about-- искате продължава да работи, този цикъл отново и отново, докато, когато? АУДИТОРИЯ: До [недоловим] стойност е равна на тази стойност. АНДИ Пенг: Точно така. Така че всъщност можете да просто write-- ние дори може да го опрости повече. Ние можем просто да се направи линия, докато, нали? Така че можете да просто трябва loop-- ние знаем, че това е малко. Но за сега, аз ще съм да се каже, "контур" - чрез това, което? Loop until-- това, което е нашата приключва състояние? Мисля, че го чух. Чух някой да го каже. Публика: Стойностите се равнява на средната. АНДИ Пенг: Кажи го отново. АУДИТОРИЯ: Или, до стойност, които търсите е равен на средната стойност. АНДИ Пенг: Какво става, ако то не е там? Какво става, ако стойността, които търсите не е всъщност в този масив? АУДИТОРИЯ: Ще се върнете 1. АНДИ Пенг: Но това, което искаме да линия, докато ако имаме състояние? Да. АУДИТОРИЯ: До има само едно качество? АНДИ Пенг: Можете линия until-- така че знам, че ти си ще имат стойност макс, нали? И знаеш ли, че ти започваш да имат стойност мин, нали? Тъй също, че е нещо, Забравих да кажа, преди, че нещо, което е критична за двоично търсене е, че вашият масив е вече сортирани. Защото няма начин за правене това, ако те са просто случайни стойности. Ти не знаеш, ако един е голяма от другата, нали? Така че вие ​​знаете, че вашето макс и Вашите минути са тук, нали? Ако ти започваш да се коригиране Вашата макс във вашите минути и mid-- нека просто приемем Вашата средата на стойност не е прав here-- започваш да се основно линия до минималната си е почти същото като вашето макс, нали, или ако вашият макс не е същото като вашето мин. Нали така? Защото, когато това се случи, вие знаете, че в крайна сметка съм удари една и съща стойност. Значи вие искате да линия до вашата мин е по-малка от или равна to-- Опа, не по-малко от или равно на, по друг начин around-- макс е. Знаете, че да има смисъл? Взех няколко опита, за да получите това право. Но цикъл, докато си макс стойност е по-малко по същество почти малка или равна на минималната си, нали? Това е, когато знаеш, че сте се сближили. АУДИТОРИЯ: Кога бихте си за максимална стойност е по-малко от минимума? АНДИ Пенг: Ако държите като го коригира, които е това, което ние ще да се прави в тази посока. Това прави ли смисъл? Минимален и максимален са само числа, че ние сме най-вероятно ще искате да създадете, за да следите къде ние не търсим. Тъй като съществува масива независимо от това, което правим. Подобно, не сме всъщност физически отсичайки масива, нали? Ние просто адаптиране където ние не търсим. Това прави ли смисъл? АУДИТОРИЯ: Да. АНДИ Пенг: OK. Така че, ако това е условието за нашата линия, какво искаме вътре в този цикъл? Какво ще се иска да направя? Така че в момента, ние имаме макс и мин, нали, Вероятно е създаден тук някъде. Отиваме да вероятно ще пожелаете да се намери средата, нали? Как ще да е може да се намери в средата? Каква е mathematical-- АУДИТОРИЯ: Макс плюс минути, разделени на две. АНДИ Пенг: Точно така. Това прави ли смисъл? И знаете вие, момчета, да видят защо ние не само use-- защо ние направихме това вместо да правиш точно п разделена на 2? Това е така, защото п е на стойност че ще останат същите. Нали така? Но тъй като ние се коригира нашата минимална и максимални стойности, те ще се променят. И като резултат, нашата средна няма да се промени също. Така че това е защо ние искаме да се направи това точно тук. ДОБРЕ. И тогава, сега, ние открихме our-- да. АУДИТОРИЯ: Само един бърз question-- когато казвате мин и макс, се предполага, че ние тя вече сортирани? АНДИ Пенг: Да, това е всъщност предпоставка за двоично търсене, че трябва да се знае, че е сортирани. Ето защо сортиране, пишете във вашия проблем поставената пред вашия двоично търсене. ДОБРЕ. Така че сега ние знаем къде нашата средна точка е, какво искаш да правим тук? АУДИТОРИЯ: Искаме да сравнявате че на другия. АНДИ Пенг: Точно така. Така че ти започваш да се сравни средата на стойност, нали? И какво значи това кажи нас, когато сравнявате? Какво искаме да правим след това? АУДИТОРИЯ: Ако стойността е по-голям от средата, искаме да го прекъсна. АНДИ Пенг: Точно така. Така че, ако стойността е по-голям от средата, ние сме ще искате да ги промените минимум и maxes, нали? Какво искаме да се промени? Така че, ако ние знаем стойността е някъде тук, това, което правите, ние да се промени? Ние искаме да променим минимум, за да бъде средата, нали? И после друго, ако това е в този половината, какво искаме да се промени? АУДИТОРИЯ: Вашият максимум. АНДИ Пенг: Да. И след това просто ще да запази примка, нали? Защото сега, след една итерация чрез, имаш макс тук. И тогава може да се преизчисли в средата. И тогава ще може да се сравни. И ти започваш да продължава напред докато минути и maxes са по същество се сближили. И това е, когато знаеш, че сте се удари в края на това. И двете сте го намерили или не сте в този момент. Прави ли това чувство на всички? ДОБРЕ. Това е доста важно, защото ще имате да напиша това в кода си тази вечер. Но вие имате доста добър усещане за това какво трябва да се прави, кое е добре. ДОБРЕ. Така че ние имаме около седем минути преди края раздел. Така че ние ще говорим за това pset, че ние ще се прави. Така pset е разделена на две половини. Първото полувреме включва прилагане на находката , на който пишете линейно търсене, а двоично търсене и сортиране алгоритъм. Така че това е първият време в pset където ние ще бъдем като вас, момчета, което се нарича код разпределение, което е код че сме предварително писмено, но просто остави някои части на разстояние за вас, за да продължи писмена форма. Така че вие, момчета, когато се вгледате в тази код, може да получите наистина уплашен. Ако сте просто искал, Ааа, аз не знам какво, че се справя, Аз не знам, като, че изглежда толкова сложно, Ааа, да се отпуснете. ОК е. Прочетете спец. Спецификацията ще ви обясня точно това, което всички тези програми са прави. Например, generate.c е програма че ще дойде с вашия pset. Вие всъщност не трябва да го докосне, но трябва да се разбере това, което прави. И generate.c, всичко, което прави, е или генериране на случайни числа или може да го даде на семена, като предварително определени номера, че са необходими, и тя генерира повече номера. Така че има специфичен начин за приложат generate.c, в която може просто да направи един куп номера за да можете да тествате вашите други методи на. Така че, ако искате да, за Например, тества вашата находка, вие ще искате да стартирате generate.c, генерира един куп номера, и след това пуснете си помощници функция. Вашият помощници функция е мястото, където сте всъщност физически пишете код. И мисля, че на помощници като библиотека файл пишеш, че находката се обажда. И така, в рамките на helpers.c, ще направите търсене и сортиране. И тогава започваш да се същество Просто всички тях, взети заедно. Спецификацията ще ви кажа как да сложи това в командния ред. И вие ще бъдете в състояние да се тества дали Не си вид и търсене работим. Готино. Вече започна и всеки, срещани проблеми или въпроси те имат точно сега с това? ДОБРЕ. АУДИТОРИЯ: Изчакайте. Имам въпрос. АНДИ Пенг: Да. АУДИТОРИЯ: Така че аз започнах да правя търсачката линейна в helpers.c и това не е наистина работи. Но след това по-късно разбрах, че ние просто трябва да го изтриете и да направим двоичен търсене. Така че това е от значение, ако тя не работи? АНДИ Пенг: Кратък отговор е не. Но тъй като ние сме not-- АУДИТОРИЯ: Но никой не е фактическа проверка. АНДИ Пенг: Ние никога не сме Ще видите, че. Но вие може би искате да направите сигурен търсенето си работи. Защото ако си линейна търсене не работи, тогава шансовете са ви двоичен търсене няма да работи, както добре. Защото имате подобна логика в двете. И не, това няма значение. Така единствените, които ще се превърнат в са подредени и двоично търсене. Да. И също така, много от децата са били опитвайки се да се съберат helpers.c. Вие не сте действително оставя да направи това, защото helpers.c не разполага с основна функция. И така, вие само трябва да да бъде действително съставянето генерират и да се намери, защото намерите повиквания helpers.c и функциите в него. Така, че прави грешки трън в задника. Но това е, което трябва да направим. АУДИТОРИЯ: Ти просто направи всичко, нали? АНДИ Пенг: Можете просто направи всичко, както, да. ДОБРЕ. Така, че това е от гледна точка на това, което на pset иска всички да се направи. Ако имате някакви въпроси, не се колебайте свободни да ме питате, след точка. Аз ще бъда тук за подобно, на 20 минути. И да, pset на наистина не е толкова зле. Вие, момчета, трябва да се оправи. Те, просто следвайте указанията. Вид на имате чувство за логично, това, което трябва да се случва и ще се оправи. Не бъдете прекалено уплашен. Има много код вече написано там. Не бъдете прекалено уплашена, ако не разбере какво означава всичко това. Ако това е много, това е напълно наред. И дойде в работно време. Ние ще ви помогне да погледнете. АУДИТОРИЯ: С допълнителната функции, да погледнем тези нагоре? АНДИ Пенг: Да, тези, които са в кода. В началото на срещата от 15, половината от той вече е написана за вас. Така че тези функции са вече в кода. Да. Всичко е наред. Е, най-доброто от късмет. Това е отвратително ден. Така че да се надяваме вие, момчета, не се чувстват твърде лошо за пребиваващи в и кодиране.