[Грає музика] 

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

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

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

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

Стиль був на момент крім кількох зауважень. Переконайтеся, що ви завжди Коментуючи свій код. Але ваші psets були на точці. І тримати його. І це добре для грейдера в бачити, що ви, хлопці, покласти як багато зусиль у вашому стилі і ваш дизайн в коді що ми хотіли б, щоб ви бачите. Так я передаю по моєї вдячності для решти ТП. 

Однак є Кілька питань танто Я просто хочу, щоб перейти на що як би життя і багато іншого ТП «живе трохи легше. По-перше, я помітив це повз week-- як багато з вас були працює на check50 код, перш ніж представити? ДОБРЕ. Таким чином, кожен повинен робити check50, because-- secret-- ми насправді запустити check50 як частина нашої правоті скрипти для тестування коду. Так що, якщо ваш код не вдається check50, цілком ймовірно, це, ймовірно, буде потерпіти невдачу також наш чек. Іноді ви, хлопці, є правильні відповіді. Мовляв, в жадібні, деякі з у вас є правильні цифри, Ви просто роздрукувати деякі додаткові речі. І, що додатковий матеріал насправді не проходить перевірку, бо комп'ютер не знаю, що він шукає. І так буде просто запустити через, бачити, що ваш висновок не відповідає тому, що ми очікуємо відповідь бути, і відзначте, що це неправильно. 

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

Крім того, в psets за п'ятницях опівдні. Я думаю, що є сім хвилин в кінці пільгового періоду, що ми даємо вам. За час Гарвардського, вони дозволили сім хвилин пізно, щоб всім. Так от в Єльському університеті, ми будемо дотримуватися, що добре. Але досить багато, в 12:07, якщо ваш PSET це не в тому, це буде відзначений як пізно. І тому, хоча вона відзначається а пізно, я TA-- раніше буде класифікації ваші psets. Таким чином, ви все ще будете бачити сорт з'являються. Проте, відомо, що в кінець семестру, всі пізні psets буде просто автоматично обнуляється за допомогою комп'ютера. 

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

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

АУДИТОРІЯ: Ви сказали, ми може впасти один з psets? 

ANDI Пен: Так. Так що загалом дев'ять psets протягом семестру. І якщо у вас є область points-- так просто сфера, досить багато, ви спробою виконання Проблема, ви покласти в час, ви показуєте, що ви маєте продемонстрували ви читали специфікації. Це досить багато можливостей. І якщо ви виконуєте Сфера точки, ми може впасти найнижча одним з повному обсязі. Так от у ваших інтересах, щоб заповнити та спробувати все PSET. 

Навіть якщо upload-- жоден з їм працювати, завантажувати їх усі. І тоді ми будемо, ми сподіваємося, зможуть дати вам деякі з цих точок назад. Прохолодний. Будь-які інші питання? Відмінно. 

По-друге, офіс hours-- кілька швидкі замітки про робочих годин. Отже, спочатку приходять на початку тижня. Ніхто не коли-небудь в Прийомні години по понеділках. Christabel прийшли до Прийомні години минулої ночі. Так, Christabel. І що ми маємо в офісі годин минулої ночі, Christabel? 

АУДИТОРІЯ: У нас було морозиво. 

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

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

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

Так вікторини 0 буде 14 жовтня, якщо Ви знаходитесь у розділі понеділок-середу і 15 жовтня, якщо ви перебуваєте в розділ вівторок-четвер. Це не поширюється на тих з вас, в Гарварді who-- Я думаю, ви всі будете приймати ваші опитування на 14-му. 

Так що, так, наступного тижня, якщо Девід, в лекції, йде, да, так про це Тест на наступному тижні, ви все НЕ будуть шоковані, бо ви прийшли в розділі і ви знаєте, що ваш Тест 0 протягом двох тижнів. І ми будемо мати відгук сесій і все. Так що не турбуйтеся про боятися за це. Будь-які питання before-- які-небудь питання на всіх стосуються технічних питань, класифікації, офісна годин, секції? Так. 

АУДИТОРІЯ: Так вікторини буде на лекції? 

ANDI Пен: Так. Так вікторини, я думаю, 60 хвилин, виділені цього часовому інтервалі що ви будете просто взяти в лекційному залі. Таким чином, ви не повинні прийти в на, начебто, випадкового 7:00 PM. Це все добре. Так. Прохолодний. 

Добре. Отже, ми збираємося, щоб ввести поняття для вас На цьому тижні, що Девід вже начебто з торкнулися в лекції минулого тижня. Це називається GDB. І, як багато з вас, в той час як в курс написання psets, помітив велику кнопку, яка говорить "Налагодження" на верхній частині IDE? ДОБРЕ. Так що тепер ми насправді отримати, щоб розкопати таємниця какой то кнопки насправді робить. І я гарантую вам, що це красива, красива річ. 

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

Таким чином, ми будемо робити приклад це пізніше. Таким чином, це здається трохи абстрактним. Не турбуйтеся, ми не будемо робити приклади. І так, по суті, три найбільших, Найбільш використовувані функції вам потрібно в GDB є Далі, переступити і крок в кнопки. Я збираюся очолити Тобто, насправді, просто зараз. 

Так може ви, хлопці, все бачити, що або я повинен збільшити трохи? У спину, ви можете бачити, що? Чи повинен я збільшити? Лише трохи? ОК здорово. Там ми йдемо. ДОБРЕ. 

Так що я, от, моя Реалізація для жадібний. І в той час як багато хто з вас, хлопці писали жадібні в той час як петлі form--, що це цілком прийнятно спосіб зробити it-- інший спосіб зробити це, щоб просто розділити на модулю. Бо тоді ви можете мати свій значення, а потім мати свій залишок. І тоді ви можете просто додати все це разом. Лі логіка, що я роблю тут сенс для всіх, перш ніж ми почнемо? Типу? Прохолодний. Відмінно. Це досить сексуальна частина коду, я б сказав. Як я вже сказав, Давид, в лекції, через деякий час, ви все починаєте бачити код як щось, що красиво. І іноді, коли ви бачите красивий Код, це такий чудовий відчуття. 

Так, однак, в той час як цей код дуже красиво, це не працює належним чином. Так що давайте працювати check50 на цьому. Перевірте 50 20-- уп. 2? Це pset2? Так. О, pset1. ДОБРЕ. Таким чином, ми працювати check50. 

І, як ви, хлопці, можете подивитися тут, це нездатність пару випадків. І для деяких з вас, в Звичайно робити свої проблемні набори, ви, як, ах, чому воно не працює. Чому це працює для деяких значення, але не для інших? Ну, GDB буде допомогти вам зрозуміти чому ці входи не працювали. 

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

Скільки прочитується? Давайте зробимо 0.41. І так, ми бачимо тут що це висновок 3 коли правильну відповідь, Справді, має бути 4. Так що давайте ввести GDB і подивитися, як ми може йти про фіксацію цієї проблеми. 

