СПІКЕР 1: Привіт всім! Ласкаво просимо в розділ. Так рада, що так багато з вас як тут, і кожен, хто дивиться онлайн. Так, як звичайно Ласкаво просимо. Я сподіваюся, що ви всі були прекрасні вихідні, повні відпочинку, релаксації. Це було красиво вчора. Так що, я сподіваюся, вам сподобалася на відкритому повітрі. 

Отже, спочатку пару оголошень. Класифікація. Так, більшість з вас мав отримати по електронній пошті від мене про ваше подряпин Pset, а також класифікації для Pset 1. Так, тільки пара речей. Обов'язково використовуйте check50 в style50. Вони призначені, щоб бути Ресурси для вас, хлопці, щоб переконатися, що ви отримуєте якомога більше очок, як ви можете без потреби втрачати їх. Так, такі речі, як стиль дуже важливі. Ми збираємося зняти для нього. Деякі з вас, можливо, вже зауважив, що від вашого Pset. І check50 просто дійсно простий спосіб, щоб переконатися, що ми насправді повернення того, що повинен бути повернутий користувачеві, і що все працює правильно. 

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

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

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

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

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

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

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

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

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

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

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

У місцевих жителів, всього принтами з локальних змінних. Так, в будь-який час ви в циклі, і ви просто хочете, щоб побачити, як, ой. Яка моя я? Що це ключова цінність що я инициализировать тут? Що таке повідомлення в цій точці? Це буде просто роздрукувати всі з тих, так що вам не повинні індивідуально кажуть, друку I. друку повідомлення. Друк Key. А потім Дисплей. Те, що це робить, як ви крок в рамках програми, це просто щоб переконатися, що це відображення деяких певну змінну в кожній точці. Так що ви also-- --Она ​​це вид ярлика де Ви не повинні продовжувати йти, як, ой. Друк Key або друку I. Це просто автоматично зробить це за вас. 

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

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

Що більш важливо, є термінал тут. І тут ми маємо Чому так мало? Установки. О. Правда Айк. Як це? З там. Так краще для всіх? Добре,. Прохолодний. 

Ви знаєте, коли ви знаходитесь в CS технічні труднощі класу є свого роду частиною the-- Так, давайте прояснимо це. Добре. Так, прямо тут, в розділі, які ми мали тут. Цезар являє собою виконуваний файл. Так що я зробив це. Так, одна річ, щоб зрозуміти, з GDB є що він працює тільки на виконуваних файлах. Таким чином, ви не можете запустити його на dotsy. Ви повинні реально зробити Переконайтеся, що ваш код компілюється, і що він насправді може працювати. 

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

Отже, що ж ми хочемо do-- --So, Перше, що це ми хочемо вибрати місце, щоб розбити його. Так, є одна помилка У цій програмі Цезар що я представляю, що ми збираємося з'ясувати. Це Що вона робить, це він приймає на вхід Barfoo заголовними буквами, і почему- це не міняє А. Це просто залишає тільки вона, все інше правильно, але друга буква Залишається незмінним. Так, ми збираємося, щоб спробувати з'ясувати, чому це. Так, перше, що ви, як правило, хочу зробити, коли ви починаєте на GDB є з'ясувати, де розбити його. 

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

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

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

Так, ми можемо йти далі, і продовжувати до кінця. Так, у нас є деякі клавіші там. І ми можемо роздрукувати наш ключ щоб переконатися, що це правильно. Цікаво. Не зовсім те, що ми очікували. Так, одна річ, щоб зрозуміти, з GDB також, є що це не поки ви не потрапили Далі, що лінія, що ви тільки що бачили насправді виконані. Так, в цьому випадку ключ не призначено ще. Так, Key деяке значення сміття що ви бачите на дні там. Від'ємний $ 120-- --Она ​​одного мільярда і щось дивні речі правильно? Це не той ключ, який ми очікували. Але якщо ми потрапили Далі, а потім ми спробуйте і ключ друку, це три. 

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

СПІКЕР 2: Коли ви випадковим номера, що це означає? 

СПІКЕР 1: Це просто випадковий. Це просто сміття. Це просто щось, що ваш Комп'ютер випадковим чином привласнити. Прохолодний. Отже, тепер ми можемо рухатися через, і так Тепер у нас є цей простий текстовий GetString. Отже, дозвольте мені просто ввести що відбудеться, коли ми потрапили Далі тут. Наша GDB вид зникає, чи не так? Це тому, що GetString Тепер виконання, чи не так? Так, коли ми побачили звичайний текст дорівнює GetString, відкриті круглі дужки і круглі дужки, і ми потрапили Далі, що має фактично виконано зараз. Так, він чекає нам вхідного щось. 

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

