1 00:00:00,000 --> 00:00:03,332 >> [Грає музика] 2 00:00:03,332 --> 00:00:06,490 >> ANDI Пен: Ласкаво просимо в тиждень 3 розділу. 3 00:00:06,490 --> 00:00:09,550 Спасибі, що ви, хлопці, всі, хто входить на в цьому більш ранній час початку сьогодні. 4 00:00:09,550 --> 00:00:11,466 Ми отримали хороший, трохи інтимна група сьогодні. 5 00:00:11,466 --> 00:00:14,570 Так що сподіваюся, ми доберемося до обробка, мабуть, рано, 6 00:00:14,570 --> 00:00:15,780 трохи раніше. 7 00:00:15,780 --> 00:00:22,057 Так швидко, просто деякі Анонси порядку денному сьогодні. 8 00:00:22,057 --> 00:00:23,890 Перш ніж ми почнемо, ми збираюся просто перейти 9 00:00:23,890 --> 00:00:28,910 деякі короткі матеріально-технічних питань, PSET питання, Інструктаж, такі речі, як, що. 10 00:00:28,910 --> 00:00:30,250 І тоді ми будемо пірнати прямо в. 11 00:00:30,250 --> 00:00:34,710 Ми будемо використовувати відладчик GDB під назвою, щоб почати розвінчання наш код, який Девід 12 00:00:34,710 --> 00:00:36,550 пояснив в лекції в інший день. 13 00:00:36,550 --> 00:00:39,420 Ми підемо протягом чотирьох видів роду. 14 00:00:39,420 --> 00:00:42,310 Ми підемо на них досить швидко так як вони досить інтенсивно. 15 00:00:42,310 --> 00:00:45,710 Але знайте, що всі слайди і Вихідний код завжди онлайн. 16 00:00:45,710 --> 00:00:50,810 Так що не соромтеся, у вашому прочитанні, щоб повернутися назад і поглянути на це. 17 00:00:50,810 --> 00:00:53,930 >> Ми підемо через асимптотична позначення, які 18 00:00:53,930 --> 00:00:55,944 це просто химерний спосіб сказати "час автономної роботи", 19 00:00:55,944 --> 00:00:58,360 де у нас є великий O, яка Девід пояснив в лекції. 20 00:00:58,360 --> 00:01:01,550 І у нас також є Omega, який це нижня межа часу виконання. 21 00:01:01,550 --> 00:01:06,450 І ми будемо говорити трохи більше в глибині про те, як ці роботи. 22 00:01:06,450 --> 00:01:10,160 І, нарешті, ми підемо по бінарного пошуку, тому що багато з вас, хто вже 23 00:01:10,160 --> 00:01:15,190 глянув на ваших psets, напевно, знаєте, що що це питання, яке знаходиться у вашому PSET. 24 00:01:15,190 --> 00:01:17,470 Таким чином, ви будете всі будуть щасливі що ми розглянемо це сьогодні. 25 00:01:17,470 --> 00:01:20,610 >> І, нарешті, за ваш розділ зворотного зв'язку, я насправді 26 00:01:20,610 --> 00:01:23,000 залишилося близько 15 хвилин при кінець просто перейти 27 00:01:23,000 --> 00:01:27,730 логістика pset3, які-небудь питання, може бути, трохи керівництвом, якщо хочете, 28 00:01:27,730 --> 00:01:28,990 перш ніж ми почнемо програмування. 29 00:01:28,990 --> 00:01:30,890 Так давайте спробуємо отримати через матеріал досить швидко. 30 00:01:30,890 --> 00:01:33,880 І тоді ми можемо провести деякий час приймаючи більше питань для PSET. 31 00:01:33,880 --> 00:01:35,230 ДОБРЕ. 32 00:01:35,230 --> 00:01:39,570 >> Швидко, тому лише деякі Анонси перш ніж ми почнемо сьогодні. 33 00:01:39,570 --> 00:01:45,410 По-перше, ласкаво просимо, щоб зробити це через два ваших psets. 34 00:01:45,410 --> 00:01:49,432 Я глянув на your-- Так, давайте отримати оплески для цього одного. 35 00:01:49,432 --> 00:01:51,140 Насправді, я був дуже, дійсно вражений. 36 00:01:51,140 --> 00:01:55,800 Я оцінюються перші PSET для вас, хлопці минулого тижня і ви, хлопці, зробили неймовірне. 37 00:01:55,800 --> 00:01:58,290 >> Стиль був на момент крім кількох зауважень. 38 00:01:58,290 --> 00:02:00,660 Переконайтеся, що ви завжди Коментуючи свій код. 39 00:02:00,660 --> 00:02:03,040 Але ваші psets були на точці. 40 00:02:03,040 --> 00:02:05,549 І тримати його. 41 00:02:05,549 --> 00:02:08,090 І це добре для грейдера в бачити, що ви, хлопці, покласти 42 00:02:08,090 --> 00:02:10,704 як багато зусиль у вашому стилі і ваш дизайн в коді 43 00:02:10,704 --> 00:02:12,120 що ми хотіли б, щоб ви бачите. 44 00:02:12,120 --> 00:02:16,450 Так я передаю по моєї вдячності для решти ТП. 45 00:02:16,450 --> 00:02:19,210 >> Однак є Кілька питань танто 46 00:02:19,210 --> 00:02:22,010 Я просто хочу, щоб перейти на що як би життя 47 00:02:22,010 --> 00:02:24,900 і багато іншого ТП «живе трохи легше. 48 00:02:24,900 --> 00:02:28,220 По-перше, я помітив це повз week-- як багато з вас 49 00:02:28,220 --> 00:02:32,301 були працює на check50 код, перш ніж представити? 50 00:02:32,301 --> 00:02:32,800 ДОБРЕ. 51 00:02:32,800 --> 00:02:36,690 Таким чином, кожен повинен робити check50, because-- secret-- ми насправді 52 00:02:36,690 --> 00:02:41,540 запустити check50 як частина нашої правоті скрипти для тестування коду. 53 00:02:41,540 --> 00:02:45,480 Так що, якщо ваш код не вдається check50, цілком ймовірно, 54 00:02:45,480 --> 00:02:47,570 це, ймовірно, буде потерпіти невдачу також наш чек. 55 00:02:47,570 --> 00:02:49,320 Іноді ви, хлопці, є правильні відповіді. 56 00:02:49,320 --> 00:02:52,200 Мовляв, в жадібні, деякі з у вас є правильні цифри, 57 00:02:52,200 --> 00:02:53,960 Ви просто роздрукувати деякі додаткові речі. 58 00:02:53,960 --> 00:02:55,940 І, що додатковий матеріал насправді не проходить перевірку, 59 00:02:55,940 --> 00:02:58,440 бо комп'ютер не знаю, що він шукає. 60 00:02:58,440 --> 00:03:00,981 І так буде просто запустити через, бачити, що ваш висновок не 61 00:03:00,981 --> 00:03:03,810 відповідає тому, що ми очікуємо відповідь бути, і відзначте, що це неправильно. 62 00:03:03,810 --> 00:03:06,560 >> І я знаю, що відбулося в деякі з ваших випадках на цьому тижні. 63 00:03:06,560 --> 00:03:09,870 Так що я повернувся і вручну regraded код кожного. 64 00:03:09,870 --> 00:03:12,780 У майбутньому, хоча, Будь ласка, переконайтеся, що 65 00:03:12,780 --> 00:03:14,570 що ви працюєте перевірити 50 на коді. 66 00:03:14,570 --> 00:03:17,970 Тому що це свого роду болі в ТП щоб повернутися і вручну рекласифікацію 67 00:03:17,970 --> 00:03:21,197 кожен PSET для кожного один, трохи пропустив екземпляр. 68 00:03:21,197 --> 00:03:22,530 Так що я не знімав жодного очка. 69 00:03:22,530 --> 00:03:25,210 Я думаю, що, може бути, зняв один або два для проектування. 70 00:03:25,210 --> 00:03:27,710 У майбутньому, хоча, якщо Ви не справляються check50, 71 00:03:27,710 --> 00:03:31,330 точки будуть прийняті від правильності. 72 00:03:31,330 --> 00:03:35,020 >> Крім того, в psets за п'ятницях опівдні. 73 00:03:35,020 --> 00:03:38,990 Я думаю, що є сім хвилин в кінці пільгового періоду, що ми даємо вам. 74 00:03:38,990 --> 00:03:42,434 За час Гарвардського, вони дозволили сім хвилин пізно, щоб всім. 75 00:03:42,434 --> 00:03:44,350 Так от в Єльському університеті, ми будемо дотримуватися, що добре. 76 00:03:44,350 --> 00:03:47,910 Але досить багато, в 12:07, якщо ваш PSET це не в тому, 77 00:03:47,910 --> 00:03:49,720 це буде відзначений як пізно. 78 00:03:49,720 --> 00:03:53,160 І тому, хоча вона відзначається а пізно, я TA-- 79 00:03:53,160 --> 00:03:54,870 раніше буде класифікації ваші psets. 80 00:03:54,870 --> 00:03:56,760 Таким чином, ви все ще будете бачити сорт з'являються. 81 00:03:56,760 --> 00:03:58,820 Проте, відомо, що в кінець семестру, 82 00:03:58,820 --> 00:04:02,270 всі пізні psets буде просто автоматично обнуляється за допомогою комп'ютера. 83 00:04:02,270 --> 00:04:04,490 >> Ми робимо це з двох причин. 84 00:04:04,490 --> 00:04:09,220 Один з них, іноді ми отримуємо вибачився, як відмовки деканатів, 85 00:04:09,220 --> 00:04:10,762 пізніше, що я не знаю, про ще. 86 00:04:10,762 --> 00:04:13,761 Таким чином, ми хотіли, щоб переконатися, що ми класифікації все тільки в тому випадку, як, я 87 00:04:13,761 --> 00:04:15,080 відсутня пробачити декана. 88 00:04:15,080 --> 00:04:17,000 А по-друге, майте на розум, ви все ще можете 89 00:04:17,000 --> 00:04:19,370 падіння одна PSET, що володіє повними точки розмах. 90 00:04:19,370 --> 00:04:21,430 І таким чином, ми хотіли, щоб оцінка всі ваші psets тільки 91 00:04:21,430 --> 00:04:24,730 щоб переконатися, що ваш осцилографа є і ви намагаєтеся їх. 92 00:04:24,730 --> 00:04:29,150 Таким чином, навіть якщо це пізно, ви все ще будете отримати кредит для області видимості точок, я думаю. 93 00:04:29,150 --> 00:04:33,730 >> Так Мораль історія, зробити Переконайтеся, що ваш psets в за часом. 94 00:04:33,730 --> 00:04:38,350 І якщо вони не знаходяться в на час, знаю, що це не здорово. 95 00:04:38,350 --> 00:04:41,678 Так, перш ніж я рухатися далі, хто-небудь є будь-які питання, що стосуються зворотного зв'язку Pset? 96 00:04:41,678 --> 00:04:42,178 Так. 97 00:04:42,178 --> 00:04:43,630 >> АУДИТОРІЯ: Ви сказали, ми може впасти один з psets? 98 00:04:43,630 --> 00:04:44,296 >> ANDI Пен: Так. 99 00:04:44,296 --> 00:04:47,050 Так що загалом дев'ять psets протягом семестру. 100 00:04:47,050 --> 00:04:50,610 І якщо у вас є область points-- так просто сфера, 101 00:04:50,610 --> 00:04:53,567 досить багато, ви спробою виконання Проблема, ви покласти в час, 102 00:04:53,567 --> 00:04:56,150 ви показуєте, що ви маєте продемонстрували ви читали специфікації. 103 00:04:56,150 --> 00:04:57,191 Це досить багато можливостей. 104 00:04:57,191 --> 00:04:59,370 І якщо ви виконуєте Сфера точки, ми 105 00:04:59,370 --> 00:05:03,360 може впасти найнижча одним з повному обсязі. 106 00:05:03,360 --> 00:05:06,790 Так от у ваших інтересах, щоб заповнити та спробувати все PSET. 107 00:05:06,790 --> 00:05:10,320 >> Навіть якщо upload-- жоден з їм працювати, завантажувати їх усі. 108 00:05:10,320 --> 00:05:13,711 І тоді ми будемо, ми сподіваємося, зможуть дати вам деякі з цих точок назад. 109 00:05:13,711 --> 00:05:14,210 Прохолодний. 110 00:05:14,210 --> 00:05:16,780 Будь-які інші питання? 111 00:05:16,780 --> 00:05:17,840 Відмінно. 112 00:05:17,840 --> 00:05:21,960 >> По-друге, офіс hours-- кілька швидкі замітки про робочих годин. 113 00:05:21,960 --> 00:05:24,300 Отже, спочатку приходять на початку тижня. 114 00:05:24,300 --> 00:05:26,909 Ніхто не коли-небудь в Прийомні години по понеділках. 115 00:05:26,909 --> 00:05:28,700 Christabel прийшли до Прийомні години минулої ночі. 116 00:05:28,700 --> 00:05:29,691 Так, Christabel. 117 00:05:29,691 --> 00:05:32,190 І що ми маємо в офісі годин минулої ночі, Christabel? 118 00:05:32,190 --> 00:05:33,020 >> АУДИТОРІЯ: У нас було морозиво. 119 00:05:33,020 --> 00:05:36,160 >> ANDI Пен: Так що це правильно, ми повинні були морозиво на офісних годин вчора ввечері. 120 00:05:36,160 --> 00:05:39,390 Хоча я не можу обіцяти вам, що ми матимемо морозиво в робочий час 121 00:05:39,390 --> 00:05:43,230 щотижня, що я можу обіцяти вам, є те, що буде значно 122 00:05:43,230 --> 00:05:45,380 краще студент співвідношення TA. 123 00:05:45,380 --> 00:05:47,650 Як законно, це як три до одного. 124 00:05:47,650 --> 00:05:50,350 Беручи до уваги, що з контрастують Четвер, у вас є близько 150 125 00:05:50,350 --> 00:05:52,830 дійсно підкреслив дітей і не морозиво. 126 00:05:52,830 --> 00:05:55,360 І це просто не продуктивно для всіх. 127 00:05:55,360 --> 00:05:58,730 Так Мораль цієї історії в тому, прийти раніше в робочий час і хороші речі 128 00:05:58,730 --> 00:06:00,310 станеться. 129 00:06:00,310 --> 00:06:02,110 >> Крім того, бути готовими, щоб задати питання. 130 00:06:02,110 --> 00:06:03,200 Ти знаєш? 131 00:06:03,200 --> 00:06:05,420 Незалежно від того, ТА, я думаю, говорили, 132 00:06:05,420 --> 00:06:10,710 ми отримували пару студентів які приходять в четвер на, начебто, 10:50 133 00:06:10,710 --> 00:06:15,100 не прочитавши специфікацію будучи, як мені допомогти, допоможи мені. 134 00:06:15,100 --> 00:06:18,200 На жаль, в той момент, є не так багато ми можемо зробити, щоб допомогти вам. 135 00:06:18,200 --> 00:06:19,590 Так що приїжджайте на початку тижня. 136 00:06:19,590 --> 00:06:22,040 Приходьте раніше, щоб робочий час. 137 00:06:22,040 --> 00:06:23,350 Будьте готові задавати питання. 138 00:06:23,350 --> 00:06:25,310 Переконайтеся, що ви, як студент, знаходяться там, де 139 00:06:25,310 --> 00:06:27,620 Ви повинні бути так, що ТП може направляти вас разом 140 00:06:27,620 --> 00:06:32,850 що і години офісу повинні бути виділені для. 141 00:06:32,850 --> 00:06:37,380 >> По-друге, так що я знаю професорів хотів здивувати нас з тестами. 142 00:06:37,380 --> 00:06:39,439 Я був професором ті як, йо, до речі, 143 00:06:39,439 --> 00:06:41,230 пам'ятайте, що середньостроковий у вас є наступний понеділок. 144 00:06:41,230 --> 00:06:42,855 Так, я не знаю, про те, що середньостроковий. 145 00:06:42,855 --> 00:06:45,630 Так що я збираюся бути, що ТА що нагадує вам все, що вікторину 146 00:06:45,630 --> 00:06:47,270 0-- тому що, ви знаєте, ми CS. 147 00:06:47,270 --> 00:06:50,730 Тепер, коли ми зробили масиви, ви отримаєте чому це вікторина 0, не вікторини 1, а? 148 00:06:50,730 --> 00:06:51,320 ДОБРЕ. 149 00:06:51,320 --> 00:06:52,490 О, я отримав деякі смішки на тому, що один. 150 00:06:52,490 --> 00:06:53,120 ДОБРЕ. 151 00:06:53,120 --> 00:06:59,710 >> Так вікторини 0 буде 14 жовтня, якщо Ви знаходитесь у розділі понеділок-середу 152 00:06:59,710 --> 00:07:02,920 і 15 жовтня, якщо ви перебуваєте в розділ вівторок-четвер. 153 00:07:02,920 --> 00:07:05,630 Це не поширюється на тих з вас, в Гарварді 154 00:07:05,630 --> 00:07:10,350 who-- Я думаю, ви всі будете приймати ваші опитування на 14-му. 155 00:07:10,350 --> 00:07:13,560 >> Так що, так, наступного тижня, якщо Девід, в лекції, йде, 156 00:07:13,560 --> 00:07:15,747 да, так про це Тест на наступному тижні, ви все 157 00:07:15,747 --> 00:07:17,580 НЕ будуть шоковані, бо ви прийшли в розділі 158 00:07:17,580 --> 00:07:19,664 і ви знаєте, що ваш Тест 0 протягом двох тижнів. 159 00:07:19,664 --> 00:07:21,580 І ми будемо мати відгук сесій і все. 160 00:07:21,580 --> 00:07:26,360 Так що не турбуйтеся про боятися за це. 161 00:07:26,360 --> 00:07:29,890 Будь-які питання before-- які-небудь питання на всіх стосуються технічних питань, 162 00:07:29,890 --> 00:07:32,591 класифікації, офісна годин, секції? 163 00:07:32,591 --> 00:07:33,090 Так. 164 00:07:33,090 --> 00:07:35,100 >> АУДИТОРІЯ: Так вікторини буде на лекції? 165 00:07:35,100 --> 00:07:35,766 >> ANDI Пен: Так. 166 00:07:35,766 --> 00:07:39,460 Так вікторини, я думаю, 60 хвилин, виділені цього часовому інтервалі 167 00:07:39,460 --> 00:07:42,240 що ви будете просто взяти в лекційному залі. 168 00:07:42,240 --> 00:07:44,810 Таким чином, ви не повинні прийти в на, начебто, випадкового 7:00 PM. 169 00:07:44,810 --> 00:07:46,140 Це все добре. 170 00:07:46,140 --> 00:07:47,100 Так. 171 00:07:47,100 --> 00:07:50,060 Прохолодний. 172 00:07:50,060 --> 00:07:50,840 >> Добре. 173 00:07:50,840 --> 00:07:54,330 Отже, ми збираємося, щоб ввести поняття для вас 174 00:07:54,330 --> 00:08:00,760 На цьому тижні, що Девід вже начебто з торкнулися в лекції минулого тижня. 175 00:08:00,760 --> 00:08:02,010 Це називається GDB. 176 00:08:02,010 --> 00:08:05,570 І, як багато з вас, в той час як в курс написання psets, 177 00:08:05,570 --> 00:08:09,981 помітив велику кнопку, яка говорить "Налагодження" на верхній частині IDE? 178 00:08:09,981 --> 00:08:10,480 ДОБРЕ. 179 00:08:10,480 --> 00:08:13,770 Так що тепер ми насправді отримати, щоб розкопати таємниця какой то кнопки насправді 180 00:08:13,770 --> 00:08:14,270 робить. 181 00:08:14,270 --> 00:08:16,790 І я гарантую вам, що це красива, красива річ. 182 00:08:16,790 --> 00:08:20,740 >> Так до сих пір, я думаю, там було дві речі 183 00:08:20,740 --> 00:08:23,320 студенти були, як правило, робити при налагодженні psets. 184 00:08:23,320 --> 00:08:27,635 Один з них, вони або додати в Е () - так кожні кілька ліній, 185 00:08:27,635 --> 00:08:29,760 вони додають в Е () - ой, що це змінна? 186 00:08:29,760 --> 00:08:32,551 О, що це змінна now-- і ви начебто побачити прогресування 187 00:08:32,551 --> 00:08:33,940 ваш код, як це працює. 188 00:08:33,940 --> 00:08:37,030 Або другий спосіб зробити дітей що вони просто написати цілу річ 189 00:08:37,030 --> 00:08:38,610 а потім перейти, як це в кінці кінців. 190 00:08:38,610 --> 00:08:39,970 Сподіваюся, це працює. 191 00:08:39,970 --> 00:08:44,851 Я гарантую вам, GDB краще ніж обидва з цих методів. 192 00:08:44,851 --> 00:08:45,350 Так. 193 00:08:45,350 --> 00:08:46,980 Так що це буде ваш новий кращий друг. 194 00:08:46,980 --> 00:08:51,780 Тому що це гарна річ які візуально відображає як 195 00:08:51,780 --> 00:08:54,850 що ваш код робить в певний момент 196 00:08:54,850 --> 00:08:57,486 а також те, що всі ваші змінні проведення, 197 00:08:57,486 --> 00:08:59,610 як те, що їх значення, в цій конкретній точці. 198 00:08:59,610 --> 00:09:02,670 І таким чином, ви можете дійсно встановити точки зупину в коді. 199 00:09:02,670 --> 00:09:04,350 Ви можете запустити через лінію за лінією. 200 00:09:04,350 --> 00:09:07,324 І GDB буде просто для Ви, відображається для вас, 201 00:09:07,324 --> 00:09:09,490 те, що всі ваші змінні які, що вони роблять, 202 00:09:09,490 --> 00:09:10,656 що відбувається в коді. 203 00:09:10,656 --> 00:09:13,240 І таким чином, це так легше побачити 204 00:09:13,240 --> 00:09:17,120 що замість відбувається через тов PRINTF або записуючи свої заяви. 205 00:09:17,120 --> 00:09:19,160 >> Таким чином, ми будемо робити приклад це пізніше. 206 00:09:19,160 --> 00:09:20,660 Таким чином, це здається трохи абстрактним. 207 00:09:20,660 --> 00:09:23,490 Не турбуйтеся, ми не будемо робити приклади. 208 00:09:23,490 --> 00:09:29,170 І так, по суті, три найбільших, Найбільш використовувані функції вам потрібно в GDB 209 00:09:29,170 --> 00:09:32,500 є Далі, переступити і крок в кнопки. 210 00:09:32,500 --> 00:09:34,860 Я збираюся очолити Тобто, насправді, просто зараз. 211 00:09:34,860 --> 00:09:40,930 >> Так може ви, хлопці, все бачити, що або я повинен збільшити трохи? 212 00:09:40,930 --> 00:09:43,220 213 00:09:43,220 --> 00:09:44,470 У спину, ви можете бачити, що? 214 00:09:44,470 --> 00:09:45,730 Чи повинен я збільшити? 215 00:09:45,730 --> 00:09:46,480 Лише трохи? 216 00:09:46,480 --> 00:09:49,390 ОК здорово. 217 00:09:49,390 --> 00:09:50,280 Там ми йдемо. 218 00:09:50,280 --> 00:09:50,960 ДОБРЕ. 219 00:09:50,960 --> 00:09:57,000 >> Так що я, от, моя Реалізація для жадібний. 220 00:09:57,000 --> 00:10:01,430 І в той час як багато хто з вас, хлопці писали жадібні в той час як петлі form--, що 221 00:10:01,430 --> 00:10:04,890 це цілком прийнятно спосіб зробити it-- інший спосіб зробити це, щоб просто 222 00:10:04,890 --> 00:10:06,280 розділити на модулю. 223 00:10:06,280 --> 00:10:09,290 Бо тоді ви можете мати свій значення, а потім мати свій залишок. 224 00:10:09,290 --> 00:10:11,150 І тоді ви можете просто додати все це разом. 225 00:10:11,150 --> 00:10:13,390 Лі логіка, що я роблю тут сенс для всіх, 226 00:10:13,390 --> 00:10:14,117 перш ніж ми почнемо? 227 00:10:14,117 --> 00:10:16,760 228 00:10:16,760 --> 00:10:17,980 Типу? 229 00:10:17,980 --> 00:10:18,710 Прохолодний. 230 00:10:18,710 --> 00:10:19,210 Відмінно. 231 00:10:19,210 --> 00:10:21,290 Це досить сексуальна частина коду, я б сказав. 232 00:10:21,290 --> 00:10:23,502 Як я вже сказав, Давид, в лекції, через деякий час, 233 00:10:23,502 --> 00:10:25,960 ви все починаєте бачити код як щось, що красиво. 234 00:10:25,960 --> 00:10:29,950 І іноді, коли ви бачите красивий Код, це такий чудовий відчуття. 235 00:10:29,950 --> 00:10:35,410 >> Так, однак, в той час як цей код дуже красиво, це не працює належним чином. 236 00:10:35,410 --> 00:10:37,750 Так що давайте працювати check50 на цьому. 237 00:10:37,750 --> 00:10:39,440 Перевірте 50 20-- уп. 238 00:10:39,440 --> 00:10:43,221 239 00:10:43,221 --> 00:10:43,720 2? 240 00:10:43,720 --> 00:10:44,990 Це pset2? 241 00:10:44,990 --> 00:10:46,870 Так. 242 00:10:46,870 --> 00:10:47,520 О, pset1. 243 00:10:47,520 --> 00:10:50,970 244 00:10:50,970 --> 00:10:52,890 ДОБРЕ. 245 00:10:52,890 --> 00:10:53,900 Таким чином, ми працювати check50. 246 00:10:53,900 --> 00:11:01,550 247 00:11:01,550 --> 00:11:07,170 >> І, як ви, хлопці, можете подивитися тут, це нездатність пару випадків. 248 00:11:07,170 --> 00:11:10,165 І для деяких з вас, в Звичайно робити свої проблемні набори, 249 00:11:10,165 --> 00:11:11,110 ви, як, ах, чому воно не працює. 250 00:11:11,110 --> 00:11:13,318 Чому це працює для деяких значення, але не для інших? 251 00:11:13,318 --> 00:11:17,760 Ну, GDB буде допомогти вам зрозуміти чому ці входи не працювали. 252 00:11:17,760 --> 00:11:18,320 >> ДОБРЕ. 253 00:11:18,320 --> 00:11:21,640 Отже, давайте подивимося, одне з перевіряє мене невдачу в check50 254 00:11:21,640 --> 00:11:24,920 був вхідне значення 0,41. 255 00:11:24,920 --> 00:11:27,830 Таким чином, правильна відповідь, що ви повинні отримувати це 4. 256 00:11:27,830 --> 00:11:33,090 Але замість того, що я роздруківки це 3-н, що невірно. 257 00:11:33,090 --> 00:11:36,190 Так що давайте просто запустити вручну, просто переконайтеся, що check50 працює. 258 00:11:36,190 --> 00:11:36,940 Давайте зробимо ./greedy. 259 00:11:36,940 --> 00:11:40,130 260 00:11:40,130 --> 00:11:43,340 Ой, я повинен зробити жодній. 261 00:11:43,340 --> 00:11:43,840 Там ми йдемо. 262 00:11:43,840 --> 00:11:44,381 Тепер ./greedy. 263 00:11:44,381 --> 00:11:46,950 264 00:11:46,950 --> 00:11:47,670 >> Скільки прочитується? 265 00:11:47,670 --> 00:11:49,550 Давайте зробимо 0.41. 266 00:11:49,550 --> 00:11:52,590 І так, ми бачимо тут що це висновок 3 267 00:11:52,590 --> 00:11:55,160 коли правильну відповідь, Справді, має бути 4. 268 00:11:55,160 --> 00:12:01,460 Так що давайте ввести GDB і подивитися, як ми може йти про фіксацію цієї проблеми. 269 00:12:01,460 --> 00:12:03,992 >> Отже, перший крок в завжди налагодження коду 270 00:12:03,992 --> 00:12:05,950 це встановити точку зупину, або точка, в якій ви 271 00:12:05,950 --> 00:12:09,079 хочу комп'ютера або відладчик, щоб почати дивитися. 272 00:12:09,079 --> 00:12:11,120 Так що, якщо ви дійсно не знаю, що ваша проблема, 273 00:12:11,120 --> 00:12:14,670 Зазвичай, типовий, що ми хочемо, щоб зробити, це встановити точку зупину на наш основний. 274 00:12:14,670 --> 00:12:18,520 Так що, якщо ви, хлопці, можете бачити це червона кнопка поруч, 275 00:12:18,520 --> 00:12:22,860 Так, це було мені встановивши зупину для головної функції. 276 00:12:22,860 --> 00:12:24,130 Я натисніть що. 277 00:12:24,130 --> 00:12:26,130 >> І тоді я можу піти до моєї кнопки Debug. 278 00:12:26,130 --> 00:12:27,036 Я вдарив цю кнопку. 279 00:12:27,036 --> 00:12:31,710 280 00:12:31,710 --> 00:12:36,555 Дозвольте мені віддалитися, якщо я можу. 281 00:12:36,555 --> 00:12:38,020 Там ми йдемо. 282 00:12:38,020 --> 00:12:40,730 Таким чином, ми маємо тут, панель праворуч. 283 00:12:40,730 --> 00:12:43,680 Я перепрошую, хлопці в спину, ви не можу бачити дуже добре. 284 00:12:43,680 --> 00:12:49,090 Але по суті, все це право панель робить 285 00:12:49,090 --> 00:12:53,130 є відстеження і виділений лінія, яка є рядок коду 286 00:12:53,130 --> 00:12:56,640 що комп'ютер в даний момент, а також всі ваші змінні 287 00:12:56,640 --> 00:12:57,600 сюди. 288 00:12:57,600 --> 00:13:00,487 >> Отже, ви отримали центів, монети, п, оголошені на різні речі 289 00:13:00,487 --> 00:13:01,070 в цій точці. 290 00:13:01,070 --> 00:13:04,850 Не турбуйтеся, тому що у нас немає насправді не ініціалізації їх до будь змінним ще. 291 00:13:04,850 --> 00:13:07,200 Таким чином, у вашому комп'ютері, ваш Комп'ютер просто бачачи, 292 00:13:07,200 --> 00:13:14,376 ой, 32767 був останній використовувана функція цього простору пам'яті в моєму комп'ютері. 293 00:13:14,376 --> 00:13:16,000 І так ось де центів в даний час. 294 00:13:16,000 --> 00:13:19,360 Але ні що колись ви не запустите код, вона повинна стати ініціалізації. 295 00:13:19,360 --> 00:13:24,110 >> Так давайте пройдемо, лінію лінія, те, що тут відбувається. 296 00:13:24,110 --> 00:13:25,350 ДОБРЕ. 297 00:13:25,350 --> 00:13:29,400 Так тут є три кнопки, які я тільки що пояснив. 298 00:13:29,400 --> 00:13:34,090 Ви повинні грати, або функцію Run, Кнопка, у вас є Крок за кнопку, 299 00:13:34,090 --> 00:13:36,600 і у вас також є Крок у кнопки. 300 00:13:36,600 --> 00:13:41,260 І, по суті, всі три їм просто пройти через код 301 00:13:41,260 --> 00:13:42,690 і робити різні речі. 302 00:13:42,690 --> 00:13:45,680 >> Так зазвичай, коли ви налагодження, ми не хочемо, щоб просто натиснути Play, 303 00:13:45,680 --> 00:13:47,930 тому Гра буде просто запустити код до кінця цього. 304 00:13:47,930 --> 00:13:49,070 І тоді у вас не буде насправді знаю, що ваша проблема 305 00:13:49,070 --> 00:13:51,432 Тобто, якщо ви не встановите кілька точок зупину. 306 00:13:51,432 --> 00:13:53,890 Якщо ви встановите кілька точок зупину, це буде просто автоматично 307 00:13:53,890 --> 00:13:56,030 бігти від однієї точки зупину, до іншого, щоб наступного. 308 00:13:56,030 --> 00:13:58,030 Але в цьому випадку ми в тільки, що один, тому що ми 309 00:13:58,030 --> 00:13:59,970 хочу працювати наш шлях зверху вниз вниз. 310 00:13:59,970 --> 00:14:04,830 Отже, ми збираємося, щоб ігнорувати цю кнопку зараз для цілей цієї програми. 311 00:14:04,830 --> 00:14:08,230 >> Так Крок над функцією тільки переступає кожного рядка 312 00:14:08,230 --> 00:14:11,510 і говорить вам, що комп'ютер робить. 313 00:14:11,510 --> 00:14:14,630 Крок у функції йде в реальній функції 314 00:14:14,630 --> 00:14:16,000 це на рядку коду. 315 00:14:16,000 --> 00:14:19,070 Так, наприклад, як Е (), , Яка є функцією, вірно? 316 00:14:19,070 --> 00:14:21,980 Якби я хотів, щоб фізично крок у функції Е (), 317 00:14:21,980 --> 00:14:25,610 Я б насправді йти в частині Код, де Е () була написана і подивитися, 318 00:14:25,610 --> 00:14:26,730 те, що там відбувається. 319 00:14:26,730 --> 00:14:29,924 >> Але, як правило, ми припускаємо, що код, який ми даємо вам роботи. 320 00:14:29,924 --> 00:14:31,340 Ми припускаємо, що Е () працює. 321 00:14:31,340 --> 00:14:33,170 Ми припускаємо, що GetInt () працює. 322 00:14:33,170 --> 00:14:35,170 Таким чином, немає ніякої необхідності крок у цих функцій. 323 00:14:35,170 --> 00:14:37,170 Але якщо є функції що ви пишете самі 324 00:14:37,170 --> 00:14:39,060 що ви хочете, щоб перевірити , Що відбувається, 325 00:14:39,060 --> 00:14:41,200 Ви хотіли б крок в цій функції. 326 00:14:41,200 --> 00:14:43,940 >> Так що зараз ми тільки збираємося переступити цей шматок коду. 327 00:14:43,940 --> 00:14:44,485 Отже, давайте подивимося. 328 00:14:44,485 --> 00:14:46,547 О, друк, "Про Хай, як багато змін прочитується? " 329 00:14:46,547 --> 00:14:47,130 Ми не хвилює. 330 00:14:47,130 --> 00:14:49,830 Ми знаємо, що працює, таким чином, ми крок за неї. 331 00:14:49,830 --> 00:14:53,290 >> Так п, яка є нашим поплавок, що ми в initialized-- або declared-- 332 00:14:53,290 --> 00:14:56,810 нагорі, ми тепер рівна, що GetFloat (). 333 00:14:56,810 --> 00:14:57,810 Отже, давайте переступити що. 334 00:14:57,810 --> 00:14:59,580 І ми бачимо, на Нижня тут, програма 335 00:14:59,580 --> 00:15:03,360 спонукає мене до входу значення. 336 00:15:03,360 --> 00:15:08,580 Отже, давайте Введіть значення ми хочемо перевірити тут, що 0,41. 337 00:15:08,580 --> 00:15:09,160 Відмінно. 338 00:15:09,160 --> 00:15:12,780 >> Так що тепер N-- ви, хлопці, бачите тут, на bottom-- це 339 00:15:12,780 --> 00:15:15,140 stored--, тому що ми ще не округляється, це 340 00:15:15,140 --> 00:15:19,540 зберігаються в цьому, як гігант поплавок, який +0,4099999996, 341 00:15:19,540 --> 00:15:22,550 який знаходиться досить близько до нашого Цілі, прямо зараз, до 0,41. 342 00:15:22,550 --> 00:15:26,090 І тоді ми побачимо надалі, як ми продовжувати просування за програмою, 343 00:15:26,090 --> 00:15:29,850 Після тут, н стало округлі і центів стала 41. 344 00:15:29,850 --> 00:15:30,350 Відмінно. 345 00:15:30,350 --> 00:15:32,230 Отже, ми знаємо, що робота нашої округлення в. 346 00:15:32,230 --> 00:15:34,700 Ми знаємо, що у нас є правильне число центів, 347 00:15:34,700 --> 00:15:36,990 так що ми знаємо, що це насправді не проблема. 348 00:15:36,990 --> 00:15:40,050 >> Таким чином, ми як і раніше крокувати у цій програмі. 349 00:15:40,050 --> 00:15:40,900 Ми йдемо сюди. 350 00:15:40,900 --> 00:15:46,139 І так після цього рядка коду, ми повинні знати, скільки чверті у нас є. 351 00:15:46,139 --> 00:15:46,680 Ми переступити. 352 00:15:46,680 --> 00:15:52,040 І ви бачите, ми, насправді, є один чверть, тому що ми вичитали 25 353 00:15:52,040 --> 00:15:53,790 з нашого початкового значення 41. 354 00:15:53,790 --> 00:15:55,890 І у нас є 16 залишається нашим центів. 355 00:15:55,890 --> 00:15:58,830 >> Чи розуміє все, як програма покрокового 356 00:15:58,830 --> 00:16:02,980 і чому центів стала 16 і чому, в даний час, монети став 1? 357 00:16:02,980 --> 00:16:04,610 Всі наступне, що логіка? 358 00:16:04,610 --> 00:16:05,110 Прохолодний. 359 00:16:05,110 --> 00:16:07,860 Так, як в даний момент, Робоча програма, вірно? 360 00:16:07,860 --> 00:16:09,797 Ми знаємо, що це саме робити те, що ми хочемо. 361 00:16:09,797 --> 00:16:11,880 І ми насправді не повинні роздрукувати, ах, який 362 00:16:11,880 --> 00:16:14,430 є центів на даний момент, що монети в цій точці. 363 00:16:14,430 --> 00:16:17,170 >> Ми продовжуємо йти за програмою. 364 00:16:17,170 --> 00:16:18,100 Крок за. 365 00:16:18,100 --> 00:16:18,620 Прохолодний. 366 00:16:18,620 --> 00:16:19,700 Ми йдемо по десять центів. 367 00:16:19,700 --> 00:16:20,200 Відмінно. 368 00:16:20,200 --> 00:16:22,367 Ми бачимо, що це зайняло від $ 0.10 за копійки. 369 00:16:22,367 --> 00:16:23,450 І тепер у нас є дві монети. 370 00:16:23,450 --> 00:16:25,260 Це правильно. 371 00:16:25,260 --> 00:16:31,555 >> Перейдемо гроши, і ми бачимо що ми отримали, що залишилися центів. 372 00:16:31,555 --> 00:16:32,680 Хм, це дивно. 373 00:16:32,680 --> 00:16:37,540 До тут програми, я повинен був щоб відняли мої гроші. 374 00:16:37,540 --> 00:16:39,400 Може бути, я просто не був робить цей рядок право. 375 00:16:39,400 --> 00:16:42,190 І, на жаль, ви можете побачити тут, тому що ми знаємо, 376 00:16:42,190 --> 00:16:44,360 що ми вступаємо через лінії 32 і 33, 377 00:16:44,360 --> 00:16:50,560 ось де наша програма неправильно було змінні працювати. 378 00:16:50,560 --> 00:16:55,136 Таким чином, ми можемо подивитися і побачити, о, Я віднімання центів тут, 379 00:16:55,136 --> 00:16:57,010 але я насправді не додаючи до моєї вартості монети. 380 00:16:57,010 --> 00:16:57,860 Я додаю до центів. 381 00:16:57,860 --> 00:17:00,234 І я не хочу, щоб додати до центів, я хочу, щоб додати до монетам. 382 00:17:00,234 --> 00:17:05,420 Так що, якщо ми змінюємо що монети, ми отримали робочу програму. 383 00:17:05,420 --> 00:17:06,730 Я можу запустити check50. 384 00:17:06,730 --> 00:17:11,063 Ви можете просто вийти з GDB права тут і потім запустити check50 знову. 385 00:17:11,063 --> 00:17:11,938 Я міг би просто зробити це. 386 00:17:11,938 --> 00:17:14,822 387 00:17:14,822 --> 00:17:18,480 Я повинен зробити жодній. 388 00:17:18,480 --> 00:17:19,940 0,41. 389 00:17:19,940 --> 00:17:22,819 І ось, це друк з правильної відповіді. 390 00:17:22,819 --> 00:17:26,569 >> Отже, як ви, хлопці, можете бачити, GDB це дійсно потужний інструмент 391 00:17:26,569 --> 00:17:29,940 коли у нас так багато коду відбувається, і так багато змінних 392 00:17:29,940 --> 00:17:32,510 що це важко для нас, як людині, щоб відстежувати. 393 00:17:32,510 --> 00:17:35,360 Комп'ютер, в GDB відладчик, має можливість 394 00:17:35,360 --> 00:17:37,020 щоб відстежувати все. 395 00:17:37,020 --> 00:17:40,480 Я знаю, в Visionaire, ви, хлопці, ймовірно, можливо, потрапили деякі помилки сегментації 396 00:17:40,480 --> 00:17:43,150 тому що ви бігли поза межами вашого масиву. 397 00:17:43,150 --> 00:17:46,510 У прикладі Цезаря, це саме те, що я тут реалізована. 398 00:17:46,510 --> 00:17:50,060 >> Так що я забув, щоб перевірити що б сталося, якби я 399 00:17:50,060 --> 00:17:52,510 не мають два аргументи командного рядка. 400 00:17:52,510 --> 00:17:53,880 Я просто не ставили в цьому чеку. 401 00:17:53,880 --> 00:17:57,380 І тому, якщо я біжу Debug-- я поставив мій зупину направо там. 402 00:17:57,380 --> 00:17:58,055 Я біжу Debug. 403 00:17:58,055 --> 00:18:15,880 404 00:18:15,880 --> 00:18:16,550 >> ДОБРЕ. 405 00:18:16,550 --> 00:18:17,050 Так. 406 00:18:17,050 --> 00:18:20,350 Так насправді, GDB повинен був , Що сказав мені, що 407 00:18:20,350 --> 00:18:22,300 був збій сегментації там. 408 00:18:22,300 --> 00:18:24,883 Я не знаю, що відбувається тут, але, коли я побіг, 409 00:18:24,883 --> 00:18:25,590 вона працює. 410 00:18:25,590 --> 00:18:29,410 При запуску рядків коду через і GDB може просто раптово кинути на вас, 411 00:18:29,410 --> 00:18:31,540 йти і дивитися те, що червоний помилка. 412 00:18:31,540 --> 00:18:33,930 Це вам скажу, гей, ти була помилку сегментації, 413 00:18:33,930 --> 00:18:38,550 Це означає, що ви намагалися отримати доступ простір в масиві, що не існує. 414 00:18:38,550 --> 00:18:39,050 Так. 415 00:18:39,050 --> 00:18:43,280 >> Таким чином, в наступній проблемі встановлені на цьому тижні, ви, хлопці, 416 00:18:43,280 --> 00:18:45,600 ймовірно, буде багато змінні з плаваючою навколо. 417 00:18:45,600 --> 00:18:48,560 Ви не збираєтеся бути впевнені, що Всі вони мають на увазі в певний момент. 418 00:18:48,560 --> 00:18:53,560 Так GDB дійсно допоможе вам в з'ясовуючи те, що вони все зрівнявшись 419 00:18:53,560 --> 00:18:55,940 і бути в змозі бачити, що візуально. 420 00:18:55,940 --> 00:19:01,995 Хто плутати від того, як небудь з цього працював? 421 00:19:01,995 --> 00:19:02,495 Прохолодний. 422 00:19:02,495 --> 00:19:10,121 423 00:19:10,121 --> 00:19:10,620 Добре. 424 00:19:10,620 --> 00:19:14,260 Таким чином, після того, що ми збирається зануритися 425 00:19:14,260 --> 00:19:17,562 в чотири різних типи сортів на цьому тижні. 426 00:19:17,562 --> 00:19:19,520 Як багато з вас, перш все, перш ніж ми почнемо, 427 00:19:19,520 --> 00:19:23,020 прочитав усю специфікацію для pset3? 428 00:19:23,020 --> 00:19:23,824 ДОБРЕ. 429 00:19:23,824 --> 00:19:24,740 Я пишаюся вами, хлопці. 430 00:19:24,740 --> 00:19:29,110 Ось як половина класу, який значно більше, ніж минулого разу. 431 00:19:29,110 --> 00:19:33,950 >> Так що здорово, тому що, коли ми говоримо про зміст 432 00:19:33,950 --> 00:19:36,170 в lecture-- або вибачте, в section-- Мені подобається 433 00:19:36,170 --> 00:19:38,210 зв'язати багато, що назад до того, що це PSET 434 00:19:38,210 --> 00:19:40,210 і як ви хочете, щоб здійснити, що у вашому PSET. 435 00:19:40,210 --> 00:19:42,400 Так що, якщо ви приходите, що мають читати специфікації, він буде 436 00:19:42,400 --> 00:19:45,510 буде набагато простіше для вас, щоб зрозуміти, те, що я говорю про те, коли я кажу, 437 00:19:45,510 --> 00:19:48,720 агов, це може бути дійсно гарне місце для реалізації такого роду. 438 00:19:48,720 --> 00:19:52,870 Так що ті, з вас, хто читав особое_разрешеніе знаю, що, як частина вашого PSET, 439 00:19:52,870 --> 00:19:54,900 Ви будете мати, щоб написати тип роду. 440 00:19:54,900 --> 00:19:58,670 Так що це може бути дуже корисно для багатьох з вас сьогодні. 441 00:19:58,670 --> 00:20:01,760 >> Таким чином, ми почнемо з того, по суті, найпростіший тип 442 00:20:01,760 --> 00:20:04,580 з роду, вибір роду. 443 00:20:04,580 --> 00:20:06,800 Типовий алгоритм як ми йти про це 444 00:20:06,800 --> 00:20:10,460 is-- Давид через них все в лекція, так що я буду швидко рухатися уздовж 445 00:20:10,460 --> 00:20:13,900 here-- суті, ви є масив значень. 446 00:20:13,900 --> 00:20:17,170 І тоді ви знайдете маленький несортоване значення 447 00:20:17,170 --> 00:20:20,200 і ви поміняти це значення з перший несортоване значення. 448 00:20:20,200 --> 00:20:22,700 А потім ви просто повторювати з іншої частини списку. 449 00:20:22,700 --> 00:20:25,740 >> І ось наочне пояснення про те, як це буде працювати. 450 00:20:25,740 --> 00:20:30,460 Так, наприклад, якщо ми повинні були почати з масивом з п'яти елементів, індекс 451 00:20:30,460 --> 00:20:35,910 Від 0 до 4, з 3, 5, 2, 6, і 4 значення поміщений в array-- це прямо зараз, 452 00:20:35,910 --> 00:20:38,530 ми просто будемо вважати, що вони все без сортування 453 00:20:38,530 --> 00:20:41,130 бо ми не зазнали в іншому випадку. 454 00:20:41,130 --> 00:20:44,130 >> Так як вибір роду буде робота, що б перш 455 00:20:44,130 --> 00:20:46,800 проходять через повністю в несортованих масиву. 456 00:20:46,800 --> 00:20:49,120 Було б вибрати найменше значення. 457 00:20:49,120 --> 00:20:51,750 У цьому випадку, 3, правий Тепер, є найменшим. 458 00:20:51,750 --> 00:20:52,680 Він отримує до 5. 459 00:20:52,680 --> 00:20:55,620 Ні, 5 не більш than-- або вибачте, не менш 3 than--. 460 00:20:55,620 --> 00:20:57,779 Таким чином, мінімальне значення раніше 3. 461 00:20:57,779 --> 00:20:58,695 І тоді ви отримаєте 2. 462 00:20:58,695 --> 00:21:00,990 Комп'ютер бачить, ой, 2 менше, ніж 3. 463 00:21:00,990 --> 00:21:02,750 Тепер 2 повинно бути мінімальне значення. 464 00:21:02,750 --> 00:21:06,630 І так 2 свопи з цієї першої величини. 465 00:21:06,630 --> 00:21:10,702 >> Таким чином, після одного проходу, ми дійсно бачимо що 2 і 3 міняються місцями. 466 00:21:10,702 --> 00:21:13,910 І ми тільки збираємося продовжувати робити Це знову з іншою частиною масиву. 467 00:21:13,910 --> 00:21:17,660 Отже, ми збираємося, щоб просто запустити через Останні чотири індекси масиву. 468 00:21:17,660 --> 00:21:20,670 Ми побачимо, що 3 наступний мінімальне значення. 469 00:21:20,670 --> 00:21:23,240 Отже, ми збираємося, щоб поміняти що з 4. 470 00:21:23,240 --> 00:21:26,900 І тоді ми просто будемо продовжувати не проходить через до, в кінці кінців, ви 471 00:21:26,900 --> 00:21:33,730 потрапити в відсортованому масиві, в якому 2, 3, 4, 5, 6 і всі сортуються. 472 00:21:33,730 --> 00:21:37,530 Всі розуміють чи логіку про те, як працює вибір роду? 473 00:21:37,530 --> 00:21:39,669 >> Ви просто є якийсь мінімального значення. 474 00:21:39,669 --> 00:21:41,210 Ви відстежувати, що це таке. 475 00:21:41,210 --> 00:21:45,170 І всякий раз, коли ви знайдете його, ви поміняти його з першим значенням в array-- 476 00:21:45,170 --> 00:21:48,740 або, не перший value-- таке значення в масиві. 477 00:21:48,740 --> 00:21:50,150 Прохолодний. 478 00:21:50,150 --> 00:21:55,460 >> Отже, як ви, хлопці, начебто бачив з мигцем, 479 00:21:55,460 --> 00:21:58,450 ми збираємося псевдокод це. 480 00:21:58,450 --> 00:22:02,510 Так що, якщо ви, хлопці, в задній хочете утворюють групу, кожен в таблиці 481 00:22:02,510 --> 00:22:06,170 можуть утворювати мало партнера, я збираюся щоб дати вам, хлопці, як три хвилини 482 00:22:06,170 --> 00:22:08,190 просто говорити через логіка, англійською мовою, 483 00:22:08,190 --> 00:22:14,161 про те, як ми могли б реалізувати псевдокод написати вибору роду. 484 00:22:14,161 --> 00:22:14,910 І є цукерки. 485 00:22:14,910 --> 00:22:16,118 Будь ласка, приходьте і отримаєте цукерку. 486 00:22:16,118 --> 00:22:19,520 Якщо ви знаходитесь в спині і ви хочете цукерки, я можу кинути цукерки на вас. 487 00:22:19,520 --> 00:22:22,850 Насправді, зробити you-- прохолодно. 488 00:22:22,850 --> 00:22:23,552 Ой, вибачте. 489 00:22:23,552 --> 00:22:26,751 490 00:22:26,751 --> 00:22:27,250 ДОБРЕ. 491 00:22:27,250 --> 00:25:23,880 492 00:25:23,880 --> 00:25:27,140 >> Так що, якщо ми хотіли б, а клас, записи псевдокод 493 00:25:27,140 --> 00:25:30,466 про те, як можна було б підійти ця проблема, просто не соромтеся. 494 00:25:30,466 --> 00:25:32,340 Я просто ходити, а в порядку, запитаєте групи 495 00:25:32,340 --> 00:25:35,065 на наступному рядку що ми повинні робити. 496 00:25:35,065 --> 00:25:37,840 Так що, якщо ви, хлопці, хочете, щоб почати вимкнений, то, що перше, що 497 00:25:37,840 --> 00:25:40,600 робити, коли ви намагаєтеся здійснити спосіб вирішити цю програму 498 00:25:40,600 --> 00:25:43,480 вибірково відсортувати список? 499 00:25:43,480 --> 00:25:46,349 Давайте припустимо, що ми тільки що є масив, добре? 500 00:25:46,349 --> 00:25:49,088 >> АУДИТОРІЯ: Ви хочете, щоб створити деякі роду [нерозбірливо], що ви 501 00:25:49,088 --> 00:25:50,420 проходить через весь масиві. 502 00:25:50,420 --> 00:25:51,128 >> ANDI Пен: Право. 503 00:25:51,128 --> 00:25:54,100 Таким чином, ви будете хотіти, щоб ітерації через кожен простору, правильно? 504 00:25:54,100 --> 00:26:05,490 Настільки велика. 505 00:26:05,490 --> 00:26:08,600 Якщо ви, хлопці, хочете, щоб дати мені Наступний line-- да, в спину. 506 00:26:08,600 --> 00:26:11,414 507 00:26:11,414 --> 00:26:13,290 >> АУДИТОРІЯ: Перевірте їх все для найменших. 508 00:26:13,290 --> 00:26:14,248 >> ANDI Пен: Там ми йдемо. 509 00:26:14,248 --> 00:26:17,438 Тому ми хочемо, щоб пройти і перевірити бачити, що мінімальне значення, вірно? 510 00:26:17,438 --> 00:26:22,110 511 00:26:22,110 --> 00:26:24,840 Я збираюся скорочувати, що "хв." 512 00:26:24,840 --> 00:26:27,658 Що ви, хлопці, хочете робити після Ви знайшли мінімальне значення? 513 00:26:27,658 --> 00:26:28,533 >> АУДИТОРІЯ: [нерозбірливо] 514 00:26:28,533 --> 00:26:29,942 515 00:26:29,942 --> 00:26:33,150 ANDI Пен: Так що ви збираєтеся хочуть переключити його з першого цьому масиві, 516 00:26:33,150 --> 00:26:33,650 вірно? 517 00:26:33,650 --> 00:26:45,120 518 00:26:45,120 --> 00:26:46,850 Це початок, я збираюся сказати. 519 00:26:46,850 --> 00:26:47,220 Добре. 520 00:26:47,220 --> 00:26:50,386 Так що тепер ви помінялися перший Один з них, що ви хочете зробити після цього? 521 00:26:50,386 --> 00:26:54,840 Так що тепер ми знаємо, що це одне тут повинні бути найменше значення, чи не так? 522 00:26:54,840 --> 00:26:58,310 Тоді у вас є додатковий відпочинок масиву, що це несортоване. 523 00:26:58,310 --> 00:27:01,569 Так що ви хочете зробити тут, якщо ви хлопці, хочете, щоб дати мені наступний рядок? 524 00:27:01,569 --> 00:27:04,610 АУДИТОРІЯ: Отже ви хочете перебрати через решту масиву. 525 00:27:04,610 --> 00:27:05,276 ANDI Пен: Так. 526 00:27:05,276 --> 00:27:09,857 І так, що ж переборі вид має на увазі ми, напевно, потрібно? 527 00:27:09,857 --> 00:27:10,440 Який тип of-- 528 00:27:10,440 --> 00:27:12,057 >> АУДИТОРІЯ: О, додаткова змінна? 529 00:27:12,057 --> 00:27:13,890 ANDI Пен: Можливо другий цикл, чи не так? 530 00:27:13,890 --> 00:27:28,914 Таким чином, ми, ймовірно, захочуть для перебору through-- здорово. 531 00:27:28,914 --> 00:27:31,830 І тоді ви будете йти назад і ймовірно, перевірити мінімум раз 532 00:27:31,830 --> 00:27:32,100 вірно? 533 00:27:32,100 --> 00:27:34,975 І ви збираєтеся повторювати це, тому що петлі тільки збирається 534 00:27:34,975 --> 00:27:36,010 тримати працює, вірно? 535 00:27:36,010 --> 00:27:39,190 >> Отже, як ви, хлопці, можете бачити, ми просто загальний псевдокод 536 00:27:39,190 --> 00:27:41,480 про те, як ми хочемо, щоб ця програма дивитися. 537 00:27:41,480 --> 00:27:46,646 Це ітерація тут, те, що ми як правило, потрібно написати в коді 538 00:27:46,646 --> 00:27:49,270 якщо ми хочемо, щоб ітерації через Масив, який тип структури? 539 00:27:49,270 --> 00:27:51,030 Я думаю, Крістабел вже говорив це раніше. 540 00:27:51,030 --> 00:27:51,500 >> Зали: для петлі. 541 00:27:51,500 --> 00:27:52,160 >> ANDI Пен: для циклу? 542 00:27:52,160 --> 00:27:52,770 Точно. 543 00:27:52,770 --> 00:27:56,060 Так це, напевно, буде цикл. 544 00:27:56,060 --> 00:27:59,240 Що таке перевірка тут збирається означає? 545 00:27:59,240 --> 00:28:02,536 Як правило, якщо ви хочете, щоб перевірити якщо щось щось else-- 546 00:28:02,536 --> 00:28:03,270 >> АУДИТОРІЯ: Якщо. 547 00:28:03,270 --> 00:28:06,790 >> ANDI PENG: якщо, вірно? 548 00:28:06,790 --> 00:28:10,790 А потім своп тут, ми будемо перейти пізніше, бо Давида 549 00:28:10,790 --> 00:28:12,770 пройшов через це в лекції, а також. 550 00:28:12,770 --> 00:28:14,580 А потім другий ітерації implies-- 551 00:28:14,580 --> 00:28:15,120 >> АУДИТОРІЯ: Ще цикл. 552 00:28:15,120 --> 00:28:16,745 >> ANDI Пен: --another цикл, точно. 553 00:28:16,745 --> 00:28:19,870 554 00:28:19,870 --> 00:28:22,000 Так що, якщо ми шукаємо на це правильно, ми 555 00:28:22,000 --> 00:28:24,680 можна побачити, що ми, ймовірно, знадобиться вкладений цикл 556 00:28:24,680 --> 00:28:28,330 з умовним заявою до там а потім фактичне шматок коду, який це 557 00:28:28,330 --> 00:28:31,360 збирається поміняти значення. 558 00:28:31,360 --> 00:28:35,980 Так що я просто взагалі написано псевдокод код тут. 559 00:28:35,980 --> 00:28:38,910 І тоді ми насправді відбувається фізично, як клас, 560 00:28:38,910 --> 00:28:40,700 спробувати здійснити це сьогодні. 561 00:28:40,700 --> 00:28:42,486 Давайте повернемося в цей IDE. 562 00:28:42,486 --> 00:28:49,243 563 00:28:49,243 --> 00:28:50,230 >> Ой-ой. 564 00:28:50,230 --> 00:28:51,754 Чому це не-- там. 565 00:28:51,754 --> 00:28:52,253 ДОБРЕ. 566 00:28:52,253 --> 00:28:55,834 567 00:28:55,834 --> 00:28:57,500 Вибачте, дозвольте мені спробувати збільшити трохи більше. 568 00:28:57,500 --> 00:28:59,310 Там ми йдемо. 569 00:28:59,310 --> 00:29:05,060 Все, що я роблю тут, я створив Програма називається "вибір / sort.c." 570 00:29:05,060 --> 00:29:10,860 Я створив масив з дев'яти Значення, 4, 8, 2, 1, 6, 9, 7, 5, 3. 571 00:29:10,860 --> 00:29:14,370 В даний час, як ви можете Розумієте, вони не впорядковані. 572 00:29:14,370 --> 00:29:17,880 н буде число, говорить вам суму значень 573 00:29:17,880 --> 00:29:18,920 у вас є у вашому масиві. 574 00:29:18,920 --> 00:29:20,670 У цьому випадку, у нас є дев'ять значень. 575 00:29:20,670 --> 00:29:23,760 І я тільки що отримав цикл тут що виводить несортоване масив. 576 00:29:23,760 --> 00:29:28,370 >> І врешті-решт, я також отримав для цикл, який друкує його знову. 577 00:29:28,370 --> 00:29:32,070 Так, теоретично, якщо ця програма працює правильно, зрештою, 578 00:29:32,070 --> 00:29:35,670 Ви повинні побачити друкований цикл в якому 1, 2, 3, 4, 5, 6, 7, 8, 579 00:29:35,670 --> 00:29:39,310 9 все правильно в порядку. 580 00:29:39,310 --> 00:29:43,410 >> Таким чином, ми отримали наш псевдокод тут. 581 00:29:43,410 --> 00:29:46,090 Хто-небудь хоче, метою яких я просто піду просити volunteers-- 582 00:29:46,090 --> 00:29:49,540 скажіть мені точно, що якщо ввести ми хочемо, щоб, по-перше, просто ітерації 583 00:29:49,540 --> 00:29:52,840 по початок цього масиву? 584 00:29:52,840 --> 00:29:55,204 Що рядок коду я ймовірно, тут потрібно? 585 00:29:55,204 --> 00:29:56,990 >> АУДИТОРІЯ: [нерозбірливо] 586 00:29:56,990 --> 00:29:59,010 >> ANDI Пен: Так, відчуваю, безкоштовно, метою яких вибачте, вам 587 00:29:59,010 --> 00:30:02,318 не повинні стояти up-- почуття вільно підняти свій голос небагато. 588 00:30:02,318 --> 00:30:08,190 >> АУДИТОРІЯ: Для INT я дорівнює 0-- 589 00:30:08,190 --> 00:30:10,690 >> ANDI Пен: Так, добре. 590 00:30:10,690 --> 00:30:15,220 >> АУДИТОРІЯ: я менше довжини масиву. 591 00:30:15,220 --> 00:30:19,630 >> ANDI Пен: Так що майте на проти тут, тому що ми 592 00:30:19,630 --> 00:30:23,060 не їсти функція, яка говорить нам довжина масиву, 593 00:30:23,060 --> 00:30:25,790 у нас вже є Значення, яке зберігає, що. 594 00:30:25,790 --> 00:30:27,920 Вірно? 595 00:30:27,920 --> 00:30:31,010 Ще одна річ, щоб тримати в mind-- в масиві 596 00:30:31,010 --> 00:30:33,940 з дев'яти значень, які індекси? 597 00:30:33,940 --> 00:30:38,720 Давайте просто скажемо, цей масив 0 до 3. 598 00:30:38,720 --> 00:30:41,500 Ви бачите, що останній Індекс насправді 3. 599 00:30:41,500 --> 00:30:45,530 Це не 4, хоча є чотири значення в масиві. 600 00:30:45,530 --> 00:30:49,866 >> Так тут, ми повинні бути дуже обережні, того, що наша умова для довжини 601 00:30:49,866 --> 00:30:50,490 буде. 602 00:30:50,490 --> 00:30:51,948 >> АУДИТОРІЯ: не було б н мінус 1? 603 00:30:51,948 --> 00:30:54,440 ANDI Пен: Це відбувається п мінус 1, точно. 604 00:30:54,440 --> 00:30:57,379 Чи має це сенс, чому це п мінус 1, все? 605 00:30:57,379 --> 00:30:58,920 Це тому, що масиви дорівнюють нулю, індексовані. 606 00:30:58,920 --> 00:31:02,010 Вони починаються з 0 і запустити до н мінус 1. 607 00:31:02,010 --> 00:31:03,210 Так, це трохи складніше. 608 00:31:03,210 --> 00:31:03,730 ДОБРЕ. 609 00:31:03,730 --> 00:31:05,929 І потім-- 610 00:31:05,929 --> 00:31:08,054 АУДИТОРІЯ: Isnt'1, що вже подбали, хоча, 611 00:31:08,054 --> 00:31:11,400 , Просто не говорю "менше або дорівнює "і просто говорю" менш "? 612 00:31:11,400 --> 00:31:13,108 >> ANDI Пен: Це дуже гарне питання. 613 00:31:13,108 --> 00:31:13,630 Так що, так. 614 00:31:13,630 --> 00:31:17,410 Але також, таким чином, що ми реалізації перевірки право, 615 00:31:17,410 --> 00:31:19,120 вам потрібно порівняти два значення. 616 00:31:19,120 --> 00:31:21,009 Таким чином, ви насправді хочете, щоб залишити "на" порожній. 617 00:31:21,009 --> 00:31:23,050 Тому що, якщо ви порівняєте це одне, ви не збираєтеся 618 00:31:23,050 --> 00:31:25,530 є що-небудь після нього порівняти, правда? 619 00:31:25,530 --> 00:31:27,460 Так. 620 00:31:27,460 --> 00:31:29,297 Так я ++. 621 00:31:29,297 --> 00:31:30,380 Давайте додамо наші дужки в. 622 00:31:30,380 --> 00:31:30,880 Упс. 623 00:31:30,880 --> 00:31:33,950 624 00:31:33,950 --> 00:31:34,710 Відмінно. 625 00:31:34,710 --> 00:31:39,117 Таким чином, ми маємо початок нашої зовнішньої петлі. 626 00:31:39,117 --> 00:31:41,450 Так що тепер ми, ймовірно, хочете, щоб створити змінну для зберігання 627 00:31:41,450 --> 00:31:43,085 трек найменшим значенням, вірно? 628 00:31:43,085 --> 00:31:45,751 Хто-небудь хоче, щоб дати мені рядок коду, яка буде це робити? 629 00:31:45,751 --> 00:31:48,700 630 00:31:48,700 --> 00:31:53,570 Що нам потрібно, якщо ми збираємося хочуть, щоб зберегти що-небудь? 631 00:31:53,570 --> 00:31:55,047 >> Право. 632 00:31:55,047 --> 00:31:57,630 Може бути, краще, що назва буде be-- "Темп" повністю works-- 633 00:31:57,630 --> 00:32:00,655 може бути, більш влучно назвав би, якщо ми хочемо, щоб маленький value-- 634 00:32:00,655 --> 00:32:01,624 >> АУДИТОРІЯ: Мін. 635 00:32:01,624 --> 00:32:02,790 ANDI Пен: хв, там ми йдемо. 636 00:32:02,790 --> 00:32:05,230 хв буде добре. 637 00:32:05,230 --> 00:32:08,340 І ось що нам робити хочу, щоб ініціалізувати його? 638 00:32:08,340 --> 00:32:09,620 Це трохи складніше. 639 00:32:09,620 --> 00:32:13,580 Тому що зараз на початок цього масиву, 640 00:32:13,580 --> 00:32:15,730 Ви ще не дивилися ні на що, чи не так? 641 00:32:15,730 --> 00:32:19,200 Так що, автоматично, якщо ми тільки на я дорівнює 0, 642 00:32:19,200 --> 00:32:22,302 те, що ми хочемо, щоб ініціалізувати наш перший мінімальне значення для? 643 00:32:22,302 --> 00:32:22,802 АУДИТОРІЯ: я. 644 00:32:22,802 --> 00:32:24,790 ANDI Пен: я, точно. 645 00:32:24,790 --> 00:32:27,040 Christabel, чому ми хочемо ініціалізувати його я? 646 00:32:27,040 --> 00:32:28,510 >> АУДИТОРІЯ: Тому що, ну, ми, починаючи з 0. 647 00:32:28,510 --> 00:32:31,660 Так, тому що ми не маємо нічого, щоб порівняти це, мінімум буде в кінцевому підсумку 0. 648 00:32:31,660 --> 00:32:32,451 >> ANDI Пен: Точно. 649 00:32:32,451 --> 00:32:34,400 Таким чином, вона абсолютно точно. 650 00:32:34,400 --> 00:32:36,780 Тому що у нас насправді не подивився на що-небудь ще, 651 00:32:36,780 --> 00:32:38,680 ми не знаємо, що наша мінімальне значення. 652 00:32:38,680 --> 00:32:41,960 Ми хочемо, щоб просто ініціалізувати його я, що, в даний час, прямо тут. 653 00:32:41,960 --> 00:32:44,750 І, як ми як і раніше рухатися вниз цей масив, 654 00:32:44,750 --> 00:32:48,122 ми побачимо, що, один з Додатковий прохід, я збільшує. 655 00:32:48,122 --> 00:32:49,830 І так в цій точці, я, ймовірно, буде 656 00:32:49,830 --> 00:32:52,329 хочуть бути мінімальним, тому що це буде що завгодно 657 00:32:52,329 --> 00:32:54,520 початок невідсортоване масиву. 658 00:32:54,520 --> 00:32:55,270 Прохолодний. 659 00:32:55,270 --> 00:32:58,720 >> Так що тепер ми хочемо, щоб додати для циклу тут це 660 00:32:58,720 --> 00:33:03,225 збирається повторювати через несортоване або інша частина цього масиву. 661 00:33:03,225 --> 00:33:05,808 Хто-небудь хоче, щоб дати мені рядок коду, яка буде це робити? 662 00:33:05,808 --> 00:33:08,870 663 00:33:08,870 --> 00:33:11,330 Hint-- що нам потрібно тут? 664 00:33:11,330 --> 00:33:17,320 665 00:33:17,320 --> 00:33:18,820 Що збирається йти в цьому для циклу? 666 00:33:18,820 --> 00:33:19,465 Так. 667 00:33:19,465 --> 00:33:21,590 АУДИТОРІЯ: Таким чином, ми хотіли б мати різний число, 668 00:33:21,590 --> 00:33:25,080 бо ми біжимо до кінця масиву замість I, так що, можливо 669 00:33:25,080 --> 00:33:25,760 J. 670 00:33:25,760 --> 00:33:27,301 >> ANDI Пен: Так, J звучить добре для мене. 671 00:33:27,301 --> 00:33:27,850 Одно? 672 00:33:27,850 --> 00:33:33,930 >> АУДИТОРІЯ: Так би я плюс 1, бо Ви починаєте на наступній значення. 673 00:33:33,930 --> 00:33:40,395 А потім до end-- так знову, J є менше, ніж п мінус 1, а потім J ++. 674 00:33:40,395 --> 00:33:41,103 ANDI Пен: Відмінно. 675 00:33:41,103 --> 00:33:48,510 676 00:33:48,510 --> 00:33:52,750 >> А потім тут, ми збираємося хочете щоб перевірити, якщо наша умова виконується, 677 00:33:52,750 --> 00:33:53,250 вірно? 678 00:33:53,250 --> 00:33:55,740 Тому що ви хочете, щоб змінити мінімальне значення 679 00:33:55,740 --> 00:33:58,700 якщо це насправді менше, ніж ви порівнюєте його, вірно? 680 00:33:58,700 --> 00:34:01,146 Так що ми збираємося хочете тут? 681 00:34:01,146 --> 00:34:04,160 682 00:34:04,160 --> 00:34:04,897 Перевірте, щоб бачити. 683 00:34:04,897 --> 00:34:06,730 Який вид заяви ми, ймовірно, буде 684 00:34:06,730 --> 00:34:08,389 ти хочете використовувати, якщо ми хочу дещо перевірити? 685 00:34:08,389 --> 00:34:09,360 >> АУДИТОРІЯ: якщо заяву. 686 00:34:09,360 --> 00:34:10,485 >> ANDI PENG: якщо заяву. 687 00:34:10,485 --> 00:34:13,155 Так if-- і те, що буде умова, що ми хочемо в 688 00:34:13,155 --> 00:34:13,988 нашої, якщо заяву? 689 00:34:13,988 --> 00:34:18,255 690 00:34:18,255 --> 00:34:22,960 >> АУДИТОРІЯ: Якщо значення J менше, ніж значення i-- 691 00:34:22,960 --> 00:34:24,600 >> ANDI Пен: Точно. 692 00:34:24,600 --> 00:34:27,480 Так if-- так що це масив називається "масив". 693 00:34:27,480 --> 00:34:27,980 Відмінно. 694 00:34:27,980 --> 00:34:30,465 Так що, якщо array-- що це було? 695 00:34:30,465 --> 00:34:31,090 Скажіть, що ще раз. 696 00:34:31,090 --> 00:34:39,590 >> АУДИТОРІЯ: Якщо масив-J менше Масив-я, то ми б змінити хв. 697 00:34:39,590 --> 00:34:41,590 Таким чином, хв буде к. 698 00:34:41,590 --> 00:34:44,590 699 00:34:44,590 --> 00:34:47,249 >> ANDI Пен: Чи має це сенс? 700 00:34:47,249 --> 00:34:48,670 ДОБРЕ. 701 00:34:48,670 --> 00:34:52,929 А тепер сюди, ми насправді хочемо реалізувати обмін, вірно? 702 00:34:52,929 --> 00:34:58,285 Так Нагадаємо, що в лекції, що Давид, коли він намагався обміняти the--, що було 703 00:34:58,285 --> 00:34:59,996 it-- апельсиновий сік і milk-- 704 00:34:59,996 --> 00:35:01,150 >> АУДИТОРІЯ: Це було огидно. 705 00:35:01,150 --> 00:35:02,816 >> ANDI Пен: Так, це було свого роду брутто. 706 00:35:02,816 --> 00:35:05,310 Але це було досить добре Концепція демонстрації час. 707 00:35:05,310 --> 00:35:08,430 Так що думайте про ваших цінностей тут. 708 00:35:08,430 --> 00:35:10,794 Ви отримали масив з мін, масив I, 709 00:35:10,794 --> 00:35:12,460 або те, що ми намагалися поміняти тут. 710 00:35:12,460 --> 00:35:15,310 І ви, мабуть, не може залити їх в один з одним, в той же час, так? 711 00:35:15,310 --> 00:35:17,180 Так що ми збираємося щоб потрібно створити тут 712 00:35:17,180 --> 00:35:19,126 для того, щоб правильно поміняти значення? 713 00:35:19,126 --> 00:35:19,820 >> АУДИТОРІЯ: тимчасова змінна. 714 00:35:19,820 --> 00:35:21,370 >> ANDI Пен: тимчасова змінна. 715 00:35:21,370 --> 00:35:22,570 Так давайте зробимо Int темп. 716 00:35:22,570 --> 00:35:25,681 Дивись, це було б краще Час, метою яких агов, що це було? 717 00:35:25,681 --> 00:35:26,180 ДОБРЕ. 718 00:35:26,180 --> 00:35:29,800 Так що це було б краще час назвати змінну "Темп". 719 00:35:29,800 --> 00:35:30,730 Так давайте зробимо Int темп. 720 00:35:30,730 --> 00:35:32,563 Що ми збираємося SET TEMP рівну тут? 721 00:35:32,563 --> 00:35:34,752 722 00:35:34,752 --> 00:35:35,335 АУДИТОРІЯ: Мін? 723 00:35:35,335 --> 00:35:38,508 724 00:35:38,508 --> 00:35:39,716 ANDI Пен: Це трохи складніше. 725 00:35:39,716 --> 00:35:43,110 726 00:35:43,110 --> 00:35:44,880 Це насправді не має значення, в кінці кінців. 727 00:35:44,880 --> 00:35:47,690 Це не має значення, що замовлення ви вирішите поміняти в 728 00:35:47,690 --> 00:35:50,862 так довго, як ви робите, що ви відстежувати те, що ви підкачки. 729 00:35:50,862 --> 00:35:52,250 >> АУДИТОРІЯ: Це може бути масив я. 730 00:35:52,250 --> 00:35:53,666 >> ANDI Пен: Так, давайте зробимо масив-I. 731 00:35:53,666 --> 00:35:55,950 732 00:35:55,950 --> 00:35:59,305 І тоді те, що наступна рядок коду ми хочемо мати тут? 733 00:35:59,305 --> 00:36:00,680 АУДИТОРІЯ: масив я дорівнює масиву-J. 734 00:36:00,680 --> 00:36:07,154 735 00:36:07,154 --> 00:36:08,070 ANDI Пен: І, нарешті? 736 00:36:08,070 --> 00:36:12,070 АУДИТОРІЯ: масив J дорівнює масиву я. 737 00:36:12,070 --> 00:36:14,525 АУДИТОРІЯ: Або масиву J одно Масив-temp-- або температури. 738 00:36:14,525 --> 00:36:17,135 739 00:36:17,135 --> 00:36:19,430 >> ANDI Пен: ОК. 740 00:36:19,430 --> 00:36:21,510 Так що давайте працювати і подивимося, якщо він буде працювати. 741 00:36:21,510 --> 00:36:37,520 742 00:36:37,520 --> 00:36:39,335 Де, що відбувається? 743 00:36:39,335 --> 00:36:40,210 О, що це проблема. 744 00:36:40,210 --> 00:36:44,320 Дивись, на лінії 40, ми намагається використовувати масив-J? 745 00:36:44,320 --> 00:36:47,022 Але де J існує тільки в? 746 00:36:47,022 --> 00:36:48,402 >> АУДИТОРІЯ: Протягом циклу. 747 00:36:48,402 --> 00:36:49,110 ANDI Пен: Право. 748 00:36:49,110 --> 00:36:51,730 Так що ми збираємося потрібно зробити? 749 00:36:51,730 --> 00:36:53,170 >> АУДИТОРІЯ: Визначити його межами the-- 750 00:36:53,170 --> 00:36:57,777 751 00:36:57,777 --> 00:37:00,610 АУДИТОРІЯ: Так, я думаю, ви повинні використовувати інший, якщо заяву, чи не так? 752 00:37:00,610 --> 00:37:05,230 Так як, якщо minimum-- Все в порядку, дайте мені подумати. 753 00:37:05,230 --> 00:37:08,170 754 00:37:08,170 --> 00:37:09,990 >> ANDI Пен: Хлопці, спробуйте поглянути Давайте 755 00:37:09,990 --> 00:37:11,270 см, що це те, що ми можемо зробити тут? 756 00:37:11,270 --> 00:37:11,811 >> АУДИТОРІЯ: ОК. 757 00:37:11,811 --> 00:37:15,900 Таким чином, якщо мінімальна не дорівнює j-- так що якщо мінімальна ще i-- 758 00:37:15,900 --> 00:37:17,570 то ми б не поміняти. 759 00:37:17,570 --> 00:37:22,450 760 00:37:22,450 --> 00:37:24,712 >> ANDI Пен: Чи означає це, одно я? 761 00:37:24,712 --> 00:37:25,920 Що ви хочете сказати тут? 762 00:37:25,920 --> 00:37:30,494 >> АУДИТОРІЯ: Або так, якщо мінімум не рівне I, так. 763 00:37:30,494 --> 00:37:39,627 764 00:37:39,627 --> 00:37:40,210 ANDI Пен: ОК. 765 00:37:40,210 --> 00:37:42,040 Ну, що вирішує, начебто, наші проблеми. 766 00:37:42,040 --> 00:37:47,265 Але це ще не вирішити Проблема що станеться, якщо j-- так J 767 00:37:47,265 --> 00:37:49,890 не існує поза ним, те, що Ви хочете, щоб ми з ним робити? 768 00:37:49,890 --> 00:37:50,698 Оголосити його межами? 769 00:37:50,698 --> 00:37:59,410 770 00:37:59,410 --> 00:38:02,730 Давайте спробуємо це працює. 771 00:38:02,730 --> 00:38:04,435 Ой-ой. 772 00:38:04,435 --> 00:38:06,200 Наша роду не працює. 773 00:38:06,200 --> 00:38:10,060 >> Як ви можете бачити, нашу початкову Масив були ті значення. 774 00:38:10,060 --> 00:38:14,800 І після цього він повинен мати був у 1, 2, 3, 4, 5, 6, 7, 8, 9. 775 00:38:14,800 --> 00:38:15,530 Не працює. 776 00:38:15,530 --> 00:38:16,030 Ах. 777 00:38:16,030 --> 00:38:17,184 Що ми робимо? 778 00:38:17,184 --> 00:38:17,850 АУДИТОРІЯ: Налагодження. 779 00:38:17,850 --> 00:38:21,787 780 00:38:21,787 --> 00:38:23,370 ANDI Пен: Гаразд, ми можемо спробувати. 781 00:38:23,370 --> 00:38:25,030 Ми можемо налагодити. 782 00:38:25,030 --> 00:38:26,042 Огляньте небагато. 783 00:38:26,042 --> 00:38:31,177 784 00:38:31,177 --> 00:38:33,656 Давайте встановимо нашу точку зупину. 785 00:38:33,656 --> 00:38:37,280 Давайте like-- OK. 786 00:38:37,280 --> 00:38:40,444 >> Так, тому що ми вже знаємо, що ці лінії, 15 через 22, 787 00:38:40,444 --> 00:38:43,610 які working--, тому що все, що я роблю просто перебираючи і printing-- 788 00:38:43,610 --> 00:38:45,406 Я можу йти вперед і пропустити це. 789 00:38:45,406 --> 00:38:47,280 Давайте почнемо з лінії 25. 790 00:38:47,280 --> 00:38:48,712 ООП дозвольте мені позбутися цього. 791 00:38:48,712 --> 00:38:51,598 792 00:38:51,598 --> 00:38:54,057 >> АУДИТОРІЯ: Так точки зупину де починається налагодження? 793 00:38:54,057 --> 00:38:54,890 ANDI Пен: Або зупинок. 794 00:38:54,890 --> 00:38:55,670 АУДИТОРІЯ: Або зупинок. 795 00:38:55,670 --> 00:38:55,930 ANDI Пен: Так. 796 00:38:55,930 --> 00:38:58,640 Ви можете встановити точки зупину і кілька він може просто стрибати від одного до іншого. 797 00:38:58,640 --> 00:39:01,590 Але в цьому випадку ми не знаємо, де помилка відбувається. 798 00:39:01,590 --> 00:39:03,780 Таким чином, ми просто хочемо почати зверху вниз. 799 00:39:03,780 --> 00:39:05,020 Так. 800 00:39:05,020 --> 00:39:05,550 ДОБРЕ. 801 00:39:05,550 --> 00:39:08,460 >> Так ця лінія тут, ми можемо втрутитися. 802 00:39:08,460 --> 00:39:11,499 Ви можете побачити тут, ми отримали масив. 803 00:39:11,499 --> 00:39:13,290 Ті значення що в масиві. 804 00:39:13,290 --> 00:39:16,360 Ви бачите, що, як індекс 0, відповідає value-- о, 805 00:39:16,360 --> 00:39:17,526 Я збираюся спробувати, щоб збільшити. 806 00:39:17,526 --> 00:39:20,650 На жаль, це дійсно важко щоб see-- за індексом масиву 0, 807 00:39:20,650 --> 00:39:24,090 ми маємо значення 4 і Потім так далі, і так далі. 808 00:39:24,090 --> 00:39:25,670 У нас є локальні змінні. 809 00:39:25,670 --> 00:39:28,570 Зараз я дорівнює 0, що ми хочемо, щоб це було. 810 00:39:28,570 --> 00:39:31,540 811 00:39:31,540 --> 00:39:33,690 >> І так давайте тримати покрокове. 812 00:39:33,690 --> 00:39:36,850 Наш мінімальний дорівнює 0, які ми також хочемо, щоб це було. 813 00:39:36,850 --> 00:39:39,470 814 00:39:39,470 --> 00:39:45,560 І тоді ми входимо наш другий для цикл, якщо масив J менше, ніж масив-I, 815 00:39:45,560 --> 00:39:46,380 який його не було. 816 00:39:46,380 --> 00:39:48,130 Так само ви бачите, як що пропустив що? 817 00:39:48,130 --> 00:39:52,430 >> АУДИТОРІЯ: так повинно, якщо Мінімальний все that-- не випливає, що 818 00:39:52,430 --> 00:39:55,424 бути всередині першого цикл? 819 00:39:55,424 --> 00:39:57,340 ANDI Пен: Ні, тому що Ви все ще хочете, щоб перевірити. 820 00:39:57,340 --> 00:40:00,329 Ви хочете, щоб зробити порівняння кожен Час, навіть після запуску через нього. 821 00:40:00,329 --> 00:40:02,620 Ви не просто хочете, щоб зробити це на першому прохід. 822 00:40:02,620 --> 00:40:05,240 Ви хочете, щоб зробити це з кожен прохід знову. 823 00:40:05,240 --> 00:40:07,198 Отже, ви хочете, щоб перевірити Ваш стан всередині. 824 00:40:07,198 --> 00:40:11,610 825 00:40:11,610 --> 00:40:13,746 Таким чином, ми тільки збираємося тримати працює через тут. 826 00:40:13,746 --> 00:40:17,337 827 00:40:17,337 --> 00:40:18,420 Я дам вам підказку хлопцям. 828 00:40:18,420 --> 00:40:23,910 Це пов'язано з тим, що при Ви перевіряєте ваш умовний, 829 00:40:23,910 --> 00:40:26,600 Ви не перевіряючи для правильного індексу. 830 00:40:26,600 --> 00:40:32,510 Так що зараз ви перевірка Індекс масиву J менше, ніж масив 831 00:40:32,510 --> 00:40:33,970 Індекс I. 832 00:40:33,970 --> 00:40:36,580 Але те, що ти робиш на початок для циклу? 833 00:40:36,580 --> 00:40:38,260 Ви не встановивши J, рівний I? 834 00:40:38,260 --> 00:40:41,260 835 00:40:41,260 --> 00:40:45,415 >> Так, так що ми насправді можемо вийти з відладчика тут. 836 00:40:45,415 --> 00:40:47,040 Отже, давайте поглянемо на нашому псевдокоді. 837 00:40:47,040 --> 00:40:50,070 838 00:40:50,070 --> 00:40:52,580 For-- ми збираємося почати в я дорівнює 0. 839 00:40:52,580 --> 00:40:54,760 Ми збираємося йти до н мінус 1. 840 00:40:54,760 --> 00:40:58,040 Давайте перевіримо, ми мали це право? 841 00:40:58,040 --> 00:40:59,580 Так, це було в порядку. 842 00:40:59,580 --> 00:41:02,080 >> Отже всередині тут, ми створимо мінімальне значення 843 00:41:02,080 --> 00:41:03,630 і встановити, що в I рівні. 844 00:41:03,630 --> 00:41:04,950 Хіба ми це робимо? 845 00:41:04,950 --> 00:41:06,270 Так, це зробив. 846 00:41:06,270 --> 00:41:10,430 В даний час в нашій внутрішній петлі для, ми збирається робити J дорівнює я в п мінус 1. 847 00:41:10,430 --> 00:41:11,950 Хіба ми це робимо? 848 00:41:11,950 --> 00:41:15,540 Справді, ми зробили це. 849 00:41:15,540 --> 00:41:19,922 >> Так, однак, що ми тут порівняння? 850 00:41:19,922 --> 00:41:20,925 >> АУДИТОРІЯ: J + 1. 851 00:41:20,925 --> 00:41:21,716 ANDI Пен: Точно. 852 00:41:21,716 --> 00:41:24,184 853 00:41:24,184 --> 00:41:27,350 І тоді ви будете хотіти, щоб встановити мінімальна дорівнює J плюс 1, а. 854 00:41:27,350 --> 00:41:31,057 855 00:41:31,057 --> 00:41:32,640 Так що я пройшов через це дуже швидко. 856 00:41:32,640 --> 00:41:36,190 Як ви, хлопці розуміють чому це J + 1? 857 00:41:36,190 --> 00:41:36,890 ДОБРЕ. 858 00:41:36,890 --> 00:41:40,700 >> Таким чином, у вашому масиві, в Ваш перший прохід через, 859 00:41:40,700 --> 00:41:44,850 Ваш цикл, для Int я дорівнює 0, давайте просто 860 00:41:44,850 --> 00:41:46,740 припустити, що це не була змінена ще. 861 00:41:46,740 --> 00:41:53,180 862 00:41:53,180 --> 00:41:56,760 У нас є масив, повністю, всього чотири несортовані елементи, вірно? 863 00:41:56,760 --> 00:42:00,760 Тому ми хочемо, щоб ініціалізувати я дорівнювати 0. 864 00:42:00,760 --> 00:42:03,650 І я маю намір просто проходять через цю петлю. 865 00:42:03,650 --> 00:42:08,560 І тому в першому проході, ми збираємося ініціалізувати змінну "хв" 866 00:42:08,560 --> 00:42:11,245 що також дорівнює I, тому що ми не мати мінімальне значення. 867 00:42:11,245 --> 00:42:12,870 Так от в даний час дорівнює 0, а також. 868 00:42:12,870 --> 00:42:16,182 869 00:42:16,182 --> 00:42:17,640 І тоді ми будемо йти до кінця. 870 00:42:17,640 --> 00:42:19,270 І ми хочемо, щоб ітерації знову. 871 00:42:19,270 --> 00:42:22,900 Тепер, коли ми знайшли, що наш мінімальний Тобто, ми хочемо, щоб перебору 872 00:42:22,900 --> 00:42:25,190 знову, щоб побачити, якщо це порівняння, чи не так? 873 00:42:25,190 --> 00:42:40,440 Так J Ось приходить на рівне I, який є 0. 874 00:42:40,440 --> 00:42:46,320 І потім, якщо масив J плюс я, що це той, який далі знову, як менш 875 00:42:46,320 --> 00:42:49,270 ніж те, що ваш поточний мінімум значення, ви хочете поміняти місцями. 876 00:42:49,270 --> 00:42:56,850 >> Так що давайте просто сказати, що ми отримав, як, 2, 5, 1, 8. 877 00:42:56,850 --> 00:43:01,610 Прямо зараз, я дорівнює 0 і J дорівнює 0. 878 00:43:01,610 --> 00:43:05,210 І це наша мінімальне значення. 879 00:43:05,210 --> 00:43:09,950 Якщо масив-J плюс i-- так що якщо один це після того, що ми, дивлячись на 880 00:43:09,950 --> 00:43:13,450 більше, ніж один перед цим, це стане мінімум. 881 00:43:13,450 --> 00:43:18,120 >> Так от, ми бачимо, що 5 не менше, аніж. 882 00:43:18,120 --> 00:43:19,730 Так це буде, щоб не бути 5. 883 00:43:19,730 --> 00:43:23,580 Ми бачимо, що 1 менше, ніж 2, чи не так? 884 00:43:23,580 --> 00:43:32,970 Отже, тепер ми знаємо, що наша мінімум буде значення індексу на 0, 1, 2. 885 00:43:32,970 --> 00:43:34,030 Так? 886 00:43:34,030 --> 00:43:39,170 А потім, коли ви отримуєте тут, Ви можете поміняти правильні значення. 887 00:43:39,170 --> 00:43:42,610 >> Так що, коли ви, хлопці, просто маючи J раніше, ви не дивлячись на те 888 00:43:42,610 --> 00:43:43,260 після неї. 889 00:43:43,260 --> 00:43:44,520 Ви шукали на те ж саме значення, що 890 00:43:44,520 --> 00:43:46,290 Тому він просто нічого не робив. 891 00:43:46,290 --> 00:43:49,721 Чи має це сенс для всіх, Тому нам потрібно що плюс 1 там? 892 00:43:49,721 --> 00:43:50,220 ДОБРЕ. 893 00:43:50,220 --> 00:43:53,345 Тепер давайте просто запустити через нього, щоб зробити що інша частина коду є правильним. 894 00:43:53,345 --> 00:44:04,424 895 00:44:04,424 --> 00:44:05,340 Чому, що трапилося? 896 00:44:05,340 --> 00:44:14,780 897 00:44:14,780 --> 00:44:16,364 Ах, це хв прямо тут. 898 00:44:16,364 --> 00:44:17,780 Ми порівнювали невірне значення. 899 00:44:17,780 --> 00:44:24,944 900 00:44:24,944 --> 00:44:25,906 О ні. 901 00:44:25,906 --> 00:44:30,720 902 00:44:30,720 --> 00:44:33,482 >> Ах так, тут ми були обмін неправильні значення, а також. 903 00:44:33,482 --> 00:44:34,940 Тому що ми шукали в I і J. 904 00:44:34,940 --> 00:44:36,440 Ті, кого ми перевіряли. 905 00:44:36,440 --> 00:44:39,160 Ми насправді хочемо, щоб поміняти місцями Мінімальний струм мінімум, 906 00:44:39,160 --> 00:44:40,550 з тим, що один зовні. 907 00:44:40,550 --> 00:44:59,510 908 00:44:59,510 --> 00:45:05,402 І, як ви, хлопці, можете побачити вниз тут, у нас є відсортований масив. 909 00:45:05,402 --> 00:45:07,110 Це просто було зробити з той факт, що, коли 910 00:45:07,110 --> 00:45:09,350 ми перевіряли Значення, які ми порівнювали, 911 00:45:09,350 --> 00:45:11,226 ми не дивилися на правильні значення. 912 00:45:11,226 --> 00:45:13,850 Ми шукали в тому ж самому тут, насправді не його заміни. 913 00:45:13,850 --> 00:45:17,135 Ви повинні дивитися на один наступний до нього, а потім ви можете поміняти. 914 00:45:17,135 --> 00:45:19,260 Так ось те, що було свого роду прослуховування наш код, перш ніж. 915 00:45:19,260 --> 00:45:22,460 І те, що я зробив тут є все, відладчик міг би зробити для вас 916 00:45:22,460 --> 00:45:23,810 Я просто зробив це на дошка, тому що це легше 917 00:45:23,810 --> 00:45:26,320 щоб побачити, а не намагатися для збільшення масштабу відладчика. 918 00:45:26,320 --> 00:45:29,391 Чи має це сенс для всіх? 919 00:45:29,391 --> 00:45:29,890 Прохолодний. 920 00:45:29,890 --> 00:45:34,800 921 00:45:34,800 --> 00:45:35,410 >> Добре. 922 00:45:35,410 --> 00:45:41,070 Ми можемо рухатися далі до розмови про асимптотична позначення, які 923 00:45:41,070 --> 00:45:44,580 це просто фантазії спосіб сказати виконання всіх цих видів. 924 00:45:44,580 --> 00:45:47,650 Так що я знаю Девіда, в лекції, торкнувся автономної роботи. 925 00:45:47,650 --> 00:45:52,124 І він пішов через весь формулою про те, як розрахувати час автономної роботи. 926 00:45:52,124 --> 00:45:53,040 Не турбуйтеся про це. 927 00:45:53,040 --> 00:45:54,660 Якщо ви дійсно цікаво про те, як це працює, 928 00:45:54,660 --> 00:45:55,810 не соромтеся говорити зі мною після розділу. 929 00:45:55,810 --> 00:45:57,560 Ми можемо пройти через формули разом. 930 00:45:57,560 --> 00:46:00,689 Але всі ви, хлопці, повинні дійсно знаю, що п в квадраті більш 2 931 00:46:00,689 --> 00:46:01,980 це те ж саме, як н в квадраті. 932 00:46:01,980 --> 00:46:04,710 Тому що найбільший номер, показник зростає найбільше. 933 00:46:04,710 --> 00:46:06,590 І так для наших цілей, Всі ми піклуємося про 934 00:46:06,590 --> 00:46:09,470 є те, що гігантський номер, який зростає. 935 00:46:09,470 --> 00:46:13,340 >> Так що в кращому випадку виконання відбіркового роду? 936 00:46:13,340 --> 00:46:15,830 Якщо ви збираєтеся мати для перебору списку 937 00:46:15,830 --> 00:46:18,712 а потім перебору інші цього списку, 938 00:46:18,712 --> 00:46:20,420 скільки разів Ви збираєтеся ймовірно, 939 00:46:20,420 --> 00:46:24,612 в гіршому case-- в кращому випадку, sorry-- запустити через? 940 00:46:24,612 --> 00:46:27,070 Можливо, краще запитати щоб запитати, що це найгірший випадок 941 00:46:27,070 --> 00:46:28,153 виконання відбіркового роду. 942 00:46:28,153 --> 00:46:29,366 АУДИТОРІЯ: п в квадраті. 943 00:46:29,366 --> 00:46:30,740 ANDI Пен: Це н квадрат, правильно. 944 00:46:30,740 --> 00:46:36,986 Так простий спосіб думати про це, як, в будь-який час у вас є два вкладених циклів для, 945 00:46:36,986 --> 00:46:38,110 це буде н в квадраті. 946 00:46:38,110 --> 00:46:40,386 Тому що не тільки ти проходить через раз, 947 00:46:40,386 --> 00:46:42,260 у вас є, щоб повернутися і бігти через нього 948 00:46:42,260 --> 00:46:44,980 знову всередині для кожного значення. 949 00:46:44,980 --> 00:46:48,640 Таким чином, в цьому випадку, ви працюєте п раз н квадрат, який is-- вибачте, 950 00:46:48,640 --> 00:46:50,505 п раз п, дорівнює п в квадраті. 951 00:46:50,505 --> 00:46:53,230 952 00:46:53,230 --> 00:46:56,360 >> І начебто теж трохи унікальним в тому сенсі 953 00:46:56,360 --> 00:46:59,774 що це не має значення, якщо ці Значення вже в порядку. 954 00:46:59,774 --> 00:47:01,440 Він як і раніше збирається запустити через будь-якому випадку. 955 00:47:01,440 --> 00:47:03,872 Давайте просто сказати, що це був 1, 2, 3, 4. 956 00:47:03,872 --> 00:47:07,080 Незалежно від того, чи є він в порядок, це все одно б пробіг 957 00:47:07,080 --> 00:47:08,620 і досі перевіряється мінімальне значення. 958 00:47:08,620 --> 00:47:10,100 Це зробило б така ж кількість перевірок 959 00:47:10,100 --> 00:47:12,780 кожен раз, навіть якщо він насправді не чіпати. 960 00:47:12,780 --> 00:47:16,940 >> Таким чином, у такому випадку, кращим і гіршим Час автономної роботи фактично еквівалентні. 961 00:47:16,940 --> 00:47:19,160 Таким чином, очікуваний виконання селекційного сорту, 962 00:47:19,160 --> 00:47:23,790 які ми позначаємо символом тета, тета, в даному випадку, 963 00:47:23,790 --> 00:47:24,790 Також буде н квадрат. 964 00:47:24,790 --> 00:47:26,480 Всі ці три буде н квадрат. 965 00:47:26,480 --> 00:47:29,653 Це все зрозуміло, чому Середа виконання п квадраті? 966 00:47:29,653 --> 00:47:33,360 967 00:47:33,360 --> 00:47:33,980 >> Добре. 968 00:47:33,980 --> 00:47:39,120 Так що я просто хочу, щоб швидко бігти через іншу частину сортів. 969 00:47:39,120 --> 00:47:41,137 Алгоритм міхур sort-- пам'ятайте, 970 00:47:41,137 --> 00:47:43,220 це було першим Девід підійшов в лекції. 971 00:47:43,220 --> 00:47:46,000 По суті, ви крок через весь список 972 00:47:46,000 --> 00:47:48,950 і ви swap-- вас всього Порівняння двох одночасно. 973 00:47:48,950 --> 00:47:51,350 І якщо це більше, ніж ви просто поміняти їх місцями. 974 00:47:51,350 --> 00:47:53,590 Так що, якщо це більше, ви б поміняти. 975 00:47:53,590 --> 00:47:56,180 Я отримав офіційне право тут. 976 00:47:56,180 --> 00:47:59,100 >> Так що давайте просто сказати, що ви були 8, 6, 4, 2. 977 00:47:59,100 --> 00:48:00,571 Ви б порівняти 8 і 6. 978 00:48:00,571 --> 00:48:01,570 Ви повинні були б поміняти їх місцями. 979 00:48:01,570 --> 00:48:02,610 Ви б порівняти 8 і 4. 980 00:48:02,610 --> 00:48:03,609 Ви повинні були б поміняти їх місцями. 981 00:48:03,609 --> 00:48:07,000 Якщо у вас є, щоб поміняти 8 і 2, змінити їх. 982 00:48:07,000 --> 00:48:10,760 Таким чином, в такому сенсі, ви можете бачити, зіграна протягом тривалого періоду часу, 983 00:48:10,760 --> 00:48:13,730 як значення роду міхур кінці, який є, чому ми називаємо його 984 00:48:13,730 --> 00:48:15,320 бульбашкова сортування. 985 00:48:15,320 --> 00:48:19,950 >> Ми просто запустити через раз на наш другий прохід, і наш третій прохід, 986 00:48:19,950 --> 00:48:21,150 і наш четвертий прохід. 987 00:48:21,150 --> 00:48:25,820 По суті, бульбашкова сортування працює тільки до тих пір, поки не роблять ніяких більше свопи. 988 00:48:25,820 --> 00:48:31,109 Так що в цьому сенсі, це просто загальна псевдокод для нього. 989 00:48:31,109 --> 00:48:32,650 Не турбуйтеся, це не все буде на сайті. 990 00:48:32,650 --> 00:48:34,990 Ми не повинні насправді піти з цього приводу. 991 00:48:34,990 --> 00:48:38,134 >> Ми просто ініціалізувати лічильник змінна, яка починається з 0. 992 00:48:38,134 --> 00:48:39,800 І ми перебору всього масиву. 993 00:48:39,800 --> 00:48:43,420 І якщо одне значення, якщо це is-- значення більше, ніж дане значення, 994 00:48:43,420 --> 00:48:44,610 Ви збираєтеся поміняти їх місцями. 995 00:48:44,610 --> 00:48:46,860 І тоді ти просто продовжувати йти. 996 00:48:46,860 --> 00:48:47,970 І ви збираєтеся розраховувати. 997 00:48:47,970 --> 00:48:50,845 І ви тільки збираєтеся продовжувати робити це в той час лічильник більше 998 00:48:50,845 --> 00:48:53,345 ніж 0, що означає, що кожен раз, коли у вас є, щоб поміняти, 999 00:48:53,345 --> 00:48:55,220 Ви знаєте, ви хочете піти назад і ще раз перевірити. 1000 00:48:55,220 --> 00:48:59,510 Ви хочете, щоб тримати перевірку, поки ви не знаєте, що ви не повинні поміняти більше. 1001 00:48:59,510 --> 00:49:05,570 >> Так що найкращий і найгірший Справа середу виконання для бульбашкового сортування? 1002 00:49:05,570 --> 00:49:09,300 І hint-- це насправді відрізняється від вибору виду в сенсі 1003 00:49:09,300 --> 00:49:11,810 що ці два відповіді не збігаються. 1004 00:49:11,810 --> 00:49:14,709 Подумайте про те, що буде відбуватися в випадок, якщо він був уже відсортований. 1005 00:49:14,709 --> 00:49:16,500 І думати про те, що станеться, якщо він був 1006 00:49:16,500 --> 00:49:18,372 у випадку, в якому він не був відсортований. 1007 00:49:18,372 --> 00:49:20,580 І ви можете запустити вид через що, чому відбувається. 1008 00:49:20,580 --> 00:49:22,954 Я дам вам, хлопці, як, 30 секунд, щоб думати про це. 1009 00:49:22,954 --> 00:49:52,330 1010 00:49:52,330 --> 00:49:53,540 >> ДОБРЕ. 1011 00:49:53,540 --> 00:49:57,462 Хто-небудь є припущення, що в в гіршому випадку час виконання бульбашкового сортування є? 1012 00:49:57,462 --> 00:49:57,962 Так. 1013 00:49:57,962 --> 00:50:07,810 >> АУДИТОРІЯ: було б, як, п раз п мінус 1 або щось подібне? 1014 00:50:07,810 --> 00:50:10,650 Мовляв, кожен раз, коли він працює, це просто, як один своп менш 1015 00:50:10,650 --> 00:50:10,960 що б це не було. 1016 00:50:10,960 --> 00:50:12,668 >> ANDI Пен: Так, так Ви абсолютно праві. 1017 00:50:12,668 --> 00:50:15,940 І це той випадок, коли ваш Відповідь насправді більш складна 1018 00:50:15,940 --> 00:50:17,240 ніж ми повинні дати. 1019 00:50:17,240 --> 00:50:19,772 Так це буде run-- Я збираюся стерти все це тут. 1020 00:50:19,772 --> 00:50:20,480 Чи всі добре? 1021 00:50:20,480 --> 00:50:21,869 Чи можу я стерти це? 1022 00:50:21,869 --> 00:50:22,368 ДОБРЕ. 1023 00:50:22,368 --> 00:50:27,904 1024 00:50:27,904 --> 00:50:30,320 Ви збираєтеся працювати через п раз в перший раз, чи не так? 1025 00:50:30,320 --> 00:50:33,200 І вони збираються запустити через п мінус 1 вдруге, вірно? 1026 00:50:33,200 --> 00:50:37,130 І тоді ви будете тримати відбувається, п мій 2, і так далі. 1027 00:50:37,130 --> 00:50:40,210 Девід зробив це в лекції, де, якщо ви додали всі ці цінності, 1028 00:50:40,210 --> 00:50:48,080 Ви отримуєте те, що це like-- yeah-- більше 2, що істотно знижує просто 1029 00:50:48,080 --> 00:50:49,784 до п квадраті. 1030 00:50:49,784 --> 00:50:51,700 Ви збираєтеся отримати дивно частка там. 1031 00:50:51,700 --> 00:50:53,892 І так просто знаю, що п квадраті завжди 1032 00:50:53,892 --> 00:50:55,350 має пріоритет над фракцією. 1033 00:50:55,350 --> 00:50:58,450 І тому в цьому разі гіршого виконання буде н в квадраті. 1034 00:50:58,450 --> 00:51:00,210 Якби це було в порядку убування порядок, думаю, вам, 1035 00:51:00,210 --> 00:51:02,530 повинні зробити своп кожного разу. 1036 00:51:02,530 --> 00:51:05,170 >> Що б, потенційно, в кращому разі виконання? 1037 00:51:05,170 --> 00:51:08,580 Давайте просто сказати, що якщо список вже був в порядку, що б під час виконання буде? 1038 00:51:08,580 --> 00:51:09,565 >> АУДИТОРІЯ: п. 1039 00:51:09,565 --> 00:51:10,690 ANDI Пен: Це н, точно. 1040 00:51:10,690 --> 00:51:11,600 І чому це п? 1041 00:51:11,600 --> 00:51:13,850 АУДИТОРІЯ: тому що ви просто повинні перевірити на кожному разів. 1042 00:51:13,850 --> 00:51:14,770 ANDI Пен: Точно. 1043 00:51:14,770 --> 00:51:17,150 Таким чином, в кращому виконання, якщо цей список був вже 1044 00:51:17,150 --> 00:51:20,270 sorted-- скажімо 1, 2, 3, 4-- ви просто пройти, ви б перевірити, 1045 00:51:20,270 --> 00:51:21,720 ви побачите, ох, всі вони виправдалися. 1046 00:51:21,720 --> 00:51:22,636 У мене не було, щоб поміняти. 1047 00:51:22,636 --> 00:51:23,370 Я все. 1048 00:51:23,370 --> 00:51:26,500 Таким чином, в цьому випадку, це просто п або кількість кроків, які ви просто 1049 00:51:26,500 --> 00:51:29,870 повинен був перевірити в першому списку. 1050 00:51:29,870 --> 00:51:33,990 >> І після цього, ми тепер потрапив сортування вставками, де 1051 00:51:33,990 --> 00:51:39,260 алгоритм, по суті, розділити це в відсортованому і несортованих частини. 1052 00:51:39,260 --> 00:51:42,810 А потім один за іншим, невідсортоване значення 1053 00:51:42,810 --> 00:51:46,880 вставляється у відповідних позиції на початку списку. 1054 00:51:46,880 --> 00:51:52,120 >> Так, наприклад, у нас є Список 3, 5, 2, 6, 4 знову. 1055 00:51:52,120 --> 00:51:54,750 Ми знаємо, що це нині несортовані, тому що ми тільки що 1056 00:51:54,750 --> 00:51:57,030 почав дивитися на нього. 1057 00:51:57,030 --> 00:52:00,610 Ми дивимося і ми знаємо, що перше значення сортується, вірно? 1058 00:52:00,610 --> 00:52:04,190 Якщо ви тільки дивлячись на масив Розмір одного, ви знаєте, що це сортується. 1059 00:52:04,190 --> 00:52:08,230 >> Отже, ми знаємо, що Інші чотири несортоване. 1060 00:52:08,230 --> 00:52:10,980 Ми йдемо через, і ми бачимо, що значення. 1061 00:52:10,980 --> 00:52:11,730 Давайте повернемося. 1062 00:52:11,730 --> 00:52:13,130 Дивіться, що значення 5? 1063 00:52:13,130 --> 00:52:14,110 Ми дивимося на нього. 1064 00:52:14,110 --> 00:52:15,204 Ми порівнюємо його до 3. 1065 00:52:15,204 --> 00:52:17,870 Ми знаємо, що це більше, ніж 3, так що ми знаємо, що це сортується. 1066 00:52:17,870 --> 00:52:22,940 Таким чином, ми тепер знаємо, що перші два сортуються, а останні три не є. 1067 00:52:22,940 --> 00:52:24,270 >> Ми поглянемо на 2. 1068 00:52:24,270 --> 00:52:25,720 Спочатку ми перевіряємо його 5. 1069 00:52:25,720 --> 00:52:26,700 Це менше, ніж 5? 1070 00:52:26,700 --> 00:52:27,240 Це не. 1071 00:52:27,240 --> 00:52:29,510 Таким чином, ми повинні тримати дивлячись вниз. 1072 00:52:29,510 --> 00:52:30,940 Тоді ви перевірити 2 від 3. 1073 00:52:30,940 --> 00:52:31,850 Це менше, ніж? 1074 00:52:31,850 --> 00:52:32,350 Немає. 1075 00:52:32,350 --> 00:52:35,430 Таким чином, ви знаєте, що 2 повинен бути вставлений в передній і 3 і 5 1076 00:52:35,430 --> 00:52:38,200 обидва повинні бути витіснені. 1077 00:52:38,200 --> 00:52:42,190 Зробіть це знову 6 і 4. 1078 00:52:42,190 --> 00:52:48,962 І ми просто стежте суті, де ми просто перевірити, перевірити, перевірити. 1079 00:52:48,962 --> 00:52:51,170 І поки це не в праві посаду, ми б просто 1080 00:52:51,170 --> 00:52:54,890 вставте його в правильному положенні, який є, де ім'я прийшов. 1081 00:52:54,890 --> 00:52:59,830 >> Так що це просто алгоритм, псевдокод такої, начебто, 1082 00:52:59,830 --> 00:53:04,990 про те, як ми буде здійснювати сортування вставками. 1083 00:53:04,990 --> 00:53:05,954 Псевдокод тут. 1084 00:53:05,954 --> 00:53:06,620 Це все в Інтернеті. 1085 00:53:06,620 --> 00:53:10,720 Не турбуйтеся, якщо ви, хлопці, намагаючись скопіювати це вниз. 1086 00:53:10,720 --> 00:53:14,500 Отже, ще раз, то ж саме, що question-- буде кращим і гіршим автономної роботи 1087 00:53:14,500 --> 00:53:16,120 для вставки роду? 1088 00:53:16,120 --> 00:53:17,750 Це дуже схоже на останнє запитання. 1089 00:53:17,750 --> 00:53:20,479 Я дам вам, хлопці, як, 30 секунд, щоб думати про це, а також. 1090 00:53:20,479 --> 00:53:47,150 1091 00:53:47,150 --> 00:53:50,071 >> ОК чи хтось хоче дати мені найгірший виконання? 1092 00:53:50,071 --> 00:53:50,570 Так. 1093 00:53:50,570 --> 00:53:51,490 >> АУДИТОРІЯ: п в квадраті. 1094 00:53:51,490 --> 00:53:52,573 >> ANDI Пен: Це н квадраті. 1095 00:53:52,573 --> 00:53:53,730 І чому це п квадраті? 1096 00:53:53,730 --> 00:53:57,562 >> АУДИТОРІЯ: Тому що в зворотний порядок, у вас є 1097 00:53:57,562 --> 00:54:02,619 пройти через п раз п, is-- 1098 00:54:02,619 --> 00:54:03,660 ANDI Пен: Так, саме так. 1099 00:54:03,660 --> 00:54:06,610 Так само, як і в бульбашкового сортування. 1100 00:54:06,610 --> 00:54:08,720 Якщо цей список в порядку убування, ви 1101 00:54:08,720 --> 00:54:11,240 доведеться перевірити перший раз. 1102 00:54:11,240 --> 00:54:13,470 А потім з кожним додаткова вартість, ви 1103 00:54:13,470 --> 00:54:16,390 доведеться перевірити його проти кожен значення, вірно? 1104 00:54:16,390 --> 00:54:20,290 І так в цілому, ви збираєтеся зробити А.Н. раз н-пас другий п пройти, що 1105 00:54:20,290 --> 00:54:21,750 в п квадраті. 1106 00:54:21,750 --> 00:54:22,860 Що можна сказати про кращому випадку? 1107 00:54:22,860 --> 00:54:24,360 Так. 1108 00:54:24,360 --> 00:54:28,840 >> АУДИТОРІЯ: N мінус 1, оскільки Перший вже в квадрат. 1109 00:54:28,840 --> 00:54:30,270 >> ANDI Пен: Так, близько. 1110 00:54:30,270 --> 00:54:31,850 Відповідь насправді п. 1111 00:54:31,850 --> 00:54:37,189 Оскільки в той час як Перший сортувати, вона не може його actually-- 1112 00:54:37,189 --> 00:54:38,980 ми просто пощастило, в що приклад, що 2 1113 00:54:38,980 --> 00:54:40,930 відбулося найменше число. 1114 00:54:40,930 --> 00:54:43,680 Але не завжди буде так. 1115 00:54:43,680 --> 00:54:48,040 Якщо 2 вже відсортовані на початку але ви подивіться, і є 1 тут, 1116 00:54:48,040 --> 00:54:49,144 1 буде підняти його. 1117 00:54:49,144 --> 00:54:51,060 І це буде в кінцевому до того зіткнувся в будь-якому випадку. 1118 00:54:51,060 --> 00:54:56,250 >> Таким чином, в кращому випадку, це насправді просто буде н. 1119 00:54:56,250 --> 00:54:59,090 Якщо у вас є 1, 2, 3, 4, 5, 6, 7, 8, ви 1120 00:54:59,090 --> 00:55:00,940 збирається запустити через що весь список відразу 1121 00:55:00,940 --> 00:55:03,430 щоб перевірити, якщо все в порядку. 1122 00:55:03,430 --> 00:55:07,390 Це все ясно, на працюючому раз відбору, а? 1123 00:55:07,390 --> 00:55:09,960 Я знаю, що йду через це дуже швидко. 1124 00:55:09,960 --> 00:55:13,330 Але точно знаю, що, якщо ви знаєте, загальні поняття, ви повинні бути добре. 1125 00:55:13,330 --> 00:55:16,070 ДОБРЕ. 1126 00:55:16,070 --> 00:55:19,790 Так що я просто дам вам, хлопці, може бути, як, хвилину, щоб поговорити з вашими сусідами 1127 00:55:19,790 --> 00:55:21,890 на те, що лише деякі з основних відмінностей 1128 00:55:21,890 --> 00:55:23,540 між цими типами сортів. 1129 00:55:23,540 --> 00:56:24,571 1130 00:56:24,571 --> 00:56:25,570 Ми підемо над тим найближчим часом. 1131 00:56:25,570 --> 00:56:26,444 АУДИТОРІЯ: О, добре. 1132 00:56:26,444 --> 00:56:27,320 ANDI Пен: Так. 1133 00:56:27,320 --> 00:56:28,380 ДОБРЕ. 1134 00:56:28,380 --> 00:56:33,420 Прохолодний, давайте знову скликати як клас. 1135 00:56:33,420 --> 00:56:34,330 ДОБРЕ. 1136 00:56:34,330 --> 00:56:37,579 Так що це було свого роду відкрите питання в тому сенсі, 1137 00:56:37,579 --> 00:56:39,120 що є багато відповідей на них. 1138 00:56:39,120 --> 00:56:40,746 І ми будемо йти над деякими з них коротко. 1139 00:56:40,746 --> 00:56:43,411 Я просто хотів, щоб ви, хлопці думаючи про те, що диференційований 1140 00:56:43,411 --> 00:56:44,530 всі три типи сортів. 1141 00:56:44,530 --> 00:56:47,440 І почув я, також, великий question-- що ж сортування злиттям зробити? 1142 00:56:47,440 --> 00:56:50,110 Велике питання, тому що це те, що ми в наступному покриття. 1143 00:56:50,110 --> 00:56:52,850 >> Так об'єднати роду є один вид, що функції 1144 00:56:52,850 --> 00:56:56,100 дуже по-різному від інших видів. 1145 00:56:56,100 --> 00:56:58,180 Як ви, хлопці, можете see-- зробив Давид, що демо 1146 00:56:58,180 --> 00:57:01,130 де він все круто шуми, бачачи, як об'єднати 1147 00:57:01,130 --> 00:57:04,010 Сортувати побіг, як нескінченно швидше, ніж двох інших типів? 1148 00:57:04,010 --> 00:57:04,510 ДОБРЕ. 1149 00:57:04,510 --> 00:57:07,580 Так це тому, що злиття Сортувати реалізує цей розрив 1150 00:57:07,580 --> 00:57:11,020 і завоювати концепцію, що ми говорили багато про що в лекції. 1151 00:57:11,020 --> 00:57:14,550 У тому сенсі, що ми хотіли б працювати розумніше, а не важче, коли ви розділите 1152 00:57:14,550 --> 00:57:18,120 і завоювати проблеми, і зламати їх вниз, а потім покласти їх разом, 1153 00:57:18,120 --> 00:57:19,930 хороші речі завжди відбуваються. 1154 00:57:19,930 --> 00:57:21,960 >> Так так, що зливаються Сортувати по суті працює 1155 00:57:21,960 --> 00:57:24,660 є те, що ділить несортоване масив навпіл. 1156 00:57:24,660 --> 00:57:26,500 А потім він отримав дві половинки масивів. 1157 00:57:26,500 --> 00:57:28,220 І це якраз ті сортує дві половинки. 1158 00:57:28,220 --> 00:57:31,750 Він просто тримає ділення навпіл, в половина, навпіл, поки все не буде відсортований 1159 00:57:31,750 --> 00:57:33,680 а потім рекурсивно ставить все це разом. 1160 00:57:33,680 --> 00:57:36,550 >> Так що це дійсно абстрактною. 1161 00:57:36,550 --> 00:57:38,750 Так що це просто трохи псевдокоду. 1162 00:57:38,750 --> 00:57:41,040 Чи має це сенс у так, як це працює? 1163 00:57:41,040 --> 00:57:43,870 Так що давайте просто сказати, у вас є масив п елементів, правильно? 1164 00:57:43,870 --> 00:57:45,450 Якщо п менше, ніж 2, ви можете повернутися. 1165 00:57:45,450 --> 00:57:49,040 Тому що ви знаєте, що, якщо є тільки одна річ, вона повинна бути відсортовані. 1166 00:57:49,040 --> 00:57:52,600 В іншому випадку, ви сортувати ліву половину, а потім відсортувати праву половину, 1167 00:57:52,600 --> 00:57:54,140 і тоді ви зливаються. 1168 00:57:54,140 --> 00:57:56,979 >> Так в той час як виглядає насправді легко, насправді, думати про це це 1169 00:57:56,979 --> 00:58:00,270 вид важко. Тому що ви, як ну от начебто працює на себе. 1170 00:58:00,270 --> 00:58:00,769 Вірно? 1171 00:58:00,769 --> 00:58:02,430 Це працює на себе. 1172 00:58:02,430 --> 00:58:05,479 Так що в цьому сенсі, Девід торкнувся на рекурсії в класі. 1173 00:58:05,479 --> 00:58:07,270 І це поняття ми поговоримо про більш. 1174 00:58:07,270 --> 00:58:11,430 Це що це, ці дві лінії Тут, насправді це просто програма 1175 00:58:11,430 --> 00:58:13,860 кажу це, щоб запустити себе з іншого вхід. 1176 00:58:13,860 --> 00:58:17,230 Таким чином, замість запуску себе з повнота п елементів, 1177 00:58:17,230 --> 00:58:20,530 Ви можете розбити його вниз в ліва половина і права половина 1178 00:58:20,530 --> 00:58:22,680 а потім запустити його знову. 1179 00:58:22,680 --> 00:58:26,050 >> І тоді ми будемо дивитися на нього візуально, бо я візуальний учень. 1180 00:58:26,050 --> 00:58:27,270 Це працює краще для мене. 1181 00:58:27,270 --> 00:58:29,890 Таким чином, ми будемо дивитися на наочному прикладі тут. 1182 00:58:29,890 --> 00:58:36,237 >> Скажімо, ми маємо масив, шість Елементи, 3, 5, 2, 6, 4, 1, що не відсортовані. 1183 00:58:36,237 --> 00:58:37,820 Гаразд, є багато на цій сторінці. 1184 00:58:37,820 --> 00:58:43,179 Так що, якщо ви, хлопці, можете подивитися на Перший крок тут, 3, 5, 2, 6, 4, 1, 1185 00:58:43,179 --> 00:58:44,220 Ви можете розділити його навпіл. 1186 00:58:44,220 --> 00:58:45,976 У вас є 3, 5, 2, 6, 4, 1. 1187 00:58:45,976 --> 00:58:48,850 Ви знаєте, що це вам aren't-- не знаю, якщо вони сортуються чи ні, 1188 00:58:48,850 --> 00:58:52,517 так ви тримаєте розбиваючи їх в половині, навпіл, навпіл, поки врешті-решт, 1189 00:58:52,517 --> 00:58:53,600 у вас є тільки один елемент. 1190 00:58:53,600 --> 00:58:56,790 І один елемент завжди сортуються, вірно? 1191 00:58:56,790 --> 00:59:01,560 >> Отже, ми знаємо, що 3, 5, 2, 4, 6, 1, самі по собі, сортуються. 1192 00:59:01,560 --> 00:59:05,870 І тепер ми можемо покласти їх назад разом. 1193 00:59:05,870 --> 00:59:07,510 Таким чином, ми знаємо 3, 5. 1194 00:59:07,510 --> 00:59:08,510 Ставимо їх разом. 1195 00:59:08,510 --> 00:59:09,617 Ми знаємо, що це відсортований. 1196 00:59:09,617 --> 00:59:10,450 У 2-х досі там. 1197 00:59:10,450 --> 00:59:11,830 Ми можемо поставити 4 і 6 разом. 1198 00:59:11,830 --> 00:59:13,996 Ми знаємо, що це сортується, таким чином, ми покласти, що разом. 1199 00:59:13,996 --> 00:59:14,940 А 1 є. 1200 00:59:14,940 --> 00:59:18,720 >> А потім ви просто подивіться на ці дві половинки прямо тут. 1201 00:59:18,720 --> 00:59:21,300 Ви маєте 3, 5, 2, 2, 3, 5. 1202 00:59:21,300 --> 00:59:23,465 Ви можете просто порівняти початок усього. 1203 00:59:23,465 --> 00:59:26,340 Тому що ви знаєте, що це сортується і ви знаєте, що це сортується. 1204 00:59:26,340 --> 00:59:29,360 Тоді ви не повинні навіть порівняти 5, ви просто порівняти 3. 1205 00:59:29,360 --> 00:59:32,070 А 2 менше, ніж 3, так Ви знаєте, 2 необхідно перейти в кінець. 1206 00:59:32,070 --> 00:59:33,120 >> Те ж саме там. 1207 00:59:33,120 --> 00:59:34,740 1-необхідно перейти сюди. 1208 00:59:34,740 --> 00:59:37,330 А потім, коли ви йдете, щоб покласти ці два значення разом, 1209 00:59:37,330 --> 00:59:39,950 Ви знаєте, що це сортується і Ви знаєте, що сортується. 1210 00:59:39,950 --> 00:59:43,240 Так то 1 і 2, 1 становить менше 2. 1211 00:59:43,240 --> 00:59:45,570 Це говорить про те, що 1 повинні піти на кінці цього 1212 00:59:45,570 --> 00:59:47,480 навіть не дивлячись на 3 або 5. 1213 00:59:47,480 --> 00:59:50,100 А потім в 4, ви можете просто перевірити, що йде прямо тут. 1214 00:59:50,100 --> 00:59:51,480 Ви не повинні дивитися на 5. 1215 00:59:51,480 --> 00:59:52,570 Те ж саме з 6. 1216 00:59:52,570 --> 00:59:55,860 Ви знаєте, що це просто 6-- не повинні бути розглянуті. 1217 00:59:55,860 --> 00:59:57,870 >> І тому в цьому шляху, ви тільки врятувати себе 1218 00:59:57,870 --> 00:59:59,526 багато кроків, коли ви порівнюєте. 1219 00:59:59,526 --> 01:00:02,150 Ви не повинні порівнювати кожен Елемент з іншими елементами. 1220 01:00:02,150 --> 01:00:05,230 Ви просто порівняйте проти тих що вам потрібно, щоб порівняти її з. 1221 01:00:05,230 --> 01:00:06,870 Так що начебто абстрактної концепції. 1222 01:00:06,870 --> 01:00:10,540 Не турбуйтеся, якщо це не досить удару вас прямо ще. 1223 01:00:10,540 --> 01:00:14,740 Але, як правило, це як сортування злиттям працює. 1224 01:00:14,740 --> 01:00:17,750 Питання, простих запитань, перш, ніж я рухатися далі? 1225 01:00:17,750 --> 01:00:18,550 Так. 1226 01:00:18,550 --> 01:00:22,230 >> АУДИТОРІЯ: Так ви сказали, що ви берете 1, а потім 4 і 6 1227 01:00:22,230 --> 01:00:23,860 і поклав їх у. 1228 01:00:23,860 --> 01:00:26,800 Так не those-- НЕ Ви шукаєте на них 1229 01:00:26,800 --> 01:00:28,544 як окремі елементи, а не як в цілому? 1230 01:00:28,544 --> 01:00:29,210 ANDI Пен: Так. 1231 01:00:29,210 --> 01:00:32,020 Так, що відбувається є те, що ви в основному 1232 01:00:32,020 --> 01:00:33,650 створюють абсолютно новий масив. 1233 01:00:33,650 --> 01:00:36,690 Таким чином, ви знаєте, що, от, у мене є два масиви розміром 3, вірно? 1234 01:00:36,690 --> 01:00:39,600 Таким чином, ви знаєте, що мій відсортований масив повинен мати шість елементів. 1235 01:00:39,600 --> 01:00:42,270 Таким чином, ви просто створити Новий обсяг пам'яті. 1236 01:00:42,270 --> 01:00:44,270 Так ви ніби як будучи марнотратним пам'яті, 1237 01:00:44,270 --> 01:00:46,186 але це не має значення тому що це так мало. 1238 01:00:46,186 --> 01:00:48,590 Таким чином, ви дивитеся на 1 і ви подивіться на 2. 1239 01:00:48,590 --> 01:00:50,770 І ви знаєте, що 1 менше, ніж 2. 1240 01:00:50,770 --> 01:00:53,840 Таким чином, ви знаєте, що 1 повинні йти в початок всіх тих. 1241 01:00:53,840 --> 01:00:55,850 >> Ви навіть не потрібно дивитися на 3 та 5. 1242 01:00:55,850 --> 01:00:57,400 Таким чином, ви знаєте, 1 йде туди. 1243 01:00:57,400 --> 01:00:59,300 Тоді ви в основному відрубати 1. 1244 01:00:59,300 --> 01:01:00,370 Це, начебто, помер для нас. 1245 01:01:00,370 --> 01:01:03,690 Тоді ми просто повинні 2, 3, 5, а потім 4 і 6. 1246 01:01:03,690 --> 01:01:06,270 І тоді ви знаєте, що ви порівняти 4 і 2, 1247 01:01:06,270 --> 01:01:07,560 ой, 2 повинні піти туди. 1248 01:01:07,560 --> 01:01:09,685 Таким чином, ви грюкнути 2 вниз, рубайте його. 1249 01:01:09,685 --> 01:01:12,060 Тоді ви просто є 3 і 5 в 4 і 6. 1250 01:01:12,060 --> 01:01:14,650 І ви просто тримати його подрібнення поки ви не покласти їх у масиві. 1251 01:01:14,650 --> 01:01:17,110 >> АУДИТОРІЯ: Так ти просто завжди Порівнюючи [нерозбірливо]? 1252 01:01:17,110 --> 01:01:17,710 >> ANDI Пен: Точно. 1253 01:01:17,710 --> 01:01:19,590 Так що в цьому сенсі, ви просто порівняння, по суті, 1254 01:01:19,590 --> 01:01:21,240 один номер проти інший номер. 1255 01:01:21,240 --> 01:01:22,990 І тому що ви знаєте що це сортується, вам 1256 01:01:22,990 --> 01:01:24,350 не доведеться шукати через всі номери. 1257 01:01:24,350 --> 01:01:25,870 Ви просто повинні подивитися на перший. 1258 01:01:25,870 --> 01:01:27,582 І тоді ви можете просто грюкнути їх вниз, тому що ви знаєте, 1259 01:01:27,582 --> 01:01:29,640 вони належать, де вони повинні належати. 1260 01:01:29,640 --> 01:01:31,030 Так. 1261 01:01:31,030 --> 01:01:32,920 Гарне питання. 1262 01:01:32,920 --> 01:01:35,290 >> І потім, якщо кожен з вас трохи амбітний, 1263 01:01:35,290 --> 01:01:38,660 не соромтеся, щоб подивитися на цей код. 1264 01:01:38,660 --> 01:01:40,680 Це насправді фізична реалізація 1265 01:01:40,680 --> 01:01:42,150 про те, як ми повинні написати сортування злиттям. 1266 01:01:42,150 --> 01:01:44,070 І ви можете бачити, це дуже мало. 1267 01:01:44,070 --> 01:01:46,310 Але ідеї, що лежать в це досить складна. 1268 01:01:46,310 --> 01:01:50,865 Так що, якщо ви відчуваєте, як малюнок на це у виконанні домашніх завдань сьогодні, не соромтеся. 1269 01:01:50,865 --> 01:01:54,050 1270 01:01:54,050 --> 01:01:54,740 >> ДОБРЕ. 1271 01:01:54,740 --> 01:01:58,070 Так і Давид підійшов це в лекції. 1272 01:01:58,070 --> 01:02:00,660 Що в кращому випадку Час автономної роботи, в гіршому випадку час автономної роботи, 1273 01:02:00,660 --> 01:02:05,680 та очікувані автономної роботи від сортування злиттям? 1274 01:02:05,680 --> 01:02:07,260 Через пару секунд, щоб подумати. 1275 01:02:07,260 --> 01:02:11,198 Це досить важко, але вид інтуїтивним, якщо ви думаєте про це. 1276 01:02:11,198 --> 01:02:20,090 1277 01:02:20,090 --> 01:02:23,054 Добре. 1278 01:02:23,054 --> 01:02:25,269 >> Залу: в гіршому випадку п п журналу? 1279 01:02:25,269 --> 01:02:26,060 ANDI Пен: Точно. 1280 01:02:26,060 --> 01:02:29,380 І чому це п п увійти. 1281 01:02:29,380 --> 01:02:32,230 >> АУДИТОРІЯ: Хіба це не тому, що він стає експоненціально швидше, 1282 01:02:32,230 --> 01:02:35,390 так що це, як функції, які а просто бути п 1283 01:02:35,390 --> 01:02:37,529 квадрат або щось? 1284 01:02:37,529 --> 01:02:38,320 ANDI Пен: Точно. 1285 01:02:38,320 --> 01:02:40,750 Таким чином, причина, по якій виконання на це н журналу 1286 01:02:40,750 --> 01:02:44,310 п because--, що ти робити у всіх цих кроків? 1287 01:02:44,310 --> 01:02:46,190 Ви просто рубати його навпіл, вірно? 1288 01:02:46,190 --> 01:02:48,750 І тому, коли ми робимо увійти, все, що він робить 1289 01:02:48,750 --> 01:02:53,150 ділить проблему навпіл, в два рази, в два рази, в більше половини. 1290 01:02:53,150 --> 01:02:56,430 І в цьому сенсі, ви можете вид з усунути лінійну модель 1291 01:02:56,430 --> 01:02:57,510 що ми використали. 1292 01:02:57,510 --> 01:03:00,254 Тому що, коли ви нарізати речі в половині, це журнал. 1293 01:03:00,254 --> 01:03:02,420 Ось тільки математичний спосіб представлення його. 1294 01:03:02,420 --> 01:03:06,310 >> І, нарешті, в кінці, ви просто зробити один останній пас через 1295 01:03:06,310 --> 01:03:07,930 поставити всі з них в порядку, вірно? 1296 01:03:07,930 --> 01:03:10,330 І так, якщо ви просто повинні перевірити одну річ, це п. 1297 01:03:10,330 --> 01:03:13,420 І так ти начебто множення разом. 1298 01:03:13,420 --> 01:03:17,660 Так що це, як ви отримали, що остаточний перевірити п сюди з колоди п 1299 01:03:17,660 --> 01:03:18,390 тут. 1300 01:03:18,390 --> 01:03:21,060 І якщо помножити їм, що це н н увійти. 1301 01:03:21,060 --> 01:03:26,100 >> І так в кращому випадку і гірші Корпус і очікується, всі п п увійти. 1302 01:03:26,100 --> 01:03:27,943 Це також, як іншого роду. 1303 01:03:27,943 --> 01:03:30,090 Це як вибір роду в тому сенсі, що 1304 01:03:30,090 --> 01:03:32,131 Не має значення, що ваш Список, це просто буде 1305 01:03:32,131 --> 01:03:34,801 щоб зробити те ж саме кожного разу. 1306 01:03:34,801 --> 01:03:35,300 ДОБРЕ. 1307 01:03:35,300 --> 01:03:39,950 Отже, як ви, хлопці, можете бачити, навіть якщо рослини, які ми пішли through-- п 1308 01:03:39,950 --> 01:03:41,660 квадрат, це не дуже ефективно. 1309 01:03:41,660 --> 01:03:47,060 І навіть у цьому п п журналу не найефективнішим. 1310 01:03:47,060 --> 01:03:49,720 Якщо ви, хлопці, цікаво, є механізми сортування 1311 01:03:49,720 --> 01:03:54,310 які є настільки ефективно, що вони майже практично плоским в режимі виконання. 1312 01:03:54,310 --> 01:03:55,420 >> У вас є деякі журнал N. 1313 01:03:55,420 --> 01:03:58,190 У вас є деякі журнал журналу N. 1314 01:03:58,190 --> 01:04:00,330 Ми не торкаємося їх в цьому класі зараз. 1315 01:04:00,330 --> 01:04:02,663 Але якщо ви, хлопці, цікаво, не соромтеся Google, що 1316 01:04:02,663 --> 01:04:04,392 найбільш ефективні механізми сортування. 1317 01:04:04,392 --> 01:04:06,350 Я не знаю, чи є деякі дійсно смішні, 1318 01:04:06,350 --> 01:04:09,860 like-- є деякі дійсно смішні, які люди роблять. 1319 01:04:09,860 --> 01:04:12,210 І ви дивуєтеся, як вони коли-небудь думали про це. 1320 01:04:12,210 --> 01:04:15,730 Так Google, якщо у вас є запасний Час, на те, що деякі кумедні способи 1321 01:04:15,730 --> 01:04:17,730 що people-- а також ефективні ways-- люди 1322 01:04:17,730 --> 01:04:20,371 змогли реалізувати всілякі. 1323 01:04:20,371 --> 01:04:20,870 ДОБРЕ. 1324 01:04:20,870 --> 01:04:22,880 І ось тільки маленький зручний графік. 1325 01:04:22,880 --> 01:04:26,850 Я знаю все про тебе, до цього вікторині 0, буде у вашій кімнаті, ймовірно, намагається 1326 01:04:26,850 --> 01:04:27,960 запам'ятати це. 1327 01:04:27,960 --> 01:04:30,940 Так що приємно там для вас, хлопці. 1328 01:04:30,940 --> 01:04:37,120 Тільки не забувайте, логіку, made-- Тому ці цифри були відбувається. 1329 01:04:37,120 --> 01:04:39,870 Якщо ви завжди губиться, просто переконайтеся, впевнений, що ви знаєте, що сорти. 1330 01:04:39,870 --> 01:04:40,820 І ви можете запустити через їх у своєму розумі 1331 01:04:40,820 --> 01:04:42,903 щоб з'ясувати, чому ті, відповіді відповіді на ці питання. 1332 01:04:42,903 --> 01:04:46,250 1333 01:04:46,250 --> 01:04:47,600 >> Добре. 1334 01:04:47,600 --> 01:04:49,680 Отже, ми збираємося, щоб перемістити на, нарешті, пошуку. 1335 01:04:49,680 --> 01:04:51,638 Тому що, як тих з вас, хто читав PSET, 1336 01:04:51,638 --> 01:04:55,175 пошук також є частиною Проблема цьому тижні задає. 1337 01:04:55,175 --> 01:04:57,300 Вам буде запропоновано здійснити два типи пошуків. 1338 01:04:57,300 --> 01:05:00,070 Одним з них є лінійний пошук і одна двійковий пошук. 1339 01:05:00,070 --> 01:05:01,760 >> Таким чином, лінійний пошук досить легко. 1340 01:05:01,760 --> 01:05:04,070 Ви просто хочете, щоб пошук елемента зі списку, щоб побачити, якщо ви його отримаєте. 1341 01:05:04,070 --> 01:05:05,444 Ви просто повинні перебору. 1342 01:05:05,444 --> 01:05:08,170 І якщо він дорівнює те, ви можете просто повернути його, вірно? 1343 01:05:08,170 --> 01:05:10,890 Але той, що ми найбільш зацікавлені в розмові про 1344 01:05:10,890 --> 01:05:14,550 це бінарний пошук, право, яке є розділяй і володарюй механізм, який 1345 01:05:14,550 --> 01:05:18,190 Девід демонстрував в лекції. 1346 01:05:18,190 --> 01:05:20,810 >> Пам'ятайте приклад телефонної книги що він продовжує виховувати, 1347 01:05:20,810 --> 01:05:23,960 той, який він начебто боролися трохи на минулий рік, 1348 01:05:23,960 --> 01:05:27,530 де ви розділите задачу на половині, в два рази, в два рази, знову і знову, 1349 01:05:27,530 --> 01:05:30,730 поки ви не знайдете те, що ви шукаєте? 1350 01:05:30,730 --> 01:05:33,727 І ви отримали час виконання, що добре. 1351 01:05:33,727 --> 01:05:35,810 І ви можете бачити, це значно ефективнішим 1352 01:05:35,810 --> 01:05:39,080 ніж будь-який інший тип пошуку. 1353 01:05:39,080 --> 01:05:41,880 >> Таким чином, шлях, який ми б йти про реалізації двійкового пошуку 1354 01:05:41,880 --> 01:05:46,510 Тобто, якщо у нас було безліч, Індекс 0 до 6, сімох елементів, 1355 01:05:46,510 --> 01:05:49,790 ми можемо дивитися в середині, right-- вибачте, якщо наше запитання first-- 1356 01:05:49,790 --> 01:05:53,840 якщо ми хочемо, щоб поставити запитання про, що не масив містить елемент 7, 1357 01:05:53,840 --> 01:05:56,840 Очевидно, будучи людей, і має такий маленький масив, це просто для нас 1358 01:05:56,840 --> 01:05:58,210 щоб сказати так. 1359 01:05:58,210 --> 01:06:05,750 Але шлях до реалізації двійковий Пошук буде виглядати в середині. 1360 01:06:05,750 --> 01:06:08,020 >> Ми знаємо, що індекс 3 середній, тому що ми 1361 01:06:08,020 --> 01:06:09,270 знаю, що є сім елементів. 1362 01:06:09,270 --> 01:06:10,670 Що 7 ділиться на 2? 1363 01:06:10,670 --> 01:06:12,850 Ви можете відрубати що додатковий 1. 1364 01:06:12,850 --> 01:06:14,850 Ви отримали 3 в середині. 1365 01:06:14,850 --> 01:06:17,590 Так масив з 3 одно 7? 1366 01:06:17,590 --> 01:06:18,900 Це не так, вірно? 1367 01:06:18,900 --> 01:06:21,050 Але ми можемо зробити пару чеків. 1368 01:06:21,050 --> 01:06:25,380 Це масив з 3 менше, ніж 7 або це масив з 3 більше, ніж 7? 1369 01:06:25,380 --> 01:06:27,240 >> І ми знаємо, що це менше, ніж 7. 1370 01:06:27,240 --> 01:06:30,259 Отже, ми знаємо, що, ну, вона повинна не може бути в лівій половині. 1371 01:06:30,259 --> 01:06:32,300 Ми знаємо, що це має бути в правій половині, вірно? 1372 01:06:32,300 --> 01:06:34,662 Таким чином, ми можемо просто відрубати половину масиву. 1373 01:06:34,662 --> 01:06:36,370 Ми навіть не повинні дивитися на нього більше. 1374 01:06:36,370 --> 01:06:38,711 Тому що ми знаємо, що половина нашого problem-- 1375 01:06:38,711 --> 01:06:41,210 ми знаємо, що відповідь знаходиться в права половина нашого завдання. 1376 01:06:41,210 --> 01:06:42,580 Таким чином, ми просто подивіться на це зараз. 1377 01:06:42,580 --> 01:06:44,860 >> Так що тепер ми дивимося на Середина те, що залишилося. 1378 01:06:44,860 --> 01:06:46,880 Цей показник 5. 1379 01:06:46,880 --> 01:06:50,200 Ми робимо те ж саме ще раз перевірку і ми бачимо, що це менше. 1380 01:06:50,200 --> 01:06:52,050 Таким чином, ми дивимося в лівій частині, що. 1381 01:06:52,050 --> 01:06:53,430 І тоді ми бачимо, що чек. 1382 01:06:53,430 --> 01:06:57,600 Чи є значення масиву в Індекс 4 дорівнює 7? 1383 01:06:57,600 --> 01:06:58,260 Це є. 1384 01:06:58,260 --> 01:07:03,580 Таким чином, ми можемо повернутися так, тому що ми знайшли значення в нашому списку. 1385 01:07:03,580 --> 01:07:06,738 Лі шлях я пройшов що сенс всім? 1386 01:07:06,738 --> 01:07:08,760 ДОБРЕ. 1387 01:07:08,760 --> 01:07:11,670 Я дам вам, хлопці, може бути, як, три, чотири хвилини, щоб з'ясувати, 1388 01:07:11,670 --> 01:07:13,270 як псевдокод це. 1389 01:07:13,270 --> 01:07:18,070 >> Отже, уявіть, я попросив вас написати Функція називається пошук (), що повернувся 1390 01:07:18,070 --> 01:07:20,640 значення, логічне значення, що це правда чи false-- як, 1391 01:07:20,640 --> 01:07:22,970 вірно, якщо ви знайшли значення, брехня, якщо ви не зробили. 1392 01:07:22,970 --> 01:07:25,230 І тоді ви були пройшов у вартості ви 1393 01:07:25,230 --> 01:07:28,410 шукали в цінності, які це array-- о, я виразно поставити 1394 01:07:28,410 --> 01:07:29,410 що в неправильному місці. 1395 01:07:29,410 --> 01:07:29,580 ДОБРЕ. 1396 01:07:29,580 --> 01:07:31,829 У кожному разі, що повинно бути був праворуч значень. 1397 01:07:31,829 --> 01:07:36,280 А потім Int N це число елементів у цьому масиві. 1398 01:07:36,280 --> 01:07:39,430 Як би ви йти про спробу в псевдокоді цю проблему в? 1399 01:07:39,430 --> 01:07:41,630 Я дам вам, хлопці, як три хвилини, щоб зробити це. 1400 01:07:41,630 --> 01:08:00,137 1401 01:08:00,137 --> 01:08:02,595 Ні, я думаю, що є only-- да, є одна прямо тут. 1402 01:08:02,595 --> 01:08:03,261 АУДИТОРІЯ: Чи можу я? 1403 01:08:03,261 --> 01:08:04,388 ANDI Пен: Так, у мене є ти. 1404 01:08:04,388 --> 01:08:09,410 1405 01:08:09,410 --> 01:08:11,050 Це працює? 1406 01:08:11,050 --> 01:08:12,290 ОК здорово. 1407 01:08:12,290 --> 01:10:43,590 1408 01:10:43,590 --> 01:10:44,720 >> ДОБРЕ. 1409 01:10:44,720 --> 01:10:47,630 Всі правильні хлопці, ми збирається приборкати його. 1410 01:10:47,630 --> 01:10:49,730 ДОБРЕ. 1411 01:10:49,730 --> 01:10:54,020 Так припустимо, що у нас є ця прекрасна трохи масив з п значень в ньому. 1412 01:10:54,020 --> 01:10:55,170 Я не малювати лінії. 1413 01:10:55,170 --> 01:10:58,649 Але як би ми йти про намагаюся написати це? 1414 01:10:58,649 --> 01:11:00,440 Хто-небудь хоче дати мені першу лінію? 1415 01:11:00,440 --> 01:11:02,814 Якщо ви хочете, щоб дати мені Перший рядок цього псевдокоду. 1416 01:11:02,814 --> 01:11:06,563 1417 01:11:06,563 --> 01:11:08,430 >> АУДИТОРІЯ: [нерозбірливо] 1418 01:11:08,430 --> 01:11:10,138 АУДИТОРІЯ: Ви хотіли для перебору through-- 1419 01:11:10,138 --> 01:11:11,094 АУДИТОРІЯ: Просто ще один цикл? 1420 01:11:11,094 --> 01:11:11,760 АУДИТОРІЯ: --Для. 1421 01:11:11,760 --> 01:11:15,880 1422 01:11:15,880 --> 01:11:17,780 >> ANDI Пен: Так що це одне трохи складніше. 1423 01:11:17,780 --> 01:11:23,130 Подумайте about-- ви хочете тримати працює цей цикл 1424 01:11:23,130 --> 01:11:27,950 знову і знову, поки, коли? 1425 01:11:27,950 --> 01:11:30,819 >> АУДИТОРІЯ: До [нерозбірливо] значення дорівнює цьому значенню. 1426 01:11:30,819 --> 01:11:31,610 ANDI Пен: Точно. 1427 01:11:31,610 --> 01:11:33,900 Таким чином, ви можете насправді просто write-- ми можемо навіть спростити його більше. 1428 01:11:33,900 --> 01:11:35,630 Ми можемо просто зробити той час як цикл, вірно? 1429 01:11:35,630 --> 01:11:39,380 Таким чином, ви можете просто loop-- ми знаємо, що це якийсь час. 1430 01:11:39,380 --> 01:11:42,850 Але зараз, я збираюся сказати "петлю" - через що? 1431 01:11:42,850 --> 01:11:46,640 Цикл until-- що наш закінчуючи стан? 1432 01:11:46,640 --> 01:11:47,510 Я думаю, що я чув. 1433 01:11:47,510 --> 01:11:48,530 Я чув, хтось сказати. 1434 01:11:48,530 --> 01:11:51,255 >> Аудиторія: Значення дорівнює середину. 1435 01:11:51,255 --> 01:11:52,255 ANDI Пен: Скажи це ще раз. 1436 01:11:52,255 --> 01:11:54,470 АУДИТОРІЯ: Або, до Значення ви шукаєте 1437 01:11:54,470 --> 01:11:58,470 Для дорівнює середнього значення. 1438 01:11:58,470 --> 01:12:00,280 >> ANDI Пен: Що робити, якщо це не там? 1439 01:12:00,280 --> 01:12:03,113 Що робити, якщо значення ви шукаєте для насправді не в цьому масиві? 1440 01:12:03,113 --> 01:12:05,890 АУДИТОРІЯ: Ви повертаєтеся 1. 1441 01:12:05,890 --> 01:12:08,850 >> ANDI Пен: Але те, що ми хочемо, щоб цикл до якщо у нас є стан? 1442 01:12:08,850 --> 01:12:09,350 Так. 1443 01:12:09,350 --> 01:12:11,239 >> АУДИТОРІЯ: поки є тільки одне значення? 1444 01:12:11,239 --> 01:12:13,530 ANDI Пен: Ви можете цикл until-- так що ви знаєте, що ви 1445 01:12:13,530 --> 01:12:15,714 матиме максимальне значення, чи не так? 1446 01:12:15,714 --> 01:12:18,130 І ви знаєте, що ви збираєтеся мати значення хв, вірно? 1447 01:12:18,130 --> 01:12:20,379 Тому що також, це те, що Я забув сказати, перш ніж, 1448 01:12:20,379 --> 01:12:22,640 що щось, що це критично бінарного пошуку 1449 01:12:22,640 --> 01:12:24,182 є те, що ваш масив вже відсортовані. 1450 01:12:24,182 --> 01:12:26,973 Тому що немає ніякого способу робити це, якщо вони просто випадкові значення. 1451 01:12:26,973 --> 01:12:29,190 Ви не знаєте, якщо один це більше, ніж інші, вірно? 1452 01:12:29,190 --> 01:12:32,720 >> Таким чином, ви знаєте, що ваш Макс і Ваші хвилин тут, вірно? 1453 01:12:32,720 --> 01:12:35,590 Якщо ви збираєтеся бути регулювання Ваш макс в ваших хвилин і mid-- 1454 01:12:35,590 --> 01:12:38,470 давайте припустимо, ваш Значення середнього правильно here-- 1455 01:12:38,470 --> 01:12:43,910 Ви збираєтеся в основному цикл доти, мінімальна НЕ 1456 01:12:43,910 --> 01:12:47,510 приблизно те ж саме, як ваш макс, прямо або якщо ваш максимум не те ж саме, як ваш хв. 1457 01:12:47,510 --> 01:12:48,040 Вірно? 1458 01:12:48,040 --> 01:12:51,340 Тому що, коли це станеться, ви знаєте, що Ви в кінцевому підсумку потрапив у таке ж значення. 1459 01:12:51,340 --> 01:12:59,135 Так ви не хочете, щоб петлі, поки ваш хв менше або дорівнює, метою яких упс, 1460 01:12:59,135 --> 01:13:01,510 не менше або дорівнює, інакше around-- Макс. 1461 01:13:01,510 --> 01:13:15,110 1462 01:13:15,110 --> 01:13:16,160 >> Хіба що сенс? 1463 01:13:16,160 --> 01:13:18,810 Я взяв кілька спроб, щоб отримати це право. 1464 01:13:18,810 --> 01:13:21,869 Але цикл, поки ваш максимального значення по суті майже немає 1465 01:13:21,869 --> 01:13:23,410 ніж або дорівнює вашої мінімум, вірно? 1466 01:13:23,410 --> 01:13:25,201 Ось коли ви знаєте, що ви зійшлися. 1467 01:13:25,201 --> 01:13:29,290 АУДИТОРІЯ: Коли ваша максимальна значення менше, ніж мінімум? 1468 01:13:29,290 --> 01:13:31,040 ANDI Пен: Якщо ви тримаєте регулюючи його, що 1469 01:13:31,040 --> 01:13:32,380 це те, що ми збираємося щоб робити в цьому. 1470 01:13:32,380 --> 01:13:33,460 Чи має це сенс? 1471 01:13:33,460 --> 01:13:35,750 Мінімальна і максимальна просто цілі числа, ми, ймовірно, 1472 01:13:35,750 --> 01:13:39,260 збирається хочете створити, щоб тримати трек, де ми шукаємо. 1473 01:13:39,260 --> 01:13:41,790 Оскільки масив існує незалежно від того, що ми робимо. 1474 01:13:41,790 --> 01:13:45,030 Мовляв, ми насправді не фізично відрубування масиву, вірно? 1475 01:13:45,030 --> 01:13:47,261 Ми просто регулюючи де ми шукаємо. 1476 01:13:47,261 --> 01:13:48,136 Чи має це сенс? 1477 01:13:48,136 --> 01:13:48,472 >> АУДИТОРІЯ: Так. 1478 01:13:48,472 --> 01:13:49,110 >> ANDI Пен: ОК. 1479 01:13:49,110 --> 01:13:57,090 Так що, якщо ця умова нашої петлі, те, що ми хочемо всередині цієї петлі? 1480 01:13:57,090 --> 01:13:58,700 Що ми збираємося бути бажання зробити? 1481 01:13:58,700 --> 01:14:02,390 Так що зараз, у нас є макс і мін, право, 1482 01:14:02,390 --> 01:14:04,962 ймовірно, створена десь тут. 1483 01:14:04,962 --> 01:14:07,170 Ми збираємося, ймовірно, хочете знайти середину, вірно? 1484 01:14:07,170 --> 01:14:08,450 Як ми збираємося, щоб бути можливість знайти середину? 1485 01:14:08,450 --> 01:14:09,491 Що mathematical-- 1486 01:14:09,491 --> 01:14:11,079 АУДИТОРІЯ: Макс плюс хв розділені на 2. 1487 01:14:11,079 --> 01:14:11,870 ANDI Пен: Точно. 1488 01:14:11,870 --> 01:14:20,300 1489 01:14:20,300 --> 01:14:21,620 Чи має це сенс? 1490 01:14:21,620 --> 01:14:25,780 І ви, хлопці, зрозуміти, чому ми не просто use--, чому ми зробили це 1491 01:14:25,780 --> 01:14:27,850 а не робити просто п ділиться на 2? 1492 01:14:27,850 --> 01:14:30,310 Це тому, що п є значення що збирається залишитися те ж саме. 1493 01:14:30,310 --> 01:14:30,979 Вірно? 1494 01:14:30,979 --> 01:14:34,020 Але, як ми скорегуємо нашу мінімум і Максимальні значення, вони збираються змінити. 1495 01:14:34,020 --> 01:14:36,040 І в результаті, наш середній збирається змінювати занадто. 1496 01:14:36,040 --> 01:14:37,873 Так ось чому ми хочемо зробити це прямо тут. 1497 01:14:37,873 --> 01:14:38,510 ДОБРЕ. 1498 01:14:38,510 --> 01:14:41,600 >> А потім, в даний час, що ми знайшли our-- так. 1499 01:14:41,600 --> 01:14:44,270 >> АУДИТОРІЯ: Просто швидко question-- коли ви говорите, мін і макс, 1500 01:14:44,270 --> 01:14:46,410 ми припускаючи, що це вже відсортовані? 1501 01:14:46,410 --> 01:14:48,400 >> ANDI Пен: Так, це насправді передумовою для бінарного пошуку, 1502 01:14:48,400 --> 01:14:49,816 що ви повинні знати, що це сортується. 1503 01:14:49,816 --> 01:14:53,660 Саме тому-то, ви пишете у вашому Проблема встановити до вашого бінарного пошуку. 1504 01:14:53,660 --> 01:14:55,910 ДОБРЕ. 1505 01:14:55,910 --> 01:14:58,876 Так що тепер ми знаємо, де наша середина є те, що ви хочете зробити тут? 1506 01:14:58,876 --> 01:15:01,789 1507 01:15:01,789 --> 01:15:04,319 >> АУДИТОРІЯ: Ми хочемо, щоб порівняти що до іншого. 1508 01:15:04,319 --> 01:15:05,110 ANDI Пен: Точно. 1509 01:15:05,110 --> 01:15:12,280 Таким чином, ви будете порівнювати з середини до значення, чи не так? 1510 01:15:12,280 --> 01:15:14,900 1511 01:15:14,900 --> 01:15:18,670 І що це говорить нам, коли ми порівнюємо? 1512 01:15:18,670 --> 01:15:22,226 Що ми хочемо робити далі? 1513 01:15:22,226 --> 01:15:25,389 >> АУДИТОРІЯ: Якщо значення більше ніж середині, ми хочемо, щоб відрізати його. 1514 01:15:25,389 --> 01:15:26,180 ANDI Пен: Точно. 1515 01:15:26,180 --> 01:15:33,940 Таким чином, якщо значення більше ніж середині, ми 1516 01:15:33,940 --> 01:15:36,550 захоче змінити ці Мінімальна і вичерпаний, вірно? 1517 01:15:36,550 --> 01:15:38,980 Що ми хочемо змінити? 1518 01:15:38,980 --> 01:15:42,145 Так що, якщо ми знаємо, що десь значення тут, що ви у нас змінити? 1519 01:15:42,145 --> 01:15:44,758 Ми хочемо змінити нашу Мінімальний бути в середині, чи не так? 1520 01:15:44,758 --> 01:15:49,420 1521 01:15:49,420 --> 01:15:54,292 А потім ще, якщо він знаходиться в цьому половина, що ми хочемо змінити? 1522 01:15:54,292 --> 01:15:55,306 >> АУДИТОРІЯ: Ваша максимальна. 1523 01:15:55,306 --> 01:15:55,972 ANDI Пен: Так. 1524 01:15:55,972 --> 01:16:02,597 1525 01:16:02,597 --> 01:16:04,680 А потім ви просто тримати цикл, вірно? 1526 01:16:04,680 --> 01:16:08,920 Тому що зараз, після однієї ітерації через, у вас є макс тут. 1527 01:16:08,920 --> 01:16:10,760 І тоді ви можете перерахувати середині. 1528 01:16:10,760 --> 01:16:11,990 І тоді ви можете порівняти. 1529 01:16:11,990 --> 01:16:14,766 І ви збираєтеся продовжувати не до хвилин і Maxes 1530 01:16:14,766 --> 01:16:15,890 істотно зійшлися. 1531 01:16:15,890 --> 01:16:17,890 І ось, коли ви знаєте, що Ви потрапили в кінець. 1532 01:16:17,890 --> 01:16:20,280 І або ви знайшли його або ви не в цій точці. 1533 01:16:20,280 --> 01:16:23,170 >> Чи має це сенс для всіх? 1534 01:16:23,170 --> 01:16:26,020 1535 01:16:26,020 --> 01:16:26,770 ДОБРЕ. 1536 01:16:26,770 --> 01:16:27,900 Це дуже важливо, тому що ви будете мати 1537 01:16:27,900 --> 01:16:29,760 щоб написати це в коді сьогодні. 1538 01:16:29,760 --> 01:16:32,660 Але ви, хлопці, є дуже хороший відчуття, що ви повинні робити, 1539 01:16:32,660 --> 01:16:34,051 і це добре. 1540 01:16:34,051 --> 01:16:34,550 ДОБРЕ. 1541 01:16:34,550 --> 01:16:38,840 Отже, ми отримали близько семи хвилини залишилося розділ. 1542 01:16:38,840 --> 01:16:43,170 Таким чином, ми будемо говорити про це PSET, що ми будемо робити. 1543 01:16:43,170 --> 01:16:46,410 Таким чином, PSET розділений на дві половини. 1544 01:16:46,410 --> 01:16:50,230 Перша половина включає реалізації знахідку 1545 01:16:50,230 --> 01:16:54,210 в якому Ви пишете, лінійний пошук, А бінарний пошук, і алгоритм сортування. 1546 01:16:54,210 --> 01:16:56,690 >> Таким чином, це є першим раз в PSET де 1547 01:16:56,690 --> 01:17:00,050 ми будемо давати вам, хлопці, що називається Код розподілу, який є код 1548 01:17:00,050 --> 01:17:02,740 що ми попередньо написано, але просто залишили кілька шматків від 1549 01:17:02,740 --> 01:17:04,635 для Вас, щоб закінчити запис. 1550 01:17:04,635 --> 01:17:07,510 Таким чином, ви, хлопці, коли ви дивитеся на це Код, ви могли б отримати дійсно страшно. 1551 01:17:07,510 --> 01:17:08,630 Якщо ви просто хочете, Ах, я не знаю, що робить, 1552 01:17:08,630 --> 01:17:11,670 Я не знаєте, як, здається, що так складно, ах, розслабитися. 1553 01:17:11,670 --> 01:17:12,170 Все добре. 1554 01:17:12,170 --> 01:17:12,930 Читайте специфікацію. 1555 01:17:12,930 --> 01:17:16,920 Специфікація буде пояснити вам точно що всі ці програми роблять. 1556 01:17:16,920 --> 01:17:20,560 >> Наприклад, generate.c програма що прийде з вашого PSET. 1557 01:17:20,560 --> 01:17:24,060 Ви насправді не мають до неї доторкнутися, але Ви повинні розуміти, що він робить. 1558 01:17:24,060 --> 01:17:28,550 І generate.c, все це робить, або генерації випадкових чисел 1559 01:17:28,550 --> 01:17:32,400 або ви можете дати йому насіння, як у умовний номер, який він приймає, 1560 01:17:32,400 --> 01:17:34,140 і генерує більше число. 1561 01:17:34,140 --> 01:17:37,170 Таким чином, є певний спосіб, щоб здійснити generate.c, в якому 1562 01:17:37,170 --> 01:17:42,760 ви можете просто зробити купу цифр для вас, щоб перевірити свої інші методи на. 1563 01:17:42,760 --> 01:17:45,900 >> Так що, якщо ви хочете, щоб для Наприклад, перевірити свої знахідки, 1564 01:17:45,900 --> 01:17:48,970 Ви хотіли б, щоб запустити generate.c, генерувати купу цифр, 1565 01:17:48,970 --> 01:17:50,880 а потім запустити функцію помічників. 1566 01:17:50,880 --> 01:17:53,930 Ваша функція помічники де ви насправді фізично написання коду. 1567 01:17:53,930 --> 01:17:59,330 І думаю, помічників у вигляді файлу бібліотеки Ви пишете, що знахідка дзвонить. 1568 01:17:59,330 --> 01:18:02,950 І так протягом helpers.c, ви будете зробити пошуку і сортування. 1569 01:18:02,950 --> 01:18:06,500 >> І тоді ви будете по суті просто покласти їх всі разом. 1570 01:18:06,500 --> 01:18:10,350 Специфікація скаже вам, як покласти, що в командному рядку. 1571 01:18:10,350 --> 01:18:14,880 І ви зможете перевірити, чи є не ваша сортування і пошуку працюють. 1572 01:18:14,880 --> 01:18:15,870 Прохолодний. 1573 01:18:15,870 --> 01:18:18,720 Хто-небудь вже почалася, і зустрічаються проблеми або питання 1574 01:18:18,720 --> 01:18:20,520 вони мають зараз з цим? 1575 01:18:20,520 --> 01:18:21,020 ДОБРЕ. 1576 01:18:21,020 --> 01:18:21,476 >> АУДИТОРІЯ: Зачекайте. 1577 01:18:21,476 --> 01:18:21,932 У мене є питання. 1578 01:18:21,932 --> 01:18:22,844 >> ANDI Пен: Так. 1579 01:18:22,844 --> 01:18:28,390 >> АУДИТОРІЯ: Так що я почав робити лінійний пошук в helpers.c 1580 01:18:28,390 --> 01:18:29,670 і це не було дійсно працює. 1581 01:18:29,670 --> 01:18:34,590 Але потім я дізнався, ми просто повинні видалити його і зробити бінарний пошук. 1582 01:18:34,590 --> 01:18:36,991 Так чи не все одно, якщо він не працює? 1583 01:18:36,991 --> 01:18:39,700 1584 01:18:39,700 --> 01:18:41,510 >> ANDI Пен: Коротка відповідь: ні. 1585 01:18:41,510 --> 01:18:42,642 Але так як ми не-- 1586 01:18:42,642 --> 01:18:44,350 АУДИТОРІЯ: Але ніхто не насправді перевірки. 1587 01:18:44,350 --> 01:18:46,058 ANDI Пен: Ми ніколи не побачите, що. 1588 01:18:46,058 --> 01:18:49,590 Але ви, мабуть, хочете, щоб що ваш пошук роботи. 1589 01:18:49,590 --> 01:18:51,700 Тому що, якщо ваш лінійний пошук не працює, 1590 01:18:51,700 --> 01:18:54,410 то швидше за все, ваш бінарний Пошук не буде працювати, як добре. 1591 01:18:54,410 --> 01:18:56,646 Тому що у вас є подібне Логіка в них обох. 1592 01:18:56,646 --> 01:18:58,020 І немає, це не має значення. 1593 01:18:58,020 --> 01:19:01,300 Таким чином, єдиними ви включите в є свого роду і бінарний пошук. 1594 01:19:01,300 --> 01:19:02,490 Так. 1595 01:19:02,490 --> 01:19:06,610 >> А також, багато дітей були намагаючись зібрати helpers.c. 1596 01:19:06,610 --> 01:19:09,550 Ви насправді не допускаються щоб зробити це, бо helpers.c 1597 01:19:09,550 --> 01:19:11,200 не має основну функцію. 1598 01:19:11,200 --> 01:19:13,550 І тому ви повинні тільки бути насправді компіляції 1599 01:19:13,550 --> 01:19:18,670 генерувати і знайти, бо знайти дзвінки helpers.c і функції в ній. 1600 01:19:18,670 --> 01:19:20,790 Так що робить налагодження біль в дупі. 1601 01:19:20,790 --> 01:19:22,422 Але це те, що ми повинні робити. 1602 01:19:22,422 --> 01:19:23,880 АУДИТОРІЯ: Ви просто зробити все, вірно? 1603 01:19:23,880 --> 01:19:27,290 ANDI Пен: ви можете просто зробити все як добре, так. 1604 01:19:27,290 --> 01:19:28,060 ДОБРЕ. 1605 01:19:28,060 --> 01:19:32,570 Так ось воно що в плані того, що PSET просить, щоб ви все робите. 1606 01:19:32,570 --> 01:19:35,160 Якщо у вас є які-небудь питання, будь ласка, вільним запитати мені після розділу. 1607 01:19:35,160 --> 01:19:37,580 Я буду тут, як, 20 хвилин. 1608 01:19:37,580 --> 01:19:40,500 >> І так, Pset-х дійсно не так уже й погано. 1609 01:19:40,500 --> 01:19:41,680 Ви, хлопці, повинно бути в порядку. 1610 01:19:41,680 --> 01:19:43,250 Вони, просто дотримуйтесь рекомендацій. 1611 01:19:43,250 --> 01:19:47,840 Вид є почуття, за логікою, те, що має відбуватися, і ви будете в порядку. 1612 01:19:47,840 --> 01:19:48,690 Не надто страшно. 1613 01:19:48,690 --> 01:19:50,220 Там дуже багато коду вже написано. 1614 01:19:50,220 --> 01:19:53,011 Не надто страшно, якщо ви не зрозуміти, що все це означає. 1615 01:19:53,011 --> 01:19:54,749 Якщо це багато, це абсолютно нормально. 1616 01:19:54,749 --> 01:19:55,790 І прийшли до офісної годин. 1617 01:19:55,790 --> 01:19:57,520 Ми допоможемо вам поглянути. 1618 01:19:57,520 --> 01:20:00,810 >> АУДИТОРІЯ: з додатковими Функції, ми дивимося ті до? 1619 01:20:00,810 --> 01:20:03,417 >> ANDI Пен: Так, ті в коді. 1620 01:20:03,417 --> 01:20:05,750 У грі 15, половина з це вже написана для вас. 1621 01:20:05,750 --> 01:20:09,310 Так що ті функції вже в коді. 1622 01:20:09,310 --> 01:20:12,020 Так. 1623 01:20:12,020 --> 01:20:12,520 Добре. 1624 01:20:12,520 --> 01:20:14,000 Ну, удачі. 1625 01:20:14,000 --> 01:20:15,180 Це огидно день. 1626 01:20:15,180 --> 01:20:19,370 Так сподіваюся, ви, хлопці, не відчувати себе занадто погано про перебування всередині і кодування. 1627 01:20:19,370 --> 01:20:22,133