Отже, перший крок в завжди налагодження коду це встановити точку зупину, або точка, в якій ви хочу комп'ютера або відладчик, щоб почати дивитися. Так що, якщо ви дійсно не знаю, що ваша проблема, Зазвичай, типовий, що ми хочемо, щоб зробити, це встановити точку зупину на наш основний. Так що, якщо ви, хлопці, можете бачити це червона кнопка поруч, Так, це було мені встановивши зупину для головної функції. Я натисніть що. 

І тоді я можу піти до моєї кнопки Debug. Я вдарив цю кнопку. Дозвольте мені віддалитися, якщо я можу. Там ми йдемо. Таким чином, ми маємо тут, панель праворуч. Я перепрошую, хлопці в спину, ви не можу бачити дуже добре. Але по суті, все це право панель робить є відстеження і виділений лінія, яка є рядок коду що комп'ютер в даний момент, а також всі ваші змінні сюди. 

Отже, ви отримали центів, монети, п, оголошені на різні речі в цій точці. Не турбуйтеся, тому що у нас немає насправді не ініціалізації їх до будь змінним ще. Таким чином, у вашому комп'ютері, ваш Комп'ютер просто бачачи, ой, 32767 був останній використовувана функція цього простору пам'яті в моєму комп'ютері. І так ось де центів в даний час. Але ні що колись ви не запустите код, вона повинна стати ініціалізації. 

Так давайте пройдемо, лінію лінія, те, що тут відбувається. ДОБРЕ. Так тут є три кнопки, які я тільки що пояснив. Ви повинні грати, або функцію Run, Кнопка, у вас є Крок за кнопку, і у вас також є Крок у кнопки. І, по суті, всі три їм просто пройти через код і робити різні речі. 

Так зазвичай, коли ви налагодження, ми не хочемо, щоб просто натиснути Play, тому Гра буде просто запустити код до кінця цього. І тоді у вас не буде насправді знаю, що ваша проблема Тобто, якщо ви не встановите кілька точок зупину. Якщо ви встановите кілька точок зупину, це буде просто автоматично бігти від однієї точки зупину, до іншого, щоб наступного. Але в цьому випадку ми в тільки, що один, тому що ми хочу працювати наш шлях зверху вниз вниз. Отже, ми збираємося, щоб ігнорувати цю кнопку зараз для цілей цієї програми. 

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

Але, як правило, ми припускаємо, що код, який ми даємо вам роботи. Ми припускаємо, що Е () працює. Ми припускаємо, що GetInt () працює. Таким чином, немає ніякої необхідності крок у цих функцій. Але якщо є функції що ви пишете самі що ви хочете, щоб перевірити , Що відбувається, Ви хотіли б крок в цій функції. 

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

Так п, яка є нашим поплавок, що ми в initialized-- або declared-- нагорі, ми тепер рівна, що GetFloat (). Отже, давайте переступити що. І ми бачимо, на Нижня тут, програма спонукає мене до входу значення. Отже, давайте Введіть значення ми хочемо перевірити тут, що 0,41. Відмінно. 

Так що тепер N-- ви, хлопці, бачите тут, на bottom-- це stored--, тому що ми ще не округляється, це зберігаються в цьому, як гігант поплавок, який +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-- або вибачте, не менш 3 than--. Таким чином, мінімальне значення раніше 3. І тоді ви отримаєте 2. Комп'ютер бачить, ой, 2 менше, ніж 3. Тепер 2 повинно бути мінімальне значення. І так 2 свопи з цієї першої величини. 

Таким чином, після одного проходу, ми дійсно бачимо що 2 і 3 міняються місцями. І ми тільки збираємося продовжувати робити Це знову з іншою частиною масиву. Отже, ми збираємося, щоб просто запустити через Останні чотири індекси масиву. Ми побачимо, що 3 наступний мінімальне значення. Отже, ми збираємося, щоб поміняти що з 4. І тоді ми просто будемо продовжувати не проходить через до, в кінці кінців, ви потрапити в відсортованому масиві, в якому 2, 3, 4, 5, 6 і всі сортуються. Всі розуміють чи логіку про те, як працює вибір роду? 

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

Отже, як ви, хлопці, начебто бачив з мигцем, ми збираємося псевдокод це. Так що, якщо ви, хлопці, в задній хочете утворюють групу, кожен в таблиці можуть утворювати мало партнера, я збираюся щоб дати вам, хлопці, як три хвилини просто говорити через логіка, англійською мовою, про те, як ми могли б реалізувати псевдокод написати вибору роду. І є цукерки. Будь ласка, приходьте і отримаєте цукерку. Якщо ви знаходитесь в спині і ви хочете цукерки, я можу кинути цукерки на вас. Насправді, зробити you-- прохолодно. Ой, вибачте. ДОБРЕ. 

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

АУДИТОРІЯ: Ви хочете, щоб створити деякі роду [нерозбірливо], що ви проходить через весь масиві. 

ANDI Пен: Право. Таким чином, ви будете хотіти, щоб ітерації через кожен простору, правильно? Настільки велика. Якщо ви, хлопці, хочете, щоб дати мені Наступний line-- да, в спину. 

АУДИТОРІЯ: Перевірте їх все для найменших. 

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

АУДИТОРІЯ: [нерозбірливо] ANDI Пен: Так що ви збираєтеся хочуть переключити його з першого цьому масиві, вірно? Це початок, я збираюся сказати. Добре. Так що тепер ви помінялися перший Один з них, що ви хочете зробити після цього? Так що тепер ми знаємо, що це одне тут повинні бути найменше значення, чи не так? Тоді у вас є додатковий відпочинок масиву, що це несортоване. Так що ви хочете зробити тут, якщо ви хлопці, хочете, щоб дати мені наступний рядок? АУДИТОРІЯ: Отже ви хочете перебрати через решту масиву. ANDI Пен: Так. І так, що ж переборі вид має на увазі ми, напевно, потрібно? Який тип of-- 

АУДИТОРІЯ: О, додаткова змінна? ANDI Пен: Можливо другий цикл, чи не так? Таким чином, ми, ймовірно, захочуть для перебору through-- здорово. І тоді ви будете йти назад і ймовірно, перевірити мінімум раз вірно? І ви збираєтеся повторювати це, тому що петлі тільки збирається тримати працює, вірно? 

Отже, як ви, хлопці, можете бачити, ми просто загальний псевдокод про те, як ми хочемо, щоб ця програма дивитися. Це ітерація тут, те, що ми як правило, потрібно написати в коді якщо ми хочемо, щоб ітерації через Масив, який тип структури? Я думаю, Крістабел вже говорив це раніше. 

Зали: для петлі. 

ANDI Пен: для циклу? Точно. Так це, напевно, буде цикл. Що таке перевірка тут збирається означає? Як правило, якщо ви хочете, щоб перевірити якщо щось щось else-- 