Так, якщо це умова збігаються, для нашого першого? Якщо це B, це звичайний текст І. Ми можна отримати інформацію про наших місцевих жителів. Таким чином, я дорівнює нулю, а якщо шість, який ми очікуємо, і наш ключ три. Все, що має сенс, чи не так? Ці цифри все саме те, що вони повинні бути. Так, наспівувати? СПІКЕР 3: У мене є випадкові числа для шахти. СПІКЕР 1: Ну, ми можемо check-- --Ми може поговорити про те, що в одну секунду. Але ви повинні отримувати це. Так що, якщо у нас є капітал У нашій першій, ця умова має зловити його, чи не так? Так що, якщо ми потрапили Далі, ми бачимо, що це Якщо насправді виконує. Тому що, якщо ви прямуєте разом в коді, ця лінія тут, де звичайний текст я замінюється цієї арифметики, виконується тільки в If умова правильного право? 

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

І у нас є цей чек. І ця перевірка повинна працювати, чи не так? Це А. Це має бути змінене три букви вперед. Але якщо ви помітили, ми отримати щось інше. Таким чином, в цьому випадку тут, він зловив це і так ця лінія виконана, які змінені наш B. Але, в цьому випадку тут, у нас є, що він просто пропустив його, і пішов в [? L Сіфф. ?] Так щось там відбувається. Те, що це говорить вам, що, ми знаємо, що він повинен зловити тут, але це не так. Може хто-небудь подивитися, що наш Проблема в тому, в цьому рядку? Це дуже хвилин, що. І ви також можете подивитися на коді. Він також line-- забути те, що лінія це в there-- але це в [нерозбірливо]. Да? 

СПІКЕР 4: Це на більше ніж сторінку, якщо ви читаєте це в книзі. СПІКЕР 1: Точно. Так, відладчик не міг сказати, Ви що, але відладчик може вам вниз до лінії що ви знаєте, не функціонує. І іноді, коли особливо пізніше в семестр, коли Ви маєте справу з сотнею, з сто кілька рядків коду, і ви не знаю, де це не вдається, це відмінний спосіб зробити це. Так, ми знайшли наш помилка. Ви можете це виправити у файлі, а потім ви можете запустити його знову, і все буде працювати відмінно. І, найважливіше, це це може здатися, ОК. Так. Прохолодний. Ви знали, що ви шукаєте. Таким чином, ви знали, що робити. 

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

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

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

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

Так що, якщо ми повернемося до нашого PowerPoint. Чи буде це працювати? АДД. Так. Добре. Так що, якщо ви коли-небудь знадобиться будь-який з ті, знову ж таки, є список. Так Двійковий пошук, який все пам'ятає велику видовище Давида розриваючи телефонні книги в половині. Я дійсно не отримати телефонні книги більше, тому як де ти отримати телефонні книги в ці дні? Я дійсно не знаю. Двійковий пошук. Чи пам'ятає хто- Як бінарний пошук роботи? Будь взагалі? Да? СПІКЕР 5: Ви знаєте, коли Ви дивіться на яких половина це було б в, Виходячи з цього, і позбутися від іншої половини. 

СПІКЕР 1 Рівному. Так, бінарний пошук, це частково a-- --ми подобається називати це розділяй і володарюй. Отже, що ж ви будете робити це Ви будете виглядати в середині, і ви побачите, якщо він відповідає то, що ви шукаєте. А якщо це не так, то ви намагаєтеся з'ясувати, він збирається залишити половина або права половина. Так, це може бути, якщо ви шукаєте на щось, що це алфавітний, Ви бачите, о. Чи приходить Еллісон до М? Так. Так, ми збираємося подивіться на першу половину. 

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

Так, у нас є N, який є лінійний час. Якщо N за два, що трохи краще, ще росте дуже швидко. А потім ми Увійдіть, який є що ми вважаємо бінарний пошук. Якщо ми помічаємо, як вашої проблеми стає набагато і набагато більше, Час, який потрібен вам її вирішити насправді не збільшити, що багато. Це як порівняти Тут на початку. Ти як, в порядку. Нічого тут не дійсно від того, який ми використовуємо, але ви вийти на мільйон, мільярд. Ви намагаєтеся знайти some-- --you're намагаючись знайти голку в стозі сіна. 

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

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

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

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

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

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

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

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