АУДИТОРІЯ: Якщо. 

ANDI PENG: якщо, вірно? А потім своп тут, ми будемо перейти пізніше, бо Давида пройшов через це в лекції, а також. А потім другий ітерації implies-- 

АУДИТОРІЯ: Ще цикл. 

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

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

І врешті-решт, я також отримав для цикл, який друкує його знову. Так, теоретично, якщо ця програма працює правильно, зрештою, Ви повинні побачити друкований цикл в якому 1, 2, 3, 4, 5, 6, 7, 8, 9 все правильно в порядку. 

Таким чином, ми отримали наш псевдокод тут. Хто-небудь хоче, метою яких я просто піду просити volunteers-- скажіть мені точно, що якщо ввести ми хочемо, щоб, по-перше, просто ітерації по початок цього масиву? Що рядок коду я ймовірно, тут потрібно? 

АУДИТОРІЯ: [нерозбірливо] 

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

АУДИТОРІЯ: Для INT я дорівнює 0-- 

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

АУДИТОРІЯ: я менше довжини масиву. 

ANDI Пен: Так що майте на проти тут, тому що ми не їсти функція, яка говорить нам довжина масиву, у нас вже є Значення, яке зберігає, що. Вірно? Ще одна річ, щоб тримати в mind-- в масиві з дев'яти значень, які індекси? Давайте просто скажемо, цей масив 0 до 3. Ви бачите, що останній Індекс насправді 3. Це не 4, хоча є чотири значення в масиві. 

Так тут, ми повинні бути дуже обережні, того, що наша умова для довжини буде. 

АУДИТОРІЯ: не було б н мінус 1? ANDI Пен: Це відбувається п мінус 1, точно. Чи має це сенс, чому це п мінус 1, все? Це тому, що масиви дорівнюють нулю, індексовані. Вони починаються з 0 і запустити до н мінус 1. Так, це трохи складніше. ДОБРЕ. І потім-- АУДИТОРІЯ: Isnt'1, що вже подбали, хоча, , Просто не говорю "менше або дорівнює "і просто говорю" менш "? 

ANDI Пен: Це дуже гарне питання. Так що, так. Але також, таким чином, що ми реалізації перевірки право, вам потрібно порівняти два значення. Таким чином, ви насправді хочете, щоб залишити "на" порожній. Тому що, якщо ви порівняєте це одне, ви не збираєтеся є що-небудь після нього порівняти, правда? Так. Так я ++. Давайте додамо наші дужки в. Упс. Відмінно. Таким чином, ми маємо початок нашої зовнішньої петлі. Так що тепер ми, ймовірно, хочете, щоб створити змінну для зберігання трек найменшим значенням, вірно? Хто-небудь хоче, щоб дати мені рядок коду, яка буде це робити? Що нам потрібно, якщо ми збираємося хочуть, щоб зберегти що-небудь? 

Право. Може бути, краще, що назва буде be-- "Темп" повністю works-- може бути, більш влучно назвав би, якщо ми хочемо, щоб маленький value-- 

АУДИТОРІЯ: Мін. ANDI Пен: хв, там ми йдемо. хв буде добре. І ось що нам робити хочу, щоб ініціалізувати його? Це трохи складніше. Тому що зараз на початок цього масиву, Ви ще не дивилися ні на що, чи не так? Так що, автоматично, якщо ми тільки на я дорівнює 0, те, що ми хочемо, щоб ініціалізувати наш перший мінімальне значення для? АУДИТОРІЯ: я. ANDI Пен: я, точно. Christabel, чому ми хочемо ініціалізувати його я? 

АУДИТОРІЯ: Тому що, ну, ми, починаючи з 0. Так, тому що ми не маємо нічого, щоб порівняти це, мінімум буде в кінцевому підсумку 0. 

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

Так що тепер ми хочемо, щоб додати для циклу тут це збирається повторювати через несортоване або інша частина цього масиву. Хто-небудь хоче, щоб дати мені рядок коду, яка буде це робити? Hint-- що нам потрібно тут? Що збирається йти в цьому для циклу? Так. АУДИТОРІЯ: Таким чином, ми хотіли б мати різний число, бо ми біжимо до кінця масиву замість I, так що, можливо J. 

ANDI Пен: Так, J звучить добре для мене. Одно? 

АУДИТОРІЯ: Так би я плюс 1, бо Ви починаєте на наступній значення. А потім до end-- так знову, J є менше, ніж п мінус 1, а потім J ++. ANDI Пен: Відмінно. 

А потім тут, ми збираємося хочете щоб перевірити, якщо наша умова виконується, вірно? Тому що ви хочете, щоб змінити мінімальне значення якщо це насправді менше, ніж ви порівнюєте його, вірно? Так що ми збираємося хочете тут? Перевірте, щоб бачити. Який вид заяви ми, ймовірно, буде ти хочете використовувати, якщо ми хочу дещо перевірити? 

АУДИТОРІЯ: якщо заяву. 

ANDI PENG: якщо заяву. Так if-- і те, що буде умова, що ми хочемо в нашої, якщо заяву? 

АУДИТОРІЯ: Якщо значення J менше, ніж значення i-- 

ANDI Пен: Точно. Так if-- так що це масив називається "масив". Відмінно. Так що, якщо array-- що це було? Скажіть, що ще раз. 

АУДИТОРІЯ: Якщо масив-J менше Масив-я, то ми б змінити хв. Таким чином, хв буде к. 

ANDI Пен: Чи має це сенс? ДОБРЕ. А тепер сюди, ми насправді хочемо реалізувати обмін, вірно? Так Нагадаємо, що в лекції, що Давид, коли він намагався обміняти the--, що було it-- апельсиновий сік і milk-- 

АУДИТОРІЯ: Це було огидно. 

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

АУДИТОРІЯ: тимчасова змінна. 

ANDI Пен: тимчасова змінна. Так давайте зробимо Int темп. Дивись, це було б краще Час, метою яких агов, що це було? ДОБРЕ. Так що це було б краще час назвати змінну "Темп". Так давайте зробимо Int темп. Що ми збираємося SET TEMP рівну тут? АУДИТОРІЯ: Мін? ANDI Пен: Це трохи складніше. Це насправді не має значення, в кінці кінців. Це не має значення, що замовлення ви вирішите поміняти в так довго, як ви робите, що ви відстежувати те, що ви підкачки. 

АУДИТОРІЯ: Це може бути масив я. 

ANDI Пен: Так, давайте зробимо масив-I. І тоді те, що наступна рядок коду ми хочемо мати тут? АУДИТОРІЯ: масив я дорівнює масиву-J. ANDI Пен: І, нарешті? АУДИТОРІЯ: масив J дорівнює масиву я. АУДИТОРІЯ: Або масиву J одно Масив-temp-- або температури. 

ANDI Пен: ОК. Так що давайте працювати і подивимося, якщо він буде працювати. Де, що відбувається? О, що це проблема. Дивись, на лінії 40, ми намагається використовувати масив-J? Але де J існує тільки в? 

АУДИТОРІЯ: Протягом циклу. ANDI Пен: Право. Так що ми збираємося потрібно зробити? 

АУДИТОРІЯ: Визначити його межами the-- АУДИТОРІЯ: Так, я думаю, ви повинні використовувати інший, якщо заяву, чи не так? Так як, якщо minimum-- Все в порядку, дайте мені подумати. 

ANDI Пен: Хлопці, спробуйте поглянути Давайте см, що це те, що ми можемо зробити тут? 

АУДИТОРІЯ: ОК. Таким чином, якщо мінімальна не дорівнює j-- так що якщо мінімальна ще i-- то ми б не поміняти. 

ANDI Пен: Чи означає це, одно я? Що ви хочете сказати тут? 

АУДИТОРІЯ: Або так, якщо мінімум не рівне I, так. ANDI Пен: ОК. Ну, що вирішує, начебто, наші проблеми. Але це ще не вирішити Проблема що станеться, якщо j-- так J не існує поза ним, те, що Ви хочете, щоб ми з ним робити? Оголосити його межами? Давайте спробуємо це працює. Ой-ой. Наша роду не працює. 

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

Так, тому що ми вже знаємо, що ці лінії, 15 через 22, які working--, тому що все, що я роблю просто перебираючи і printing-- Я можу йти вперед і пропустити це. Давайте почнемо з лінії 25. ООП дозвольте мені позбутися цього. 

АУДИТОРІЯ: Так точки зупину де починається налагодження? ANDI Пен: Або зупинок. АУДИТОРІЯ: Або зупинок. ANDI Пен: Так. Ви можете встановити точки зупину і кілька він може просто стрибати від одного до іншого. Але в цьому випадку ми не знаємо, де помилка відбувається. Таким чином, ми просто хочемо почати зверху вниз. Так. ДОБРЕ. 

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

І так давайте тримати покрокове. Наш мінімальний дорівнює 0, які ми також хочемо, щоб це було. І тоді ми входимо наш другий для цикл, якщо масив J менше, ніж масив-I, який його не було. Так само ви бачите, як що пропустив що? 

АУДИТОРІЯ: так повинно, якщо Мінімальний все that-- не випливає, що бути всередині першого цикл? ANDI Пен: Ні, тому що Ви все ще хочете, щоб перевірити. Ви хочете, щоб зробити порівняння кожен Час, навіть після запуску через нього. Ви не просто хочете, щоб зробити це на першому прохід. Ви хочете, щоб зробити це з кожен прохід знову. Отже, ви хочете, щоб перевірити Ваш стан всередині. Таким чином, ми тільки збираємося тримати працює через тут. Я дам вам підказку хлопцям. Це пов'язано з тим, що при Ви перевіряєте ваш умовний, Ви не перевіряючи для правильного індексу. Так що зараз ви перевірка Індекс масиву J менше, ніж масив Індекс I. Але те, що ти робиш на початок для циклу? Ви не встановивши J, рівний I? 

Так, так що ми насправді можемо вийти з відладчика тут. Отже, давайте поглянемо на нашому псевдокоді. For-- ми збираємося почати в я дорівнює 0. Ми збираємося йти до н мінус 1. Давайте перевіримо, ми мали це право? Так, це було в порядку. 

Отже всередині тут, ми створимо мінімальне значення і встановити, що в I рівні. Хіба ми це робимо? Так, це зробив. В даний час в нашій внутрішній петлі для, ми збирається робити J дорівнює я в п мінус 1. Хіба ми це робимо? Справді, ми зробили це. 

Так, однак, що ми тут порівняння? 

АУДИТОРІЯ: J + 1. ANDI Пен: Точно. І тоді ви будете хотіти, щоб встановити мінімальна дорівнює J плюс 1, а. Так що я пройшов через це дуже швидко. Як ви, хлопці розуміють чому це J + 1? ДОБРЕ. 

Таким чином, у вашому масиві, в Ваш перший прохід через, Ваш цикл, для Int я дорівнює 0, давайте просто припустити, що це не була змінена ще. У нас є масив, повністю, всього чотири несортовані елементи, вірно? Тому ми хочемо, щоб ініціалізувати я дорівнювати 0. І я маю намір просто проходять через цю петлю. І тому в першому проході, ми збираємося ініціалізувати змінну "хв" що також дорівнює I, тому що ми не мати мінімальне значення. Так от в даний час дорівнює 0, а також. І тоді ми будемо йти до кінця. І ми хочемо, щоб ітерації знову. Тепер, коли ми знайшли, що наш мінімальний Тобто, ми хочемо, щоб перебору знову, щоб побачити, якщо це порівняння, чи не так? Так J Ось приходить на рівне I, який є 0. І потім, якщо масив J плюс я, що це той, який далі знову, як менш ніж те, що ваш поточний мінімум значення, ви хочете поміняти місцями. 

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

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

Так що, коли ви, хлопці, просто маючи J раніше, ви не дивлячись на те після неї. Ви шукали на те ж саме значення, що Тому він просто нічого не робив. Чи має це сенс для всіх, Тому нам потрібно що плюс 1 там? ДОБРЕ. Тепер давайте просто запустити через нього, щоб зробити що інша частина коду є правильним. Чому, що трапилося? Ах, це хв прямо тут. Ми порівнювали невірне значення. О ні. 

Ах так, тут ми були обмін неправильні значення, а також. Тому що ми шукали в I і J. Ті, кого ми перевіряли. Ми насправді хочемо, щоб поміняти місцями Мінімальний струм мінімум, з тим, що один зовні. І, як ви, хлопці, можете побачити вниз тут, у нас є відсортований масив. Це просто було зробити з той факт, що, коли ми перевіряли Значення, які ми порівнювали, ми не дивилися на правильні значення. Ми шукали в тому ж самому тут, насправді не його заміни. Ви повинні дивитися на один наступний до нього, а потім ви можете поміняти. Так ось те, що було свого роду прослуховування наш код, перш ніж. І те, що я зробив тут є все, відладчик міг би зробити для вас Я просто зробив це на дошка, тому що це легше щоб побачити, а не намагатися для збільшення масштабу відладчика. Чи має це сенс для всіх? Прохолодний. 

Добре. Ми можемо рухатися далі до розмови про асимптотична позначення, які це просто фантазії спосіб сказати виконання всіх цих видів. Так що я знаю Девіда, в лекції, торкнувся автономної роботи. І він пішов через весь формулою про те, як розрахувати час автономної роботи. Не турбуйтеся про це. Якщо ви дійсно цікаво про те, як це працює, не соромтеся говорити зі мною після розділу. Ми можемо пройти через формули разом. Але всі ви, хлопці, повинні дійсно знаю, що п в квадраті більш 2 це те ж саме, як н в квадраті. Тому що найбільший номер, показник зростає найбільше. І так для наших цілей, Всі ми піклуємося про є те, що гігантський номер, який зростає. 