Мм-хм? 

СТУДЕНТ: [нерозбірливо]? ВИКЛАДАЧ: Так. Існував щось знайти в середині. 

СТУДЕНТ: Таким чином, ми можемо використовувати його. Добре. 

ВИКЛАДАЧ: Прекрасно. Так що перше, що нам потрібно зробити. Так знайти середину. Велика. Так що у вас є уявлення про те, як ми могли б насправді знайти середину з кодом? 

СТУДЕНТ: Так. п над 2? ВИКЛАДАЧ: Так п над 2. Так що головне пам'ятати, що Ваші верхні та нижні межі зміни. Ми продовжуємо звужуючи участь з масиву ми сподіваємося. Так п над 2 працюватиме тільки для першої речі ми робимо. Так що, верхній і нижній до уваги, як ми могли б отримати, що середній елемент? Тому що ми хочемо, щоб середина між верхньою і нижньою, чи не так? Мм-хм? 

СТУДЕНТ: [нерозбірливо]. 

ВИКЛАДАЧ: Отже, ми маємо деяку середину. І це буде верхня плюс нижче більш 2. Дивовижний. Там ми йдемо. Одна лінія вниз. Ви, хлопці, на вашому шляху. Так що тепер у нас є наш середнього, те, що ми хочемо зробити? Просто в цілому. Вам не потрібно кодувати його. Так. СТУДЕНТ: [нерозбірливо]? ВИКЛАДАЧ: Так що це плюс, бо ти знайти середнє між двома з них. Так що якщо ви думаєте про них, як вид збільшення в з боків, думаю про це, коли ви наближаєтеся середній, ви хочете так. Так що, якщо ви були по обидві сторони від середній, і у нас є як 5 і 7. При додаванні їх разом вам отримати 12, ви розділите на 2, 6. 

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

СТУДЕНТ: [нерозбірливо] рівно посередині якщо вони був випадок, коли є багато менших кількостях і як один великої кількості? 

ВИКЛАДАЧ: Все, що Вам потрібно це середина масиву. Так що, якщо у вас була купа невеликих кількостях а потім один дійсно велика кількість зрештою, це не має значення. Все, що має значення в тому, що вони сортуються, ви просто хочу подивитися на середині масив, тому що ви все ще нарізки вашу проблему в два рази. Прохолодний. Так що тепер у нас є середній, що ми будемо робити далі? 

СТУДЕНТ: Порівняння. ВИКЛАДАЧ: порівняти. Так порівнювати середній для value_wanted. Прохолодний. Отже, ви бачите тут у нас є це значення ми хочемо тут. Пам'ятайте, що це масив. Так середній відноситься до індексу. Таким чином, ми хочемо зробити значення середині. Не забувайте, якщо ви хочете порівняти, подвійні рівних. Ви робите один дорівнює ви просто хочу, щоб перепризначити його, а потім, звичайно, це буде значення, яке ви хочете. Так що не робіть цього. 

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

СТУДЕНТ: Роздрукуйте. 

ВИКЛАДАЧ: Ну, ми не хочу, щоб роздрукувати. Так що це Ьоо тут, тому ми хочу повернутися істинним або хибним. Ми говоримо, це число [? АСР? ?] Таким чином, якщо вона є, ми щойно повернулися чи правда. Якщо я можу записати вірно. 

СТУДЕНТ: Чому б вам не повернутися до нуля? ВИКЛАДАЧ: Таким чином, ви могли повернути нуль, якщо ви хотіли. Але в даному випадку, тому що наша функція повертає логічне значення, ми повинні повернутися істинним або хибним. СТУДЕНТ: Коли ти кажучи логічне вираз, Ви можете встановити його рівним брехня? Як якщо я хочу сказати, якщо ця умова не виконується, як це верхня дорівнює брехня. Чи буде це розуміти, якщо ви просто покласти брехня на іншу сторону? ВИКЛАДАЧ: Так. Так насправді, якщо ви коли-небудь щось робити як зверху або нижче, що повертає істину або брехня і це насправді поганий стиль скажемо дорівнює дорівнює правда чи рівних дорівнює брехня. Ви хочете використовувати цей результат як сам, як ваш чек. Не те, що я хотів. Це те, що я хотів. Таким чином, у випадку, якщо ви питаєте про щось, як зберегти це в с. 