Так що в кращому випадку виконання відбіркового роду? Якщо ви збираєтеся мати для перебору списку а потім перебору інші цього списку, скільки разів Ви збираєтеся ймовірно, в гіршому case-- в кращому випадку, sorry-- запустити через? Можливо, краще запитати щоб запитати, що це найгірший випадок виконання відбіркового роду. АУДИТОРІЯ: п в квадраті. ANDI Пен: Це н квадрат, правильно. Так простий спосіб думати про це, як, в будь-який час у вас є два вкладених циклів для, це буде н в квадраті. Тому що не тільки ти проходить через раз, у вас є, щоб повернутися і бігти через нього знову всередині для кожного значення. Таким чином, в цьому випадку, ви працюєте п раз н квадрат, який is-- вибачте, п раз п, дорівнює п в квадраті. 

І начебто теж трохи унікальним в тому сенсі що це не має значення, якщо ці Значення вже в порядку. Він як і раніше збирається запустити через будь-якому випадку. Давайте просто сказати, що це був 1, 2, 3, 4. Незалежно від того, чи є він в порядок, це все одно б пробіг і досі перевіряється мінімальне значення. Це зробило б така ж кількість перевірок кожен раз, навіть якщо він насправді не чіпати. 

Таким чином, у такому випадку, кращим і гіршим Час автономної роботи фактично еквівалентні. Таким чином, очікуваний виконання селекційного сорту, які ми позначаємо символом тета, тета, в даному випадку, Також буде н квадрат. Всі ці три буде н квадрат. Це все зрозуміло, чому Середа виконання п квадраті? 

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

Так що давайте просто сказати, що ви були 8, 6, 4, 2. Ви б порівняти 8 і 6. Ви повинні були б поміняти їх місцями. Ви б порівняти 8 і 4. Ви повинні були б поміняти їх місцями. Якщо у вас є, щоб поміняти 8 і 2, змінити їх. Таким чином, в такому сенсі, ви можете бачити, зіграна протягом тривалого періоду часу, як значення роду міхур кінці, який є, чому ми називаємо його бульбашкова сортування. 

Ми просто запустити через раз на наш другий прохід, і наш третій прохід, і наш четвертий прохід. По суті, бульбашкова сортування працює тільки до тих пір, поки не роблять ніяких більше свопи. Так що в цьому сенсі, це просто загальна псевдокод для нього. Не турбуйтеся, це не все буде на сайті. Ми не повинні насправді піти з цього приводу. 

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

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

ДОБРЕ. Хто-небудь є припущення, що в в гіршому випадку час виконання бульбашкового сортування є? Так. 

АУДИТОРІЯ: було б, як, п раз п мінус 1 або щось подібне? Мовляв, кожен раз, коли він працює, це просто, як один своп менш що б це не було. 

ANDI Пен: Так, так Ви абсолютно праві. І це той випадок, коли ваш Відповідь насправді більш складна ніж ми повинні дати. Так це буде run-- Я збираюся стерти все це тут. Чи всі добре? Чи можу я стерти це? ДОБРЕ. Ви збираєтеся працювати через п раз в перший раз, чи не так? І вони збираються запустити через п мінус 1 вдруге, вірно? І тоді ви будете тримати відбувається, п мій 2, і так далі. Девід зробив це в лекції, де, якщо ви додали всі ці цінності, Ви отримуєте те, що це like-- yeah-- більше 2, що істотно знижує просто до п квадраті. Ви збираєтеся отримати дивно частка там. І так просто знаю, що п квадраті завжди має пріоритет над фракцією. І тому в цьому разі гіршого виконання буде н в квадраті. Якби це було в порядку убування порядок, думаю, вам, повинні зробити своп кожного разу. 

Що б, потенційно, в кращому разі виконання? Давайте просто сказати, що якщо список вже був в порядку, що б під час виконання буде? 

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

І після цього, ми тепер потрапив сортування вставками, де алгоритм, по суті, розділити це в відсортованому і несортованих частини. А потім один за іншим, невідсортоване значення вставляється у відповідних позиції на початку списку. 

Так, наприклад, у нас є Список 3, 5, 2, 6, 4 знову. Ми знаємо, що це нині несортовані, тому що ми тільки що почав дивитися на нього. Ми дивимося і ми знаємо, що перше значення сортується, вірно? Якщо ви тільки дивлячись на масив Розмір одного, ви знаєте, що це сортується. 

Отже, ми знаємо, що Інші чотири несортоване. Ми йдемо через, і ми бачимо, що значення. Давайте повернемося. Дивіться, що значення 5? Ми дивимося на нього. Ми порівнюємо його до 3. Ми знаємо, що це більше, ніж 3, так що ми знаємо, що це сортується. Таким чином, ми тепер знаємо, що перші два сортуються, а останні три не є. 

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

Так що це просто алгоритм, псевдокод такої, начебто, про те, як ми буде здійснювати сортування вставками. Псевдокод тут. Це все в Інтернеті. Не турбуйтеся, якщо ви, хлопці, намагаючись скопіювати це вниз. Отже, ще раз, то ж саме, що question-- буде кращим і гіршим автономної роботи для вставки роду? Це дуже схоже на останнє запитання. Я дам вам, хлопці, як, 30 секунд, щоб думати про це, а також. 

ОК чи хтось хоче дати мені найгірший виконання? Так. 

АУДИТОРІЯ: п в квадраті. 

ANDI Пен: Це н квадраті. І чому це п квадраті? 

АУДИТОРІЯ: Тому що в зворотний порядок, у вас є пройти через п раз п, is-- ANDI Пен: Так, саме так. Так само, як і в бульбашкового сортування. Якщо цей список в порядку убування, ви доведеться перевірити перший раз. А потім з кожним додаткова вартість, ви доведеться перевірити його проти кожен значення, вірно? І так в цілому, ви збираєтеся зробити А.Н. раз н-пас другий п пройти, що в п квадраті. Що можна сказати про кращому випадку? Так. 

АУДИТОРІЯ: N мінус 1, оскільки Перший вже в квадрат. 

ANDI Пен: Так, близько. Відповідь насправді п. Оскільки в той час як Перший сортувати, вона не може його actually-- ми просто пощастило, в що приклад, що 2 відбулося найменше число. Але не завжди буде так. Якщо 2 вже відсортовані на початку але ви подивіться, і є 1 тут, 1 буде підняти його. І це буде в кінцевому до того зіткнувся в будь-якому випадку. 

Таким чином, в кращому випадку, це насправді просто буде н. Якщо у вас є 1, 2, 3, 4, 5, 6, 7, 8, ви збирається запустити через що весь список відразу щоб перевірити, якщо все в порядку. Це все ясно, на працюючому раз відбору, а? Я знаю, що йду через це дуже швидко. Але точно знаю, що, якщо ви знаєте, загальні поняття, ви повинні бути добре. ДОБРЕ. Так що я просто дам вам, хлопці, може бути, як, хвилину, щоб поговорити з вашими сусідами на те, що лише деякі з основних відмінностей між цими типами сортів. Ми підемо над тим найближчим часом. АУДИТОРІЯ: О, добре. ANDI Пен: Так. ДОБРЕ. Прохолодний, давайте знову скликати як клас. ДОБРЕ. Так що це було свого роду відкрите питання в тому сенсі, що є багато відповідей на них. І ми будемо йти над деякими з них коротко. Я просто хотів, щоб ви, хлопці думаючи про те, що диференційований всі три типи сортів. І почув я, також, великий question-- що ж сортування злиттям зробити? Велике питання, тому що це те, що ми в наступному покриття. 

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

Так так, що зливаються Сортувати по суті працює є те, що ділить несортоване масив навпіл. А потім він отримав дві половинки масивів. І це якраз ті сортує дві половинки. Він просто тримає ділення навпіл, в половина, навпіл, поки все не буде відсортований а потім рекурсивно ставить все це разом. 

Так що це дійсно абстрактною. Так що це просто трохи псевдокоду. Чи має це сенс у так, як це працює? Так що давайте просто сказати, у вас є масив п елементів, правильно? Якщо п менше, ніж 2, ви можете повернутися. Тому що ви знаєте, що, якщо є тільки одна річ, вона повинна бути відсортовані. В іншому випадку, ви сортувати ліву половину, а потім відсортувати праву половину, і тоді ви зливаються. 

Так в той час як виглядає насправді легко, насправді, думати про це це вид важко. Тому що ви, як ну от начебто працює на себе. Вірно? Це працює на себе. Так що в цьому сенсі, Девід торкнувся на рекурсії в класі. І це поняття ми поговоримо про більш. Це що це, ці дві лінії Тут, насправді це просто програма кажу це, щоб запустити себе з іншого вхід. Таким чином, замість запуску себе з повнота п елементів, Ви можете розбити його вниз в ліва половина і права половина а потім запустити його знову. 

І тоді ми будемо дивитися на нього візуально, бо я візуальний учень. Це працює краще для мене. Таким чином, ми будемо дивитися на наочному прикладі тут. 

Скажімо, ми маємо масив, шість Елементи, 3, 5, 2, 6, 4, 1, що не відсортовані. Гаразд, є багато на цій сторінці. Так що, якщо ви, хлопці, можете подивитися на Перший крок тут, 3, 5, 2, 6, 4, 1, Ви можете розділити його навпіл. У вас є 3, 5, 2, 6, 4, 1. Ви знаєте, що це вам aren't-- не знаю, якщо вони сортуються чи ні, так ви тримаєте розбиваючи їх в половині, навпіл, навпіл, поки врешті-решт, у вас є тільки один елемент. І один елемент завжди сортуються, вірно? 

Отже, ми знаємо, що 3, 5, 2, 4, 6, 1, самі по собі, сортуються. І тепер ми можемо покласти їх назад разом. Таким чином, ми знаємо 3, 5. Ставимо їх разом. Ми знаємо, що це відсортований. У 2-х досі там. Ми можемо поставити 4 і 6 разом. Ми знаємо, що це сортується, таким чином, ми покласти, що разом. А 1 є. 

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

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

І тому в цьому шляху, ви тільки врятувати себе багато кроків, коли ви порівнюєте. Ви не повинні порівнювати кожен Елемент з іншими елементами. Ви просто порівняйте проти тих що вам потрібно, щоб порівняти її з. Так що начебто абстрактної концепції. Не турбуйтеся, якщо це не досить удару вас прямо ще. Але, як правило, це як сортування злиттям працює. Питання, простих запитань, перш, ніж я рухатися далі? Так. 

АУДИТОРІЯ: Так ви сказали, що ви берете 1, а потім 4 і 6 і поклав їх у. Так не those-- НЕ Ви шукаєте на них як окремі елементи, а не як в цілому? ANDI Пен: Так. Так, що відбувається є те, що ви в основному створюють абсолютно новий масив. Таким чином, ви знаєте, що, от, у мене є два масиви розміром 3, вірно? Таким чином, ви знаєте, що мій відсортований масив повинен мати шість елементів. Таким чином, ви просто створити Новий обсяг пам'яті. Так ви ніби як будучи марнотратним пам'яті, але це не має значення тому що це так мало. Таким чином, ви дивитеся на 1 і ви подивіться на 2. І ви знаєте, що 1 менше, ніж 2. Таким чином, ви знаєте, що 1 повинні йти в початок всіх тих. 

Ви навіть не потрібно дивитися на 3 та 5. Таким чином, ви знаєте, 1 йде туди. Тоді ви в основному відрубати 1. Це, начебто, помер для нас. Тоді ми просто повинні 2, 3, 5, а потім 4 і 6. І тоді ви знаєте, що ви порівняти 4 і 2, ой, 2 повинні піти туди. Таким чином, ви грюкнути 2 вниз, рубайте його. Тоді ви просто є 3 і 5 в 4 і 6. І ви просто тримати його подрібнення поки ви не покласти їх у масиві. 

АУДИТОРІЯ: Так ти просто завжди Порівнюючи [нерозбірливо]? 

ANDI Пен: Точно. Так що в цьому сенсі, ви просто порівняння, по суті, один номер проти інший номер. І тому що ви знаєте що це сортується, вам не доведеться шукати через всі номери. Ви просто повинні подивитися на перший. І тоді ви можете просто грюкнути їх вниз, тому що ви знаєте, вони належать, де вони повинні належати. Так. Гарне питання. 

І потім, якщо кожен з вас трохи амбітний, не соромтеся, щоб подивитися на цей код. Це насправді фізична реалізація про те, як ми повинні написати сортування злиттям. І ви можете бачити, це дуже мало. Але ідеї, що лежать в це досить складна. Так що, якщо ви відчуваєте, як малюнок на це у виконанні домашніх завдань сьогодні, не соромтеся. 

ДОБРЕ. Так і Давид підійшов це в лекції. Що в кращому випадку Час автономної роботи, в гіршому випадку час автономної роботи, та очікувані автономної роботи від сортування злиттям? Через пару секунд, щоб подумати. Це досить важко, але вид інтуїтивним, якщо ви думаєте про це. Добре. 

Залу: в гіршому випадку п п журналу? ANDI Пен: Точно. І чому це п п увійти. 

АУДИТОРІЯ: Хіба це не тому, що він стає експоненціально швидше, так що це, як функції, які а просто бути п квадрат або щось? ANDI Пен: Точно. Таким чином, причина, по якій виконання на це н журналу п because--, що ти робити у всіх цих кроків? Ви просто рубати його навпіл, вірно? І тому, коли ми робимо увійти, все, що він робить ділить проблему навпіл, в два рази, в два рази, в більше половини. І в цьому сенсі, ви можете вид з усунути лінійну модель що ми використали. Тому що, коли ви нарізати речі в половині, це журнал. Ось тільки математичний спосіб представлення його. 