Так що, якщо у нас є Int основний (порожнечу) і щось на зразок цього. І у вас є, якщо є верхня який вхід і ти з проханням, якщо ви можете зробити щось на зразок цього? Чи не так? СТУДЕНТ: я намагався зробити це [нерозбірливо]. Тому що, якщо it's-- ВИКЛАДАЧ: справа. Отже, ви хочете, щоб це було хибним, чи не так? СТУДЕНТ: Так. ВИКЛАДАЧ: Так що в цьому випадку ви хочу, щоб це виконати, якщо це не так. Так здорово, що у вас там таке. Так що пам'ятайте вигук Точка заперечує речі? Це говорить [нерозбірливо] означає не. Так що, якщо ми подивимося на щойно ця частина тут, ви б сказати, що має значення брехня, як ви хочете, щоб він. Чи не помилкове істинно, які значить це виконати. Чи має це сенс? СТУДЕНТ: Так. ВИКЛАДАЧ: Awesome. Добре. Таким чином, ми могли б просто повернутися правда в цьому випадку. Так що тепер у нас є два інших випадків в цьому випадку. Які наші два інших випадки? Давайте просто робити це таким чином. Отже, давайте почнемо з ще якщо значення в середині менше, ніж значення ми хочемо. Таким чином, наша цінність в середині менше ніж значення, що ми шукаємо. 

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

СТУДЕНТ: Нижній. 

ВИКЛАДАЧ: Ми будемо щоб дивитися на лівій. Так ще, якщо мало значення менше. Так вашому середнього значення тут менше, ніж те, що ми хочемо. Тому ми хочемо, щоб взяти Права сторона масиві. Таким чином, ми збираємося оновити наш нижня межа. Таким чином, ми будемо переназначать нашого нижче. І що ви думаєте нижче повинна бути? СТУДЕНТ: середнє значення? ВИКЛАДАЧ: Так середній value-- СТУДЕНТ: Плюс 1. ВИКЛАДАЧ: --plus 1. Може хто-небудь сказати мені, чому у нас є, що плюс 1? 

СТУДЕНТ: [? Немає значення?] Більш дорівнює їй. 

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

Так що тепер у нас є остання умова які я завжди заради безпеки Ви можете перевірити тут, інакше, якщо значення в середній більше, ніж значення ми хочемо. Це означає, що ми хочемо ліва рука наполовину. То який з них ми збираємося оновити? Верхній. І що це за один збирався рівнятися? Середній мінус 1, тому що, Звичайно, ми хочемо, щоб переконатися, що ми не дивлячись на цього середнього значення знову. А то у нас його. Це так. От і все, бінарний пошук. Це не так уже й погано, чи не так? Це як 10 рядків Код з пробілами. Так, дуже потужний, дуже корисно, ви будете бути з використанням його в одному з ваших подальших psets. Може бути, це не один, але пізніше. Так вивчати його. Люблю це. Це буде ставитися до вас добре. Так хто-небудь є які-небудь питання по бінарного пошуку? Так. 

СТУДЕНТ: це має значення чи Чи ваш н парних або непарних? 

ВИКЛАДАЧ: Ні. Тому що ми кинули його в середину, як INT, це буде просто обрізати його. Так він залишатиметься ціле, і це буде зрештою розібратися в усьому. Таким чином, ви не повинні турбуватися про це. Все добре? Дивовижний. Прохолодний. Так, ви, хлопці, отримав це. Слайд-шоу. Так як ми говоримо про, я знаю, Девід згадав складності автономної роботи. 

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

СТУДЕНТ: [нерозбірливо] first-- ВИКЛАДАЧ: Так середній будучи Перший елемент, який ми підходимо до, чи не так? Отже або масив з одного або все, що ми шукаємо тільки трапляється, прямо по середині. Так що це наш найкращий випадок. Ви отримуєте в реальних проблем, ймовірно, не збирається досягти [нерозбірливо], що часто. А як щодо нашої гіршому випадку? Наш найгірший випадок журналу н. І що повинен робити з усім Повноваження два речі, які я казав о. 

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