І, нарешті, в кінці, ви просто зробити один останній пас через поставити всі з них в порядку, вірно? І так, якщо ви просто повинні перевірити одну річ, це п. І так ти начебто множення разом. Так що це, як ви отримали, що остаточний перевірити п сюди з колоди п тут. І якщо помножити їм, що це н н увійти. 

І так в кращому випадку і гірші Корпус і очікується, всі п п увійти. Це також, як іншого роду. Це як вибір роду в тому сенсі, що Не має значення, що ваш Список, це просто буде щоб зробити те ж саме кожного разу. ДОБРЕ. Отже, як ви, хлопці, можете бачити, навіть якщо рослини, які ми пішли through-- п квадрат, це не дуже ефективно. І навіть у цьому п п журналу не найефективнішим. Якщо ви, хлопці, цікаво, є механізми сортування які є настільки ефективно, що вони майже практично плоским в режимі виконання. 

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

Добре. Отже, ми збираємося, щоб перемістити на, нарешті, пошуку. Тому що, як тих з вас, хто читав PSET, пошук також є частиною Проблема цьому тижні задає. Вам буде запропоновано здійснити два типи пошуків. Одним з них є лінійний пошук і одна двійковий пошук. 

Таким чином, лінійний пошук досить легко. Ви просто хочете, щоб пошук елемента зі списку, щоб побачити, якщо ви його отримаєте. Ви просто повинні перебору. І якщо він дорівнює те, ви можете просто повернути його, вірно? Але той, що ми найбільш зацікавлені в розмові про це бінарний пошук, право, яке є розділяй і володарюй механізм, який Девід демонстрував в лекції. 

Пам'ятайте приклад телефонної книги що він продовжує виховувати, той, який він начебто боролися трохи на минулий рік, де ви розділите задачу на половині, в два рази, в два рази, знову і знову, поки ви не знайдете те, що ви шукаєте? І ви отримали час виконання, що добре. І ви можете бачити, це значно ефективнішим ніж будь-який інший тип пошуку. 

Таким чином, шлях, який ми б йти про реалізації двійкового пошуку Тобто, якщо у нас було безліч, Індекс 0 до 6, сімох елементів, ми можемо дивитися в середині, right-- вибачте, якщо наше запитання first-- якщо ми хочемо, щоб поставити запитання про, що не масив містить елемент 7, Очевидно, будучи людей, і має такий маленький масив, це просто для нас щоб сказати так. Але шлях до реалізації двійковий Пошук буде виглядати в середині. 

Ми знаємо, що індекс 3 середній, тому що ми знаю, що є сім елементів. Що 7 ділиться на 2? Ви можете відрубати що додатковий 1. Ви отримали 3 в середині. Так масив з 3 одно 7? Це не так, вірно? Але ми можемо зробити пару чеків. Це масив з 3 менше, ніж 7 або це масив з 3 більше, ніж 7? 

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

Так що тепер ми дивимося на Середина те, що залишилося. Цей показник 5. Ми робимо те ж саме ще раз перевірку і ми бачимо, що це менше. Таким чином, ми дивимося в лівій частині, що. І тоді ми бачимо, що чек. Чи є значення масиву в Індекс 4 дорівнює 7? Це є. Таким чином, ми можемо повернутися так, тому що ми знайшли значення в нашому списку. Лі шлях я пройшов що сенс всім? ДОБРЕ. Я дам вам, хлопці, може бути, як, три, чотири хвилини, щоб з'ясувати, як псевдокод це. 

Отже, уявіть, я попросив вас написати Функція називається пошук (), що повернувся значення, логічне значення, що це правда чи false-- як, вірно, якщо ви знайшли значення, брехня, якщо ви не зробили. І тоді ви були пройшов у вартості ви шукали в цінності, які це array-- о, я виразно поставити що в неправильному місці. ДОБРЕ. У кожному разі, що повинно бути був праворуч значень. А потім Int N це число елементів у цьому масиві. Як би ви йти про спробу в псевдокоді цю проблему в? Я дам вам, хлопці, як три хвилини, щоб зробити це. Ні, я думаю, що є only-- да, є одна прямо тут. АУДИТОРІЯ: Чи можу я? ANDI Пен: Так, у мене є ти. Це працює? ОК здорово. 

ДОБРЕ. Всі правильні хлопці, ми збирається приборкати його. ДОБРЕ. Так припустимо, що у нас є ця прекрасна трохи масив з п значень в ньому. Я не малювати лінії. Але як би ми йти про намагаюся написати це? Хто-небудь хоче дати мені першу лінію? Якщо ви хочете, щоб дати мені Перший рядок цього псевдокоду. 

АУДИТОРІЯ: [нерозбірливо] АУДИТОРІЯ: Ви хотіли для перебору through-- АУДИТОРІЯ: Просто ще один цикл? АУДИТОРІЯ: --Для. 

ANDI Пен: Так що це одне трохи складніше. Подумайте about-- ви хочете тримати працює цей цикл знову і знову, поки, коли? 

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

Аудиторія: Значення дорівнює середину. ANDI Пен: Скажи це ще раз. АУДИТОРІЯ: Або, до Значення ви шукаєте Для дорівнює середнього значення. 

ANDI Пен: Що робити, якщо це не там? Що робити, якщо значення ви шукаєте для насправді не в цьому масиві? АУДИТОРІЯ: Ви повертаєтеся 1. 

ANDI Пен: Але те, що ми хочемо, щоб цикл до якщо у нас є стан? Так. 

АУДИТОРІЯ: поки є тільки одне значення? ANDI Пен: Ви можете цикл until-- так що ви знаєте, що ви матиме максимальне значення, чи не так? І ви знаєте, що ви збираєтеся мати значення хв, вірно? Тому що також, це те, що Я забув сказати, перш ніж, що щось, що це критично бінарного пошуку є те, що ваш масив вже відсортовані. Тому що немає ніякого способу робити це, якщо вони просто випадкові значення. Ви не знаєте, якщо один це більше, ніж інші, вірно? 

Таким чином, ви знаєте, що ваш Макс і Ваші хвилин тут, вірно? Якщо ви збираєтеся бути регулювання Ваш макс в ваших хвилин і mid-- давайте припустимо, ваш Значення середнього правильно here-- Ви збираєтеся в основному цикл доти, мінімальна НЕ приблизно те ж саме, як ваш макс, прямо або якщо ваш максимум не те ж саме, як ваш хв. Вірно? Тому що, коли це станеться, ви знаєте, що Ви в кінцевому підсумку потрапив у таке ж значення. Так ви не хочете, щоб петлі, поки ваш хв менше або дорівнює, метою яких упс, не менше або дорівнює, інакше around-- Макс. 

Хіба що сенс? Я взяв кілька спроб, щоб отримати це право. Але цикл, поки ваш максимального значення по суті майже немає ніж або дорівнює вашої мінімум, вірно? Ось коли ви знаєте, що ви зійшлися. АУДИТОРІЯ: Коли ваша максимальна значення менше, ніж мінімум? ANDI Пен: Якщо ви тримаєте регулюючи його, що це те, що ми збираємося щоб робити в цьому. Чи має це сенс? Мінімальна і максимальна просто цілі числа, ми, ймовірно, збирається хочете створити, щоб тримати трек, де ми шукаємо. Оскільки масив існує незалежно від того, що ми робимо. Мовляв, ми насправді не фізично відрубування масиву, вірно? Ми просто регулюючи де ми шукаємо. Чи має це сенс? 

АУДИТОРІЯ: Так. 

ANDI Пен: ОК. Так що, якщо ця умова нашої петлі, те, що ми хочемо всередині цієї петлі? Що ми збираємося бути бажання зробити? Так що зараз, у нас є макс і мін, право, ймовірно, створена десь тут. Ми збираємося, ймовірно, хочете знайти середину, вірно? Як ми збираємося, щоб бути можливість знайти середину? Що mathematical-- АУДИТОРІЯ: Макс плюс хв розділені на 2. ANDI Пен: Точно. Чи має це сенс? І ви, хлопці, зрозуміти, чому ми не просто use--, чому ми зробили це а не робити просто п ділиться на 2? Це тому, що п є значення що збирається залишитися те ж саме. Вірно? Але, як ми скорегуємо нашу мінімум і Максимальні значення, вони збираються змінити. І в результаті, наш середній збирається змінювати занадто. Так ось чому ми хочемо зробити це прямо тут. ДОБРЕ. 

А потім, в даний час, що ми знайшли our-- так. 

АУДИТОРІЯ: Просто швидко question-- коли ви говорите, мін і макс, ми припускаючи, що це вже відсортовані? 

ANDI Пен: Так, це насправді передумовою для бінарного пошуку, що ви повинні знати, що це сортується. Саме тому-то, ви пишете у вашому Проблема встановити до вашого бінарного пошуку. ДОБРЕ. Так що тепер ми знаємо, де наша середина є те, що ви хочете зробити тут? 

АУДИТОРІЯ: Ми хочемо, щоб порівняти що до іншого. ANDI Пен: Точно. Таким чином, ви будете порівнювати з середини до значення, чи не так? І що це говорить нам, коли ми порівнюємо? Що ми хочемо робити далі? 

АУДИТОРІЯ: Якщо значення більше ніж середині, ми хочемо, щоб відрізати його. ANDI Пен: Точно. Таким чином, якщо значення більше ніж середині, ми захоче змінити ці Мінімальна і вичерпаний, вірно? Що ми хочемо змінити? Так що, якщо ми знаємо, що десь значення тут, що ви у нас змінити? Ми хочемо змінити нашу Мінімальний бути в середині, чи не так? А потім ще, якщо він знаходиться в цьому половина, що ми хочемо змінити? 

АУДИТОРІЯ: Ваша максимальна. ANDI Пен: Так. А потім ви просто тримати цикл, вірно? Тому що зараз, після однієї ітерації через, у вас є макс тут. І тоді ви можете перерахувати середині. І тоді ви можете порівняти. І ви збираєтеся продовжувати не до хвилин і Maxes істотно зійшлися. І ось, коли ви знаєте, що Ви потрапили в кінець. І або ви знайшли його або ви не в цій точці. 

Чи має це сенс для всіх? ДОБРЕ. Це дуже важливо, тому що ви будете мати щоб написати це в коді сьогодні. Але ви, хлопці, є дуже хороший відчуття, що ви повинні робити, і це добре. ДОБРЕ. Отже, ми отримали близько семи хвилини залишилося розділ. Таким чином, ми будемо говорити про це PSET, що ми будемо робити. Таким чином, PSET розділений на дві половини. Перша половина включає реалізації знахідку в якому Ви пишете, лінійний пошук, А бінарний пошук, і алгоритм сортування. 

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

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

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

І тоді ви будете по суті просто покласти їх всі разом. Специфікація скаже вам, як покласти, що в командному рядку. І ви зможете перевірити, чи є не ваша сортування і пошуку працюють. Прохолодний. Хто-небудь вже почалася, і зустрічаються проблеми або питання вони мають зараз з цим? ДОБРЕ. 

АУДИТОРІЯ: Зачекайте. У мене є питання. 

ANDI Пен: Так. 

АУДИТОРІЯ: Так що я почав робити лінійний пошук в helpers.c і це не було дійсно працює. Але потім я дізнався, ми просто повинні видалити його і зробити бінарний пошук. Так чи не все одно, якщо він не працює? 

ANDI Пен: Коротка відповідь: ні. Але так як ми не-- АУДИТОРІЯ: Але ніхто не насправді перевірки. ANDI Пен: Ми ніколи не побачите, що. Але ви, мабуть, хочете, щоб що ваш пошук роботи. Тому що, якщо ваш лінійний пошук не працює, то швидше за все, ваш бінарний Пошук не буде працювати, як добре. Тому що у вас є подібне Логіка в них обох. І немає, це не має значення. Таким чином, єдиними ви включите в є свого роду і бінарний пошук. Так. 

А також, багато дітей були намагаючись зібрати helpers.c. Ви насправді не допускаються щоб зробити це, бо helpers.c не має основну функцію. І тому ви повинні тільки бути насправді компіляції генерувати і знайти, бо знайти дзвінки helpers.c і функції в ній. Так що робить налагодження біль в дупі. Але це те, що ми повинні робити. АУДИТОРІЯ: Ви просто зробити все, вірно? ANDI Пен: ви можете просто зробити все як добре, так. ДОБРЕ. Так ось воно що в плані того, що PSET просить, щоб ви все робите. Якщо у вас є які-небудь питання, будь ласка, вільним запитати мені після розділу. Я буду тут, як, 20 хвилин. 

І так, Pset-х дійсно не так уже й погано. Ви, хлопці, повинно бути в порядку. Вони, просто дотримуйтесь рекомендацій. Вид є почуття, за логікою, те, що має відбуватися, і ви будете в порядку. Не надто страшно. Там дуже багато коду вже написано. Не надто страшно, якщо ви не зрозуміти, що все це означає. Якщо це багато, це абсолютно нормально. І прийшли до офісної годин. Ми допоможемо вам поглянути. 

АУДИТОРІЯ: з додатковими Функції, ми дивимося ті до? 

ANDI Пен: Так, ті в коді. У грі 15, половина з це вже написана для вас. Так що ті функції вже в коді. Так. Добре. Ну, удачі. Це огидно день. Так сподіваюся, ви, хлопці, не відчувати себе занадто погано про перебування всередині і кодування.