Якщо у вас це перемішані мішок чисел і ви говорите, ОК, я збираюся перевірити середину Кількість і число Я шукаю менше, ніж, я просто хочу, довільно викинути половину. Ви не знаєте, якщо ваша Цифри в цій іншій половині. Ваш список повинен бути відсортований. Крім того, це може бути йти вперед трохи, але ви повинні мати довільний доступ. Ви повинні бути в змозі просто перейти на цю середнього елемента. Якщо у вас є, щоб пройти через щось або це займе у вас додаткові кроки щоб дістатися до цього середнього елемента, це не увійти н більше, бо Ви додаєте більше роботи в ньому. І це зробить трохи більше сенсу в два тижні, але я тільки почасти хотів би випередити, дати вам, хлопці уявлення про те, що прийти. Але ті два важливі допущення що вам потрібно для бінарного списку. Переконайтеся, що він відсортований. Це великий для Ви, хлопці, прямо зараз. І на що ми можемо піти в Решта наших сортів. Так чотири sorts-- міхур, вставка, вибір, і злиття. Вони все круто. Якщо ви, хлопці, вирішили взяти CS 124, Ви дізнаєтеся про всілякі сортів. І якщо ви шанувальник XKCD, є це дійсно здорово комікс про як дійсно неефективних видів, які я дуже рекомендую вам йти дивитися. Одним з них є, як панічний роду, які як, ой ні, повернути масив випадкових. Shutdown система. Залиште. Так що викликають гумор завжди добре. 

Так хто-небудь пам'ятає вид з як тільки загальне уявлення про те, як працює бульбашкового сортування. Ви пам'ятаєте? 

СТУДЕНТ: Так. 

ВИКЛАДАЧ: Піти на це. 

СТУДЕНТ: Так що ви збираєтеся через і якщо він більше, то потрібно поміняти місцями два. 

ВИКЛАДАЧ: Мм-ом. Точно. Таким чином, ви просто перебрати. Ви перевірити два числа. Якщо один перед більше ніж той, згодом, Ви просто обміняти їх таким чином, щоб в Таким чином, все більш високими номерами міхур вверх до кінця списку і все менше число міхур вниз. 

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

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

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

І це велика річ з бульбашкового сортування. Ми знаємо, що, коли ми мають нульові свопи, що означає, що всі, знаходиться в повному порядку. Це свого роду, як ми перевіряємо. Таким чином, ми також збираємося кодувати міхур роду, які також не в тому, що погано. Жоден з них не так уже й погано. Я знаю, що вони можуть здатися трохи страшно. Я знаю, коли я взяв клас, навіть коли я викладав клас для перший раз в минулому році, Я був, як, як я можу це зробити? Це має сенс у теорії, але як ми насправді це зробити? Саме тому я і хочу, щоб йти через код з вами, хлопці тут. Так що у мене псевдокод для вас, хлопці на цей раз. Так що майте це на увазі, як ми збираємося перейти протягом. Тому у нас є якийсь лічильник, що відстежує наші свопи, тому що нам потрібно, щоб переконатися, що ми перевіряємо, що. І ми ітерації весь масив як ми тільки що зробили з цим прикладом. Якщо елемент, перш ніж більше елемент після, де ми знаходимося, ми обміняти їх і ми збільшуємо OUR Лічильник тому що як тільки ми поміняти, ми хочемо, щоб наш лічильник знаю, що. Будь-які питання є? Щось, здається, смішно тут. СТУДЕНТ: Ви встановити лічильник на нуль кожен раз, коли ви йдете через петлю? Ви не продовжувати назад до нуля кожен раз? ВИКЛАДАЧ: Не обов'язково. Так що ж відбувається у нас пройти тут. Так що в той час, пам'ятайте, що це виконуватиме один раз в обов'язковому порядку. Так це буде встановлено лічильник дорівнює нулю, то це буде для перебору. Як воно проходить по, вона оновить лічильник. Як він оновлює лічильник, коли це буде зроблено, коли він досяг кінця масиву, якщо наш списку не відсортований, Лічильник були оновлені. 

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

СТУДЕНТ: Що б функція бути для перекачки елементи? 

ВИКЛАДАЧ: Таким чином, ми можемо насправді писати що якщо ми збираємося прямо зараз. Прохолодний. Так на цій ноті, Елісон збирається Щоб повернутися назад у прилад. Це буде весело. І у нас є наш славний бульбашкова сортування річ тут. Так що я вже зробив на велосипеді через масив. У нас є наші свопи, які дорівнюють нулю. Тому ми хочемо, щоб поміняти прилеглих елементи, якщо вони вийшли з ладу. Тому перше, що ми повинні робимо, перебору нашого масиву. 

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

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

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

СТУДЕНТ: Якщо масив п менш масиву н плюс 1. ВИКЛАДАЧ: Мм-ом. Ну, менше або більше, ніж. СТУДЕНТ: Більше. Тоді ми хочемо поміняти їх місцями. Точно. Так що тепер ми потрапляємо в те, що Механізм для перекачки їх? Таким чином, ми пройшли через цю стисло, тип функції підкачування минулого тижня. Хтось пам'ятає, як він працював? Таким чином, ми не можемо просто передати їх, чи не так? Тому що одне з них буде губитися. Якщо ми сказали, дорівнює Б, а той дорівнює A, все раптово обидва просто дорівнює B. 

Отже, що ми повинні зробити, це ми є тимчасову змінну ось збирається провести один з наших-то час ми знаходимося в процесі перекачування. Так що у нас є, ми будемо мати деякий Int Температура дорівнює to-- можна призначити залежно від того, що ви хочете, просто переконайтеся, що ви відслідковувати it-- тому в даному випадку, я збираюся призначити його на масиві н плюс 1. Так що відбувається, щоб вмістити все Значення в цьому другому блоці що ми дивимося на. 

І тоді ми можемо зробити, це ми можемо піти вперед, а також переназначать масив н плюс 1, тому що ми знаємо, що Тобто це значення зберігається. Це також є одним із великої things-- Я не знаю, якщо хтось з вас були проблеми, коли при перемиканні два рядків коду раптом все працювало. Замовити дуже важливо в CS. Тому переконайтеся, що ви діаграмі речі, якщо це можливо щодо того, що відбувається насправді. Так що тепер ми збираємося перепризначити масиву п плюс 1, тому що ми знаємо, що Тобто це значення зберігається. 

І ми можемо призначити, що в масиві н а в даному випадку масив я. Занадто багато змінних. Добре. Так що тепер ми переведені масив, який я плюс 1 рівним, що знаходиться в масиві I. І тепер ми можемо повернутися і призначити масив я до чого? Будь? 

СТУДЕНТ: 10. 

ВИКЛАДАЧ: 10. Точно. І останнє. Якщо ми помінялися це зараз, Що ми повинні зробити? Що одна справа що збирається розповісти нам якщо ми коли-небудь припинити цю програму? Що говорить нам, що ми є відсортований список? Якщо ми не виконують ніяких свопів, чи не так? Якщо свопи дорівнює нулю в кінці цього. Тому, коли ви виконати обмін, як ми тільки що зробив тут, ми хочемо оновити свопи. І я знаю, що було Питання раніше про можеш використовувати нуль або один, а з істинними або помилковими. І ось що це робить тут. Таким чином, це говорить якщо не свопи. Так що, якщо свопи дорівнює нулю, що is-- я завжди отримати мої істини і мої falses переплутали. Ми хочемо, щоб нам оцінити щоб вірно і це не так. Так що, якщо це нуль, то це брехня. Якщо ви заперечувати його [? бац?] стає правдою. Отже ця лінія виконує. 

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

СТУДЕНТ: Що перерву зробити? 

ВИКЛАДАЧ: Перерва просто ламає тебе з петлі. Таким чином, в даному випадку це було б так само, як завершити програму і ви б просто є свій відсортований список. СТУДЕНТ: Восхитительно. ВИКЛАДАЧ: Я шкодую? СТУДЕНТ: Бо раніше ми б написав 1 над написана нулю уявити, що якщо що буде працювати чи ні. 

ВИКЛАДАЧ: Так. Таким чином, ви можете повернутися до нуля або 1. В цьому випадку, тому що ми насправді не робити що-небудь за допомогою функції, ми просто хочемо, щоб зламати. Ми дійсно не піклуються про це. Гальмівна також добре, якщо він використовується для виходу з з чотирьох петель або умов, які Ви не хочете, щоб виконання. Це займе вас з них. Це щось на зразок нюанс речі. Я відчуваю, що є багато ручної завивки, як ви дізнаєтеся про це найближчим часом. 

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

СТУДЕНТ: [нерозбірливо] Int основний звичайно. Ви повинні мати, що для цього? 

ВИКЛАДАЧ: Таким чином, ми просто шукали просто за фактичною алгоритму сортування. Якщо ви мали його протягом як великої програми, Ви б мати Int основний десь. Залежно від того, де ви використовувати цей алгоритм, було б визначити, що повертається до неї. Але для нашого випадку, ми строго дивлячись на те, як це робить насправді перебору масиву. Таким чином, ми не турбуватися про це. 

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

СТУДЕНТ: N мінус 1. ВИКЛАДАЧ: N мінус 1. Значить, є н мінус 1 порівняння. Так одна справа розуміти, що на першій ітерації, ми йдемо до кінця, ми порівняємо ці two-- так от 1. Ці два, три, чотири. Таким чином, після однієї ітерації ми вже є чотири порівнянь. Коли я говорю про час виконання і п. N є кількістю порівнянь як функція від того, скільки елементів у нас є. Добре? 

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

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

Добре. Так що тепер, що це найкращий випадок виконання? СТУДЕНТ: Нуль? Або 1? 

ВИКЛАДАЧ: Так 1 буде одним порівняння. Право. 

СТУДЕНТ: N мінус 1? 

ВИКЛАДАЧ: Так що, так. Так н мінус 1. Всякий раз, коли у вас є таке поняття, як п мінус 1, ми, як правило, просто висадити його і ми просто скажемо, п, тому що ви є порівняти кожен з these-- кожної пари. Тому було б н мінус 1, який ми ми просто скажемо, приблизно н. Коли ви маєте справу з виконання, все в наближає. До тих пір, як експонента правильно, ви дуже добре. 

Ось як ми з нею боремося. Так що в кращому випадку це п, означає, що список вже відсортований, і все, що ми зробити, це запустити через і переконайтеся, що це сортуються. Прохолодний. Добре. Отже, як ви бачите тут, ми просто є ще кілька графіків. Так п квадрат. Fun. Набагато гірше, ніж п, як ми бачимо, і набагато, набагато гірше, ніж журналу 2n. І тоді ви також отримуєте в журналах журналів. І ви берете 124, ви отримаєте в як лог зірки, яка, як божевільний. Так що якщо ви зацікавлені, пошук журналу зірка. Це забавно. Тому у нас є цей великий графік. Просто голови, це чудовий графік, щоб мати для середньостроковій перспективі, тому що ми довго б задати вам ці рідшає. Так просто голови, тобто це на Середньостроковий на хорошому шпаргалку є. Таким чином, ми просто дивилися на бульбашкового сортування. В гіршому випадку, п квадрат, кращий випадок, п. І ми збираємося дивитися на інших. 

І як ви можете бачити, тільки той, який дійсно добре є сортування злиттям, які ми отримаємо в чому. Отже, ми збираємося піти в Наступний here-- вибір роду. Чи пам'ятає хтось, як Вибір роду працював? Піти на це. 

СТУДЕНТ: В основному йдуть через Порядок і створити новий список. І так само, як ви кладете елементи в, покласти їх в правильному місці в новому списку. 

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

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

Відсортований частину ви просто залишити в спокої. Мм-хм? 

СТУДЕНТ: Як це знаю, що це найменший, чи не порівнюючи його до кожного іншому значенню в масиві. ВИКЛАДАЧ: Він робить порівняти його. Нам подобається пропустив його. Це просто взагалі в цілому. Так. Коли ми пишемо код, я що ви будете більш задоволені. Але ви зберігаєте цей перший Елемент як найменше. Ви порівняйте, і ви сказати, в порядку, це менше? Так. Тримайте його. Ось це менше? Ні? 

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

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

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

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

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

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

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

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

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

Це означає, що, ну, ми перебору тут. Незалежно від значення тут не наш маленький річ. Ми не хочемо його. Ми хочемо, щоб перепризначити його. Так що, якщо ми перепризначення його, що робити Ви думаєте, може бути в цьому коді тут? Ми хочемо, щоб перепризначити маленький і положення. Так що це найменший в даний час? СТУДЕНТ: Array к. ВИКЛАДАЧ: Array к. І те, що це положення зараз? Що індекси наша найменше значення? Це просто к. Так масиву К, К, вони збігаються. Таким чином, ми хотіли передати це. А потім, коли ми виявили, що наш маленький, так в кінці цього для петлі Тут ми знайшли те, що наш маленький значення, так що ми просто поміняти його. В цьому випадку, як кажуть наші Найменше значення тут. Це наша найменше значення. 

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

не студенти: Для розміру, ви ніколи дійсно визначити або змінити його, як це дізнатися? 

ВИКЛАДАЧ: Так одна справа помітити тут є розмір внутр. Так ми говоримо в цьому sort-- роду є функція в цьому case-- це Вибір роду, він пройшов В з функцією. Так що, якщо він не був прийнятий в, ви могли б зробити щось як з довжиною масиву або ви б перебору щоб знайти довжину. Але тому що це пройшло в, ми можемо просто використовувати його. Ви просто припустимо, що користувач дав вам правильний розмір, що насправді являє розмір вашого масиву. Прохолодний? 

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

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

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

СТУДЕНТ: ви порівнюєте through-- ВИКЛАДАЧ: справа. Ти порівняння через. На кожній ітерації, незважаючи на те, ми зменшуючи це один, Ви все ще шукаєте через все, щоб знайти самі маленькі. Таким чином, навіть якщо ваша найменше значення Тут на початку, Ви все ще порівнюючи його проти всього іншого щоб переконатися, що це найменше. Таким чином, ви будете в кінцевому підсумку працює через приблизно н квадраті разів. Добре. І те, що в гіршому випадку? Також п квадраті, бо ви збираєтеся щоб робити ту ж саму процедуру. Так, в даному випадку, вибір зразок є щось що ми називаємо очікуваний час виконання. Таким чином, в інших, ми просто знаємо, верхні та нижні межі. Залежно від того, як з розуму нашого Список або як несортоване це, вони різняться між п або п квадрата. Ми не знаємо. 

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

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

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

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

Тоді ми подивимося на наш Наступний, і ми говоримо, 6. ОК, 6 більше, ніж все в нашому масиві, так що ми просто помітити його до кінця. А потім ми дивимося на 4. 4 менше, ніж 6, це менше, ніж 5, але це більше, ніж 3. Так що ми просто вставити його прямо в посередині між 3 і 5. Таким чином, щоб зробити що трохи трохи більш конкретними, ось ніби Ідея про те, що сталося. Таким чином, для кожного несортоване елемента, ми визначити, де в відсортованому частини це. 

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

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

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

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

Тому, коли J дорівнює 1, в цьому випадку і Масив J мінус одно-- так масив J мінус 1 2 в цьому case-- якщо це більше, ніж елемент, Потім все це робить зміщується речі вниз. Так, в даному випадку, масив J мінус один Масив буде нульовим, який є 2. 2 максимум, ніж 4, так що це не виконується. Так зрушення не з'їжджати. Що це робить тут просто переміщення відсортований масив вниз. В цьому випадку, насправді, ми може do-- давайте зробимо це 3. Так що, якщо ми хочемо йти через с цей приклад, ми зараз тут. Це сортується. Це несортоване. Прохолодний? Так я дорівнює 2, так наш елемент дорівнює 3. І наша J дорівнює 2. Таким чином, ми з нетерпінням через і ми сказати, в порядку, це масив J мінус один більше, ніж елемента що ми дивимося? І так, чи не так? 4 більше, ніж 3 і J 2, так що цей код виконується. 

Так що тепер, що ми робимо масив на 2, так прямо тут, ми поміняти їх місцями. Таким чином, ми просто сказати: ОК, масив на 2 тепер буде 3. І J збирається рівнятися J мінус 1, який дорівнює 1. Це жахливо, але ви, хлопці, отримаєте цю ідею. J тепер дорівнює 1. І масив J тільки збирається бути дорівнює нашого елемента, який був 4. Я стер щось я не повинен є або miswrote-то, але ви, хлопці, отримаєте цю ідею. 

Це рухатися в п. І потім, якби це було, це було б петля знову, і це було б сказати, в порядку, J = 1 тепер. І масив J мінус 1 тепер 2. Є 2 менше, ніж наші елемента? Ні? Це означає, що ми в вставляється цей елемент в правильному місці в нашому масиві. Тоді ми можемо взяти це, і ми говоримо, ОК, наш упорядкований масив тут. І це було б взяти цей номер 6 і бути як, в порядку, становить 6 менше, ніж це число? Ні? Прохолодний. У нас все добре. 

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

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

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

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

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

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

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

В іншому випадку це підводить це Останній елемент масиву, а потім приймає суму інша частина масиву. Так що це просто розбити його на все більш дрібні проблеми. Коротше кажучи, рекурсія, Функція, яка називає себе. Якщо це все, що ви вийшли з цього, це те, що рекурсивна функція. Якщо взяти 51, ви отримаєте дуже, дуже зручно за допомогою рекурсії. Це дійсно здорово. Це мало сенс в подібному 3 ранку одного разу вночі. І я подумала: чому Не я не використовую це? 

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

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

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

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

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

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

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

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

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