1 00:00:00,000 --> 00:00:00,990 2 00:00:00,990 --> 00:00:02,970 >> [Грає музика] 3 00:00:02,970 --> 00:00:10,400 4 00:00:10,400 --> 00:00:12,550 >> Девід Дж Малан: Це CS50. 5 00:00:12,550 --> 00:00:14,612 І це почало тижні три. 6 00:00:14,612 --> 00:00:16,820 Таким чином, ми отримали багато цікавої речі, щоб покрити сьогодні. 7 00:00:16,820 --> 00:00:20,160 Багато можливостей для добровольців на сцені. 8 00:00:20,160 --> 00:00:22,780 І в кінцевому рахунку, сьогодні нема про коді взагалі. 9 00:00:22,780 --> 00:00:24,820 Але це про ідеї, і це про алгоритми, 10 00:00:24,820 --> 00:00:28,420 а насправді повернути деякі з Уроки, витягнуті з нульовою тижня, 11 00:00:28,420 --> 00:00:31,910 де нагадаємо, ми представив це чудовисько. 12 00:00:31,910 --> 00:00:33,880 І запозичення натхнення того, щоб почати 13 00:00:33,880 --> 00:00:36,879 вирішити все витонченішими проблеми алгоритмічно. 14 00:00:36,879 --> 00:00:38,420 Але спочатку пару оголошень. 15 00:00:38,420 --> 00:00:42,020 Таким чином, одна, якщо ви хотіли б приєднатися до Співробітники та однокласники CS50 за ланчем 16 00:00:42,020 --> 00:00:44,670 в цю п'ятницю, і тут, і в Кембридж, і в Нью-Хейвені, 17 00:00:44,670 --> 00:00:48,060 будь ласка, відвідайте Курсу сайт, де URL може бути знайдений. 18 00:00:48,060 --> 00:00:50,390 Лекція в середу буде же не бути тут, в Сандерс. 19 00:00:50,390 --> 00:00:53,610 Це буде тільки онлайн, так налаштуватися на сайті CS50 на, в 20 00:00:53,610 --> 00:00:55,850 Чи тут в Кембриджі або Нью-Гейвен, а також. 21 00:00:55,850 --> 00:00:58,110 >> І тоді проблема встановити два вже у ваших руках. 22 00:00:58,110 --> 00:01:03,067 Якщо ви не пірнали в ще, дозвольте мені запропонувати сформульоване пропозицію сильно 23 00:01:03,067 --> 00:01:05,150 що особливо зараз, в проблема встановлює заздалегідь, 24 00:01:05,150 --> 00:01:08,669 Ви дійсно хочете, щоб почати зараз, якщо не плескатися трохи на вихідні або до 25 00:01:08,669 --> 00:01:10,710 коли вони вперше вийти на П'ятницях, тому що ви будете 26 00:01:10,710 --> 00:01:14,380 знайти, що вони не обов'язково отримувати більше або більш складним в 27 00:01:14,380 --> 00:01:14,950 SE. 28 00:01:14,950 --> 00:01:17,575 Я думаю, що ви знайдете, що в Взагалі, вони, як правило, приймати приблизно 29 00:01:17,575 --> 00:01:18,892 навколо стільки ж часу. 30 00:01:18,892 --> 00:01:20,850 Але це, звичайно, залежить на студента, і він 31 00:01:20,850 --> 00:01:22,880 залежить від менталітету з якою ви наближаєтеся до нього. 32 00:01:22,880 --> 00:01:24,910 Але незмінно, ви збираєтеся запустити проти якоїсь стіни, 33 00:01:24,910 --> 00:01:26,350 і ви збираєтеся вдарити якась помилка, і ви просто 34 00:01:26,350 --> 00:01:27,950 не буде в змозі отримати над ним в якийсь момент. 35 00:01:27,950 --> 00:01:31,380 І це дуже цінно, щоб мати можливість відійти, повернутися наступного дня, 36 00:01:31,380 --> 00:01:35,286 перейти до офісних годин, пост на CS50 Обговорити і т.п., насправді отримати розблокований. 37 00:01:35,286 --> 00:01:36,160 Так що майте це на увазі. 38 00:01:36,160 --> 00:01:40,830 Починаючи раннє, наскільки це можливо це найкраще, що ви можете зробити. 39 00:01:40,830 --> 00:01:44,160 Так от, де ми почали клас, за нульовою тижня. 40 00:01:44,160 --> 00:01:47,441 І ми можемо отримати добровольця тут, щоб допомогти мені знайти мікрофони? 41 00:01:47,441 --> 00:01:47,940 ДОБРЕ. 42 00:01:47,940 --> 00:01:48,900 Стоячи вже. 43 00:01:48,900 --> 00:01:50,080 Давай до. 44 00:01:50,080 --> 00:01:53,707 Вгадайте, що це, як це буде працювати. 45 00:01:53,707 --> 00:01:54,415 Як вас звати? 46 00:01:54,415 --> 00:01:55,570 АЛАН ESTRADA: Алан Естрада. 47 00:01:55,570 --> 00:01:56,778 Девід Дж Малан: Алан Естрада. 48 00:01:56,778 --> 00:01:57,910 Давай до. 49 00:01:57,910 --> 00:01:58,619 Приємно познайомитись. 50 00:01:58,619 --> 00:01:59,910 АЛАН ESTRADA: Приємно познайомитися. 51 00:01:59,910 --> 00:02:02,772 Девід Дж Малан: І ви були тут з нами в нульовому тижні, звичайно. 52 00:02:02,772 --> 00:02:03,028 АЛАН ESTRADA: я був. 53 00:02:03,028 --> 00:02:03,160 Я був. 54 00:02:03,160 --> 00:02:05,868 >> Девід Дж Малан: Так може ви йдете вперед і знайти для нас Майк Сміт, 55 00:02:05,868 --> 00:02:08,639 так швидко, як ви можете? 56 00:02:08,639 --> 00:02:10,639 Як швидко, як ви можете. 57 00:02:10,639 --> 00:02:13,756 Буквально розриваючи проблеми в половині, як вам потрібно. 58 00:02:13,756 --> 00:02:15,130 >> АЛАН ESTRADA: Хм. 59 00:02:15,130 --> 00:02:17,380 Девід Дж Малан: Буквально розриваючи проблему в два рази. 60 00:02:17,380 --> 00:02:20,210 61 00:02:20,210 --> 00:02:22,083 >> АЛАН ESTRADA: Ой. 62 00:02:22,083 --> 00:02:22,583 Мм. 63 00:02:22,583 --> 00:02:23,300 Дуже добре. 64 00:02:23,300 --> 00:02:23,700 >> Девід Дж Малан: ОК. 65 00:02:23,700 --> 00:02:24,200 Добре. 66 00:02:24,200 --> 00:02:24,701 Дякую. 67 00:02:24,701 --> 00:02:25,700 АЛАН ESTRADA: Дуже добре. 68 00:02:25,700 --> 00:02:26,210 ДОБРЕ. 69 00:02:26,210 --> 00:02:27,610 >> Девід Дж Малан: І тепер, Ви звів його 70 00:02:27,610 --> 00:02:29,320 до половини розміру проблеми. 71 00:02:29,320 --> 00:02:31,267 Тепер, ми до чверті. 72 00:02:31,267 --> 00:02:33,475 Ви звертаючи уваги на з якого боку ми тримаємо? 73 00:02:33,475 --> 00:02:34,405 >> [Сміється] 74 00:02:34,405 --> 00:02:35,970 >> АЛАН ESTRADA: Так, я think-- 75 00:02:35,970 --> 00:02:37,594 >> Девід Дж Малан: Який розділ ми в? 76 00:02:37,594 --> 00:02:39,150 АЛАН ESTRADA: Глушителі, так. 77 00:02:39,150 --> 00:02:39,941 >> Девід Дж Малан: ОК. 78 00:02:39,941 --> 00:02:42,810 Але Майк Сміт збирається щоб бути після Глушники. 79 00:02:42,810 --> 00:02:44,130 Так-- 80 00:02:44,130 --> 00:02:48,180 >> [Сміється] 81 00:02:48,180 --> 00:02:48,742 >> Добре. 82 00:02:48,742 --> 00:02:50,200 АЛАН ESTRADA: Де ми шукаємо? 83 00:02:50,200 --> 00:02:52,049 Девід Дж Малан: Майк Сміт. 84 00:02:52,049 --> 00:02:53,090 АЛАН ESTRADA: Майк Сміт. 85 00:02:53,090 --> 00:02:54,760 Девід Дж Малан: Тепер ми в хірургічне. 86 00:02:54,760 --> 00:02:57,840 Тепер лікарі. 87 00:02:57,840 --> 00:02:58,340 Now-- 88 00:02:58,340 --> 00:02:59,856 >> АЛАН ESTRADA: Let's- давайте йти з реальною. 89 00:02:59,856 --> 00:03:00,370 Нерухомість. 90 00:03:00,370 --> 00:03:00,970 >> Девід Дж Малан: Нерухомість. 91 00:03:00,970 --> 00:03:01,470 ДОБРЕ. 92 00:03:01,470 --> 00:03:03,700 Якщо вам потрібно реальне. 93 00:03:03,700 --> 00:03:05,250 Тепер, який шлях Майк Сміт? 94 00:03:05,250 --> 00:03:06,250 >> АЛАН ESTRADA: Таким чином. 95 00:03:06,250 --> 00:03:07,333 >> Девід Дж Малан: Яким чином? 96 00:03:07,333 --> 00:03:08,240 АЛАН ESTRADA: Зачекайте. 97 00:03:08,240 --> 00:03:08,790 M is-- правильно? 98 00:03:08,790 --> 00:03:09,110 Ми почали with-- 99 00:03:09,110 --> 00:03:10,090 >> Девід Дж Малан: Так. 100 00:03:10,090 --> 00:03:10,650 Вони залишили. 101 00:03:10,650 --> 00:03:11,430 Ваше право. 102 00:03:11,430 --> 00:03:11,710 >> АЛАН ESTRADA: Так. 103 00:03:11,710 --> 00:03:13,126 >> Девід Дж Малан: Так Майк тут. 104 00:03:13,126 --> 00:03:13,990 АЛАН ESTRADA: Що? 105 00:03:13,990 --> 00:03:14,665 >> [Сміється] 106 00:03:14,665 --> 00:03:17,365 107 00:03:17,365 --> 00:03:18,330 >> Поганий приклад, хлопці. 108 00:03:18,330 --> 00:03:18,830 Вибачте. 109 00:03:18,830 --> 00:03:21,610 Девід Дж Малан: Це навчить Ви вискочити з свого стільця. 110 00:03:21,610 --> 00:03:22,318 >> АЛАН ESTRADA: Ой. 111 00:03:22,318 --> 00:03:22,890 Ох. 112 00:03:22,890 --> 00:03:23,390 Я вам. 113 00:03:23,390 --> 00:03:24,670 Я вам. 114 00:03:24,670 --> 00:03:25,170 Ох. 115 00:03:25,170 --> 00:03:25,669 Ох. 116 00:03:25,669 --> 00:03:26,812 Це is-- ОК, я вам. 117 00:03:26,812 --> 00:03:27,520 Сміт прямо тут? 118 00:03:27,520 --> 00:03:28,894 >> Девід Дж Малан: Сміт, спасибі. 119 00:03:28,894 --> 00:03:30,535 Так що я буду тримати дивлячись Сміт? 120 00:03:30,535 --> 00:03:30,790 >> АЛАН ESTRADA: О, так. 121 00:03:30,790 --> 00:03:31,340 Ні-ні-ні. 122 00:03:31,340 --> 00:03:31,600 О ні. 123 00:03:31,600 --> 00:03:31,940 Це моє. 124 00:03:31,940 --> 00:03:32,580 >> Девід Дж Малан: О, ви отримали Сміт. 125 00:03:32,580 --> 00:03:33,415 ДОБРЕ. 126 00:03:33,415 --> 00:03:34,040 >> АЛАН ESTRADA: Так, я отримав Сміт прямо тут. 127 00:03:34,040 --> 00:03:34,700 Вибачте, хлопці. 128 00:03:34,700 --> 00:03:35,860 Я думав, ми Michael-- шукали Михайла. 129 00:03:35,860 --> 00:03:36,550 Вибачте. 130 00:03:36,550 --> 00:03:37,550 >> Девід Дж Малан: Це нормально. 131 00:03:37,550 --> 00:03:39,950 Гаразд, тепер ми в Paccini і сини. 132 00:03:39,950 --> 00:03:41,242 >> АЛАН ESTRADA: Paccini і сини. 133 00:03:41,242 --> 00:03:43,158 Девід Дж Малан: Тільки ви і я на цьому. 134 00:03:43,158 --> 00:03:44,050 ДОБРЕ. 135 00:03:44,050 --> 00:03:45,130 Як нас знайти Майк Сміт. 136 00:03:45,130 --> 00:03:45,830 Сміт. 137 00:03:45,830 --> 00:03:46,310 >> АЛАН ESTRADA: Сміт. 138 00:03:46,310 --> 00:03:46,750 >> Девід Дж Малан: Сміт. 139 00:03:46,750 --> 00:03:47,728 Ми в R для сміття. 140 00:03:47,728 --> 00:03:48,644 АЛАН ESTRADA: Сміття. 141 00:03:48,644 --> 00:03:50,096 Ох. 142 00:03:50,096 --> 00:03:52,480 Це займе якийсь час. 143 00:03:52,480 --> 00:03:54,340 >> [Сміється] 144 00:03:54,340 --> 00:03:55,804 145 00:03:55,804 --> 00:03:56,720 Девід Дж Малан: Взуття. 146 00:03:56,720 --> 00:03:58,080 Ми у взутті. 147 00:03:58,080 --> 00:04:00,210 >> АЛАН ESTRADA: Тепер ми gonna-- 148 00:04:00,210 --> 00:04:01,105 >> Девід Дж Малан: Ніцца. 149 00:04:01,105 --> 00:04:01,980 АЛАН ESTRADA: Which-- 150 00:04:01,980 --> 00:04:03,620 [Сміється] 151 00:04:03,620 --> 00:04:05,440 О, це здорово. 152 00:04:05,440 --> 00:04:06,910 [Сміється] 153 00:04:06,910 --> 00:04:08,380 154 00:04:08,380 --> 00:04:09,390 >> Девід Дж Малан: Це нормально. 155 00:04:09,390 --> 00:04:11,365 >> АЛАН ESTRADA: О, це добре. 156 00:04:11,365 --> 00:04:14,425 Я не думаю, що я збираюся є PSAT приятелів після цього. 157 00:04:14,425 --> 00:04:15,300 Девід Дж Малан: Добре. 158 00:04:15,300 --> 00:04:16,078 Спортивні. 159 00:04:16,078 --> 00:04:17,036 АЛАН ESTRADA: Спортивні. 160 00:04:17,036 --> 00:04:18,668 Хм, L, M, N, O, П. 161 00:04:18,668 --> 00:04:19,459 Девід Дж Малан: ОК. 162 00:04:19,459 --> 00:04:21,600 Так що давайте розірвати це навпіл. 163 00:04:21,600 --> 00:04:22,270 Все добре. 164 00:04:22,270 --> 00:04:25,606 На цьому закінчується погано в будь-якому випадку, тому що Майк Сміт не буде в жовтих сторінках. 165 00:04:25,606 --> 00:04:26,430 >> АЛАН ESTRADA: Ой. 166 00:04:26,430 --> 00:04:27,140 >> Девід Дж Малан: Ні, це нормально. 167 00:04:27,140 --> 00:04:28,930 Але давайте уявимо, як він на цій сторінці. 168 00:04:28,930 --> 00:04:33,260 Так що тепер, ви звели проблему вниз на одну сторінку, і ми знайшли Майка Сміта. 169 00:04:33,260 --> 00:04:35,180 >> [Радісної] 170 00:04:35,180 --> 00:04:35,757 171 00:04:35,757 --> 00:04:36,340 Добре, дякую. 172 00:04:36,340 --> 00:04:40,700 173 00:04:40,700 --> 00:04:41,200 ДОБРЕ. 174 00:04:41,200 --> 00:04:43,646 Це було незвично. 175 00:04:43,646 --> 00:04:45,954 Але це було ще швидше ніж лінійний пошук, 176 00:04:45,954 --> 00:04:47,870 де ми починаємо на початку книги, 177 00:04:47,870 --> 00:04:51,210 і ми рухаємося наш шлях зліва направо, в кінцевому підсумку, дивлячись на Майка Сміта. 178 00:04:51,210 --> 00:04:53,540 І так, якщо телефонна книга був, можливо, 1000 сторінок, 179 00:04:53,540 --> 00:04:56,300 може бути, це зайняло б нам 10 або близько того сторінок сльози. 180 00:04:56,300 --> 00:04:59,380 >> Але ви, можливо, використовувала торкнувся припущення 181 00:04:59,380 --> 00:05:03,602 у все це, що є що в телефонній книзі на заздалегідь було те, що? 182 00:05:03,602 --> 00:05:04,310 АУДИТОРІЯ: Сортувати. 183 00:05:04,310 --> 00:05:05,000 Девід Дж Малан: Це відсортовані. 184 00:05:05,000 --> 00:05:05,160 Вірно? 185 00:05:05,160 --> 00:05:07,909 Це відсортовані за алфавітом, тому що всі ці імена та номери 186 00:05:07,909 --> 00:05:11,230 упорядковано від А х до Z, і в алфавітному порядку між ними. 187 00:05:11,230 --> 00:05:13,100 Але сьогодні, ми тепер запитати питання, ну, 188 00:05:13,100 --> 00:05:16,170 як зробив Verizon або телефон Компанія отримати його в такому стані? 189 00:05:16,170 --> 00:05:19,560 >> Тому що одна справа використовувати Припущення, що, і тому 190 00:05:19,560 --> 00:05:22,570 вирішити проблему з Алгоритм більш ефективно. 191 00:05:22,570 --> 00:05:24,900 Але ми ніколи дійсно запитав нульовий тижня, ну, 192 00:05:24,900 --> 00:05:27,790 скільки це коштувало Verizon або хтось ще 193 00:05:27,790 --> 00:05:29,620 щоб отримати, що телефонну книгу в відсортованому порядку? 194 00:05:29,620 --> 00:05:29,780 >> Вірно? 195 00:05:29,780 --> 00:05:31,529 Це не має значення, якщо дивлячись Mike Smith 196 00:05:31,529 --> 00:05:35,190 супер швидкий, якщо вона приймає вас на рік сортувати сторінки спочатку. 197 00:05:35,190 --> 00:05:35,690 Вірно? 198 00:05:35,690 --> 00:05:38,620 Ви можете також просто просіяти через рандомізованому телефонній книзі, 199 00:05:38,620 --> 00:05:40,690 якщо це буде супер дорого для сортування. 200 00:05:40,690 --> 00:05:42,350 Так що, якщо ми можемо мати інший доброволець. 201 00:05:42,350 --> 00:05:46,350 Давайте дивитися тут візьмемо як ми might-- приходять на up-- як 202 00:05:46,350 --> 00:05:48,100 ми могли б йти про сортування них. 203 00:05:48,100 --> 00:05:51,990 >> І якщо насправді міг Йорданія приєднатися до нас тут, на сцені. 204 00:05:51,990 --> 00:05:55,100 Давай на мить. 205 00:05:55,100 --> 00:05:56,359 Як вас звати? 206 00:05:56,359 --> 00:05:57,150 Кароліна: Керолайн. 207 00:05:57,150 --> 00:05:58,691 Девід Дж Малан: Керолайн, давай до. 208 00:05:58,691 --> 00:06:02,070 І ви будете приєднався мною і Йорданії тут. 209 00:06:02,070 --> 00:06:03,800 Керолайн, спасибі. 210 00:06:03,800 --> 00:06:04,300 Добре. 211 00:06:04,300 --> 00:06:08,330 Отже, що ми маємо тут для Керолайн 26 сині книги 212 00:06:08,330 --> 00:06:10,747 що ФАС використовує для управління деякі випускні іспити. 213 00:06:10,747 --> 00:06:13,330 Вони стають важко знайти, але те, що ми зробили заздалегідь 214 00:06:13,330 --> 00:06:15,800 є те, що ми вклали чиєсь ім'я на передній кожен з них, 215 00:06:15,800 --> 00:06:18,133 але ми тримали його простим шляхом потім гасити повні імена. 216 00:06:18,133 --> 00:06:22,720 Таким чином, ми б поставити людину з ім'ям L, D, J, B, повністю від А до Z, 217 00:06:22,720 --> 00:06:24,090 але вони у випадковому порядку. 218 00:06:24,090 --> 00:06:26,890 І так, якби ви, кажу СВІЙ шлях через проблеми, як ви 219 00:06:26,890 --> 00:06:31,620 зробити це, ви можете йти вперед і сортувати їх для нас, від А до Я. 220 00:06:31,620 --> 00:06:34,070 >> АУДИТОРІЯ: ОК, так що я, як, середній. 221 00:06:34,070 --> 00:06:35,050 С починає. 222 00:06:35,050 --> 00:06:42,410 Б. Дж, перш ніж Л. В, В. 223 00:06:42,410 --> 00:06:45,140 >> Девід Дж Малан: Тримайте, що думав протягом однієї секунди. 224 00:06:45,140 --> 00:06:48,910 Бо інакше, це тільки цікавими для вас, мене і Йорданії. 225 00:06:48,910 --> 00:06:49,724 Там ми йдемо. 226 00:06:49,724 --> 00:06:50,640 АУДИТОРІЯ: [нерозбірливо]. 227 00:06:50,640 --> 00:06:57,299 Р. 228 00:06:57,299 --> 00:06:58,090 Девід Дж Малан: ОК. 229 00:06:58,090 --> 00:06:59,310 Що ви робите? 230 00:06:59,310 --> 00:07:01,730 >> Кароліна: М приходить після О. 231 00:07:01,730 --> 00:07:02,564 >> Девід Дж Малан: ОК. 232 00:07:02,564 --> 00:07:03,064 >> Кароліна: О. 233 00:07:03,064 --> 00:07:04,120 Девід Дж Малан: О, добре. 234 00:07:04,120 --> 00:07:04,970 >> Кароліна: Е. 235 00:07:04,970 --> 00:07:06,730 >> Девід Дж Малан: E, F. Так. 236 00:07:06,730 --> 00:07:07,620 >> Кароліна: T, U, V. 237 00:07:07,620 --> 00:07:10,689 >> Девід Дж Малан: V, T, U, V. Так-то воно Схоже, ви making-- продовжувати. 238 00:07:10,689 --> 00:07:12,730 Схоже, ви робите велика купа тут, 239 00:07:12,730 --> 00:07:13,910 і вид великої купи там. 240 00:07:13,910 --> 00:07:16,230 Таким чином, перша половина алфавіту, Друга половина алфавіту. 241 00:07:16,230 --> 00:07:16,460 ДОБРЕ. 242 00:07:16,460 --> 00:07:16,960 Добре. 243 00:07:16,960 --> 00:07:19,680 Вид поділу проблеми на дві частини. 244 00:07:19,680 --> 00:07:21,771 M, N, Х. Так. 245 00:07:21,771 --> 00:07:22,270 Кароліна: К. 246 00:07:22,270 --> 00:07:22,980 Девід Дж Малан: ОК. 247 00:07:22,980 --> 00:07:25,070 К. Отже, ви начебто вибору їх один за іншим, 248 00:07:25,070 --> 00:07:27,620 покласти його вліво або вправо, або Z збирається на підлозі. 249 00:07:27,620 --> 00:07:28,012 ДОБРЕ. 250 00:07:28,012 --> 00:07:29,190 >> Кароліна: Z збирається на підлозі. 251 00:07:29,190 --> 00:07:29,360 >> Девід Дж Малан: ОК. 252 00:07:29,360 --> 00:07:30,920 У збирається на підлозі. 253 00:07:30,920 --> 00:07:31,735 Тепер ми можемо поставити X. 254 00:07:31,735 --> 00:07:32,409 >> Кароліна: Г. 255 00:07:32,409 --> 00:07:33,700 Девід Дж Малан: G відбувається залишилося. 256 00:07:33,700 --> 00:07:36,017 S йде правильно. 257 00:07:36,017 --> 00:07:37,642 Гаразд, А пройшовши весь шлях вліво. 258 00:07:37,642 --> 00:07:38,790 >> Кароліна: A, B, C, D. 259 00:07:38,790 --> 00:07:39,873 >> Девід Дж Малан: Тепер, добре. 260 00:07:39,873 --> 00:07:43,260 У нас є A, B, C. Вт збирається там. 261 00:07:43,260 --> 00:07:45,566 Гаразд, Т. 262 00:07:45,566 --> 00:07:46,611 >> Кароліна: H, I, J. 263 00:07:46,611 --> 00:07:47,860 Девід Дж Малан: H, I, J. Добре. 264 00:07:47,860 --> 00:07:49,160 Кароліна: У центрі, я gonna-- 265 00:07:49,160 --> 00:07:50,000 Девід Дж Малан: ОК. 266 00:07:50,000 --> 00:07:52,375 Так що тепер, ми збираємося виду злиття цих різних паль. 267 00:07:52,375 --> 00:08:00,730 Таким чином, через С, тоді я бачу D, і Е, F і і G і Н, І. Ніцца. 268 00:08:00,730 --> 00:08:05,540 J, К. А потім, це купа з ніг на голову, але це нормально. 269 00:08:05,540 --> 00:08:06,040 Звичайно. 270 00:08:06,040 --> 00:08:07,240 Ми можемо скоротити деякі кути. 271 00:08:07,240 --> 00:08:07,950 ДОБРЕ. 272 00:08:07,950 --> 00:08:10,530 І тоді ми повинні W, X, Y, Z. 273 00:08:10,530 --> 00:08:11,250 >> Кароліна: Так. 274 00:08:11,250 --> 00:08:11,880 >> Девід Дж Малан: Відмінно. 275 00:08:11,880 --> 00:08:14,122 Таким чином, велике спасибі Керолайн для сортування них. 276 00:08:14,122 --> 00:08:15,030 >> [Радісної] 277 00:08:15,030 --> 00:08:17,287 >> Дякую. 278 00:08:17,287 --> 00:08:18,120 Велике спасибі. 279 00:08:18,120 --> 00:08:22,910 Так що тепер давайте на хвилину як Керолайн ходив, що 280 00:08:22,910 --> 00:08:26,040 і що саме ми змогли, метою яких, як ми 281 00:08:26,040 --> 00:08:28,409 змогли вирішити, що Проблема, коли ми були просто 282 00:08:28,409 --> 00:08:29,950 враховуючи цілий букет випадкових входів. 283 00:08:29,950 --> 00:08:31,610 >> Ну, схоже, є було небагато системи там? 284 00:08:31,610 --> 00:08:32,110 Право. 285 00:08:32,110 --> 00:08:34,495 Так раніше листів в алфавіті, вона 286 00:08:34,495 --> 00:08:37,120 був покласти ліворуч, а пізніх букви в алфавіті, 287 00:08:37,120 --> 00:08:38,270 вона була покласти в правий. 288 00:08:38,270 --> 00:08:40,500 І як тільки вона знайшла деякі проксимальних літери, ті, 289 00:08:40,500 --> 00:08:43,124 які йдуть поруч один з одним, вона вкладати їх в порядку. 290 00:08:43,124 --> 00:08:46,750 І таким чином, ми були свого роду ці маленькі купи відсортованих входів, що відбуваються. 291 00:08:46,750 --> 00:08:50,540 >> І так, що цілком як те, що більшість з нас люди будуть робити. 292 00:08:50,540 --> 00:08:53,530 Ми начебто просіяти через нього, і ми начебто є механізм. 293 00:08:53,530 --> 00:08:56,930 Але це може бути важко, щоб написати його вниз у формулі як такої. 294 00:08:56,930 --> 00:08:59,010 Він відчував себе трохи більш органічним, ніж це. 295 00:08:59,010 --> 00:09:02,560 Отже, давайте подивимося, якщо ми можемо в даний час межі Проблема з меншою кількістю входів. 296 00:09:02,560 --> 00:09:05,170 >> Замість 26, давайте зробити щось набагато менше 297 00:09:05,170 --> 00:09:09,890 з просто сказати, сім, за ці двері, так би мовити. 298 00:09:09,890 --> 00:09:11,300 Є тільки сьомій чисел? 299 00:09:11,300 --> 00:09:15,240 І якщо мета тепер в рука, щоб знайти значення, 300 00:09:15,240 --> 00:09:17,850 давайте подивимося, наскільки ефективно ми можемо йти про це. 301 00:09:17,850 --> 00:09:22,460 І давайте подивимося, якщо ми можемо в даний час почати застосовувати деякі цифри, 302 00:09:22,460 --> 00:09:26,310 або деякі формули, з якою, щоб описати ефективність нашої телефонній книзі 303 00:09:26,310 --> 00:09:31,060 Алгоритм, наш алгоритм іспит книги, і в більш загальному, пошуку інформації. 304 00:09:31,060 --> 00:09:34,770 >> Таким чином, для цього, дозвольте мені йти вперед, і на сенсорному екрані сюди, 305 00:09:34,770 --> 00:09:41,100 поставити веб-браузер, який має саме ці сім дверей. 306 00:09:41,100 --> 00:09:46,670 І якщо ми могли б отримати один добровільно прийти на тут, 307 00:09:46,670 --> 00:09:48,480 Я поклав ці ж двері тут. 308 00:09:48,480 --> 00:09:49,170 Швидкий громадських засадах. 309 00:09:49,170 --> 00:09:51,130 >> Це одно-- демо збираються до все швидше і швидше в даний час. 310 00:09:51,130 --> 00:09:51,600 Йдемо вниз. 311 00:09:51,600 --> 00:09:52,308 Як вас звати? 312 00:09:52,308 --> 00:09:53,040 Тревор: Тревор. 313 00:09:53,040 --> 00:09:53,998 >> Девід Дж Малан: Тревор? 314 00:09:53,998 --> 00:09:55,770 Гаразд, Тревор, давай вниз. 315 00:09:55,770 --> 00:09:59,212 Так Тревор добровільно тут, щоб зробити подібну проблему, але це 316 00:09:59,212 --> 00:10:02,170 вужчим за обсягом, і що відбувається щоб дозволити нам, щоб спробувати оформити в даний час 317 00:10:02,170 --> 00:10:03,970 процес сортування ці цифри. 318 00:10:03,970 --> 00:10:05,500 >> Так Тревор, приємно зустрітися з вами. 319 00:10:05,500 --> 00:10:08,720 Так от масив, так кажуть, список з семи дверей. 320 00:10:08,720 --> 00:10:10,327 Ідіть вперед і знайти нам номер 50. 321 00:10:10,327 --> 00:10:12,410 І потім, після того факту, розкажіть, як ви його знайшли. 322 00:10:12,410 --> 00:10:19,124 323 00:10:19,124 --> 00:10:20,040 Якщо be-- всі права. 324 00:10:20,040 --> 00:10:21,945 Так, це один тут? 325 00:10:21,945 --> 00:10:24,680 Ой-ой. 326 00:10:24,680 --> 00:10:25,560 ДОБРЕ. 327 00:10:25,560 --> 00:10:26,680 Ви натиснули, що один. 328 00:10:26,680 --> 00:10:28,690 Добре. 329 00:10:28,690 --> 00:10:29,780 >> І добре. 330 00:10:29,780 --> 00:10:30,970 Тепер ви натиснули цю. 331 00:10:30,970 --> 00:10:34,060 І дозвольте мені дати вам мікрофон, так що у вас є це в мить. 332 00:10:34,060 --> 00:10:37,000 Ідіть вперед і натисніть поруч, що ви маєте намір. 333 00:10:37,000 --> 00:10:39,812 Так добре. 334 00:10:39,812 --> 00:10:41,020 Тревор: Чи можу я повторно клацніть двері? 335 00:10:41,020 --> 00:10:42,620 Девід Дж Малан: Ні, ви не можете повторно клацніть. 336 00:10:42,620 --> 00:10:43,119 Тревор: ОК. 337 00:10:43,119 --> 00:10:43,974 Ось цей. 338 00:10:43,974 --> 00:10:45,640 Девід Дж Малан: Де ви хочете піти? 339 00:10:45,640 --> 00:10:46,410 Який? 340 00:10:46,410 --> 00:10:47,230 >> Тревор: Це одне. 341 00:10:47,230 --> 00:10:48,042 >> Девід Дж Малан: Ні 342 00:10:48,042 --> 00:10:48,450 >> Тревор: ОК. 343 00:10:48,450 --> 00:10:48,735 Ось цей. 344 00:10:48,735 --> 00:10:49,020 >> Девід Дж Малан: Так. 345 00:10:49,020 --> 00:10:49,700 Це було добре. 346 00:10:49,700 --> 00:10:50,380 Добре. 347 00:10:50,380 --> 00:10:53,900 Так що ж ваш алгоритм або Процедура для цього, Тревор? 348 00:10:53,900 --> 00:10:56,149 >> Тревор: Я тільки що пройшов через двері, поки я не знайшов 50. 349 00:10:56,149 --> 00:10:56,940 Девід Дж Малан: ОК. 350 00:10:56,940 --> 00:10:58,150 Відмінно алгоритм. 351 00:10:58,150 --> 00:10:59,540 Так що все в порядку. 352 00:10:59,540 --> 00:11:03,120 Тому що справді, якщо я відкрию що за цими двома іншими дверима, те, що 353 00:11:03,120 --> 00:11:06,954 ми знайдемо тут є те, що у нас є тільки випадковий вхід. 354 00:11:06,954 --> 00:11:08,870 Так що насправді, як було добре, як ви могли б отримати. 355 00:11:08,870 --> 00:11:12,509 І справді, ви отримали краще, ніж вичерпно пошуку весь масив, 356 00:11:12,509 --> 00:11:15,300 тому що це було б дійсно пощастило, якщо ви вдарив кількість 357 00:11:15,300 --> 00:11:16,604 50 в самий останній двері. 358 00:11:16,604 --> 00:11:18,520 Але що, якщо ми замість дав вам припущення. 359 00:11:18,520 --> 00:11:20,630 Припустимо, що я ніби все ці двері навколо, 360 00:11:20,630 --> 00:11:23,500 так що у вас є номера сортуються в цей раз, 361 00:11:23,500 --> 00:11:29,730 але цього разу він насправді different-- цей раз, 362 00:11:29,730 --> 00:11:32,640 це насправді упорядковано для вас. 363 00:11:32,640 --> 00:11:35,380 А тепер ставите боку полягає в хіт номер 50. 364 00:11:35,380 --> 00:11:36,090 >> Тревор: ОК. 365 00:11:36,090 --> 00:11:37,670 >> Девід Дж Малан: Що ваш алгоритм буде? 366 00:11:37,670 --> 00:11:39,628 >> Тревор: Ну, якщо це сортується, це або відбувається 367 00:11:39,628 --> 00:11:42,710 щоб be-- якщо великий, щоб за величиною, спаданням, це буде перший, 368 00:11:42,710 --> 00:11:44,751 або, якщо це навпаки, це буде останнім. 369 00:11:44,751 --> 00:11:48,897 Так що я просто натисніть цю двері, і Потім просто натисніть на останню двері. 370 00:11:48,897 --> 00:11:49,980 Девід Дж Малан: Відмінно. 371 00:11:49,980 --> 00:11:50,270 Добре. 372 00:11:50,270 --> 00:11:51,150 Таким чином, ми знайшли номер 50. 373 00:11:51,150 --> 00:11:52,970 Тому, як тільки ви знали, вони були відсортовані, ми 374 00:11:52,970 --> 00:11:55,040 змогли використати це припущення. 375 00:11:55,040 --> 00:11:57,040 Так що вони занадто багато, як приклад телефонної книги. 376 00:11:57,040 --> 00:11:59,540 Як тільки у вас є, навіть з невелика проблема, як це, 377 00:11:59,540 --> 00:12:02,380 Ваші входи попередньо відсортовані, ми можемо насправді знайти значення можливо 378 00:12:02,380 --> 00:12:03,130 більш ефективно. 379 00:12:03,130 --> 00:12:05,800 >> І я не кажу вам, якщо це було відсортовано мала до велика, або великого до малого, 380 00:12:05,800 --> 00:12:08,080 і так було дуже розумно щоб почати на одному кінці або інший 381 00:12:08,080 --> 00:12:09,750 насправді знайти, що цільове значення. 382 00:12:09,750 --> 00:12:11,400 Так що спасибі Тревору, а також. 383 00:12:11,400 --> 00:12:13,260 І я propose-- красиво зроблено. 384 00:12:13,260 --> 00:12:16,960 У нас є невеликий кліп, насправді, що є одним з наших улюблених моментів у CS50, 385 00:12:16,960 --> 00:12:19,700 в результаті чого іноді ці демки не зовсім за планом. 386 00:12:19,700 --> 00:12:22,050 І справді зараз я під'їхав неправильний інтерфейс 387 00:12:22,050 --> 00:12:23,508 з якою використовувати сенсорний екран. 388 00:12:23,508 --> 00:12:24,660 Так це була моя вина є. 389 00:12:24,660 --> 00:12:26,600 >> Так що це буде зробити для кліп в наступному році, як 390 00:12:26,600 --> 00:12:28,570 чому я був натиснувши на моєму власному екрані. 391 00:12:28,570 --> 00:12:31,390 Але давайте поглянемо на те, що сталося торік 392 00:12:31,390 --> 00:12:34,770 з Джеєм, який придумав, багато як Тревор тут, добровільно, 393 00:12:34,770 --> 00:12:39,380 і в цьому короткий кліп, ви побачите як ця ж демонстраційний не зовсім 394 00:12:39,380 --> 00:12:41,074 виявити ті ж уроки, витягнуті. 395 00:12:41,074 --> 00:12:41,740 [ВІДТВОРЕННЯ ВІДЕО] 396 00:12:41,740 --> 00:12:45,360 -Все Я хочу, щоб ви зараз зробити, це знайти для мене, і для нас, 397 00:12:45,360 --> 00:12:51,674 дійсно, число 50 один крок за один раз. 398 00:12:51,674 --> 00:12:52,450 >> -Кількість 50? 399 00:12:52,450 --> 00:12:53,190 >> -Кількість 50. 400 00:12:53,190 --> 00:12:55,356 І ви можете виявити те, що За кожним з цих дверей 401 00:12:55,356 --> 00:12:58,540 просто торкаючись його пальцем. 402 00:12:58,540 --> 00:13:00,910 Блін. 403 00:13:00,910 --> 00:13:02,870 >> [Сміється] 404 00:13:02,870 --> 00:13:03,806 >> [КІНЕЦЬ ПЕРЕГЛЯДУ] 405 00:13:03,806 --> 00:13:05,430 Девід Дж Малан: Так що пішли дуже добре. 406 00:13:05,430 --> 00:13:06,796 Ті були несортовані двері. 407 00:13:06,796 --> 00:13:08,670 І Джей, звичайно, знайти все це занадто швидко. 408 00:13:08,670 --> 00:13:12,910 Тревор зробив набагато кращу роботу в термінах доступний момент, 409 00:13:12,910 --> 00:13:15,850 так би мовити, в цьому році в займає більше часу, щоб знайти його. 410 00:13:15,850 --> 00:13:17,950 Звичайно, тоді ми дали Джей другий шанс, 411 00:13:17,950 --> 00:13:20,320 в результаті чого ми відсортували двері, як ми це робили для Тревора, 412 00:13:20,320 --> 00:13:22,300 і Тревор зробив супер добре в цей раз. 413 00:13:22,300 --> 00:13:26,124 Але Джей зробив це в два рази швидше. 414 00:13:26,124 --> 00:13:26,790 [ВІДТВОРЕННЯ ВІДЕО] 415 00:13:26,790 --> 00:13:29,650 -The Метою тепер є також знайти нам номер 50, 416 00:13:29,650 --> 00:13:33,030 але зробити це алгоритмічно, і розкажіть нам, як ви збираєтеся про це. 417 00:13:33,030 --> 00:13:33,660 >> -ДОБРЕ. 418 00:13:33,660 --> 00:13:35,604 >> -А Якщо ви знайдете його, ви тримаєте кіно. 419 00:13:35,604 --> 00:13:37,228 Якщо ви не знайдете його, ви дати його назад. 420 00:13:37,228 --> 00:13:38,044 >> -Man. 421 00:13:38,044 --> 00:13:38,860 >> -Ой! 422 00:13:38,860 --> 00:13:40,800 >> - [Нерозбірливо] ОК. 423 00:13:40,800 --> 00:13:46,236 Так що я збираюся перевірити кінці спочатку визначити, якщо there's-- О. 424 00:13:46,236 --> 00:13:48,646 >> [Оплески] 425 00:13:48,646 --> 00:13:53,948 426 00:13:53,948 --> 00:13:55,729 >> [КІНЕЦЬ ПЕРЕГЛЯДУ] 427 00:13:55,729 --> 00:13:56,520 Девід Дж Малан: ОК. 428 00:13:56,520 --> 00:13:59,760 Так сортування двері ясно призводить до більшої ефективності. 429 00:13:59,760 --> 00:14:01,680 І так, в два рази швидше це те, що я мав на увазі там. 430 00:14:01,680 --> 00:14:03,270 І так Джей пощастило обидва рази. 431 00:14:03,270 --> 00:14:06,685 І він також пощастило в минулому, що рік, я замовив кілька Blu-Ray дисків 432 00:14:06,685 --> 00:14:07,560 насправді видають. 433 00:14:07,560 --> 00:14:09,768 Мені шкода, цього року ми не мають те ж саме, Тревор. 434 00:14:09,768 --> 00:14:11,540 Але все-таки краще було кілька років тому. 435 00:14:11,540 --> 00:14:14,820 І деякі з вас, можливо, знаєте, це хлопець, Шон, який, коли він був у CS50, 436 00:14:14,820 --> 00:14:17,780 був кинутий виклик з точним Та ж проблема, хоча і в SD, 437 00:14:17,780 --> 00:14:19,360 як ви скоро побачите, тому в день. 438 00:14:19,360 --> 00:14:22,622 І ви побачите, що не тільки зробив він займе трохи більше часу, ніж Джей, 439 00:14:22,622 --> 00:14:25,580 трохи більше, ніж Тревор, це було насправді це прекрасна можливість 440 00:14:25,580 --> 00:14:29,820 займатися майже всі в Натовп ла Ціна праворуч, заохочуючи 441 00:14:29,820 --> 00:14:31,889 йому знайти номер, ми шукали. 442 00:14:31,889 --> 00:14:32,930 Давайте. взяти швидкий погляд. 443 00:14:32,930 --> 00:14:33,320 >> [ВІДТВОРЕННЯ ВІДЕО] 444 00:14:33,320 --> 00:14:33,820 >> -ДОБРЕ. 445 00:14:33,820 --> 00:14:36,680 Так ваше завдання тут, Шон, полягає в наступному. 446 00:14:36,680 --> 00:14:40,860 Я сховав за ними Двері число сім. 447 00:14:40,860 --> 00:14:45,120 Але захований в деяких з цих дверей а також інші негативні числа. 448 00:14:45,120 --> 00:14:47,500 І ваша мета, щоб думати цієї верхньому рядку чисел 449 00:14:47,500 --> 00:14:50,390 як тільки масив, або просто Послідовність папірців 450 00:14:50,390 --> 00:14:51,510 з номерами позаду них. 451 00:14:51,510 --> 00:14:55,540 І ваша мета, використовуючи тільки верхню Масив тут, знайти мені номер сім. 452 00:14:55,540 --> 00:14:58,570 І ми потім збирається критикувати як ви йдете про робити це. 453 00:14:58,570 --> 00:14:59,070 -Добре. 454 00:14:59,070 --> 00:15:00,850 -Знайти Нам номер сім, будь ласка. 455 00:15:00,850 --> 00:15:10,500 456 00:15:10,500 --> 00:15:11,000 Немає. 457 00:15:11,000 --> 00:15:15,050 458 00:15:15,050 --> 00:15:18,550 П'ять, 19, 13. 459 00:15:18,550 --> 00:15:22,240 460 00:15:22,240 --> 00:15:24,770 >> [Сміється] 461 00:15:24,770 --> 00:15:25,910 >> Це не питання з підступом. 462 00:15:25,910 --> 00:15:29,410 463 00:15:29,410 --> 00:15:29,910 Один. 464 00:15:29,910 --> 00:15:33,218 465 00:15:33,218 --> 00:15:34,695 >> [Сміється] 466 00:15:34,695 --> 00:15:37,861 На даний момент, ваш рахунок не надто добре, так що ви могли б також продовжувати. 467 00:15:37,861 --> 00:15:40,610 468 00:15:40,610 --> 00:15:41,110 Три. 469 00:15:41,110 --> 00:15:43,890 470 00:15:43,890 --> 00:15:45,378 >> [Сміється] 471 00:15:45,378 --> 00:15:46,370 472 00:15:46,370 --> 00:15:47,774 >> Продовжуй. 473 00:15:47,774 --> 00:15:50,690 Чесно кажучи, я не можу допомогти, але цікаво, те, що ви навіть думати про, so-- 474 00:15:50,690 --> 00:15:51,959 >> [Сміється] 475 00:15:51,959 --> 00:15:53,229 476 00:15:53,229 --> 00:15:55,020 Тільки верхній ряд, так у вас є три зліва. 477 00:15:55,020 --> 00:15:56,200 Так що знайдіть мені сім. 478 00:15:56,200 --> 00:15:59,700 479 00:15:59,700 --> 00:16:02,167 >> [Сміється] 480 00:16:02,167 --> 00:16:14,870 481 00:16:14,870 --> 00:16:15,370 17. 482 00:16:15,370 --> 00:16:25,675 483 00:16:25,675 --> 00:16:26,946 Сім. 484 00:16:26,946 --> 00:16:28,780 >> [Оплески] 485 00:16:28,780 --> 00:16:29,426 >> Добре. 486 00:16:29,426 --> 00:16:30,360 >> [КІНЕЦЬ ПЕРЕГЛЯДУ] 487 00:16:30,360 --> 00:16:31,840 >> Девід Дж Малан: Таким чином, ми могли дивитися це протягом усього дня. 488 00:16:31,840 --> 00:16:34,090 І, звичайно, деякі з демо в цьому році, можливо, 489 00:16:34,090 --> 00:16:36,330 Тепер буде в кінцевому підсумку в наступний відео року, а також. 490 00:16:36,330 --> 00:16:39,040 Так що тепер давайте насправді зосередитися на алгоритмах 491 00:16:39,040 --> 00:16:42,140 тут, щоб побачити, якщо ми не можемо Тепер починають формалізувати 492 00:16:42,140 --> 00:16:46,650 як ми можемо йти про отримання наших даних в цьому стані, що це сортується, 493 00:16:46,650 --> 00:16:50,054 так що в кінцевому рахунку, ми можемо насправді шукати його більш ефективно. 494 00:16:50,054 --> 00:16:52,470 І хоча ми збираємося використовувати досить невеликі набори даних, 495 00:16:52,470 --> 00:16:54,511 як ми восьмій чисел Тобто тут, на борту, 496 00:16:54,511 --> 00:16:58,230 в кінцевому рахунку, ці ж ідеї можна застосувати 1000 входів, мільйон входів, 497 00:16:58,230 --> 00:17:02,100 4 млрд входи, тому що алгоритми будуть принципово те ж саме. 498 00:17:02,100 --> 00:17:05,359 >> І таким чином, це наш останній можливість для добровольців сьогодні, 499 00:17:05,359 --> 00:17:09,790 але, мабуть, найбільш активна участь одного, для яких ми повинні восьмій добровольців 500 00:17:09,790 --> 00:17:12,960 прийти і ходити з нами через Процес сортування, що скоро 501 00:17:12,960 --> 00:17:15,212 бути на цих музику варто тут. 502 00:17:15,212 --> 00:17:16,170 Дозвольте мені почати знову тут. 503 00:17:16,170 --> 00:17:19,692 >> Таким чином, одна в turquoise-- зелений це? 504 00:17:19,692 --> 00:17:21,130 Ви вчиненні? 505 00:17:21,130 --> 00:17:21,630 Два. 506 00:17:21,630 --> 00:17:23,069 Йдемо вниз. 507 00:17:23,069 --> 00:17:23,569 ДОБРЕ. 508 00:17:23,569 --> 00:17:24,420 Три. 509 00:17:24,420 --> 00:17:25,400 Чотири. 510 00:17:25,400 --> 00:17:27,247 Нехай me-- ОК, п'ять. 511 00:17:27,247 --> 00:17:28,830 Ви висувається вашим другом. 512 00:17:28,830 --> 00:17:31,340 Шість, сім, вісім. 513 00:17:31,340 --> 00:17:32,130 Давай до. 514 00:17:32,130 --> 00:17:32,630 Добре. 515 00:17:32,630 --> 00:17:33,190 Дуже дякую. 516 00:17:33,190 --> 00:17:33,689 Давай до. 517 00:17:33,689 --> 00:17:34,790 Давай до. 518 00:17:34,790 --> 00:17:35,330 >> Добре. 519 00:17:35,330 --> 00:17:38,890 Так що у нас є here-- і це є одним з найбільш незручних ті, 520 00:17:38,890 --> 00:17:42,390 так як це вимагає, щоб ви гумор мені протягом тільки трохи часу. 521 00:17:42,390 --> 00:17:43,442 Ви повинні бути номер один. 522 00:17:43,442 --> 00:17:44,150 Як вас звати? 523 00:17:44,150 --> 00:17:44,610 >> АННАН: Аннан. 524 00:17:44,610 --> 00:17:45,526 >> Девід Дж Малан: Аннан. 525 00:17:45,526 --> 00:17:46,092 Девід. 526 00:17:46,092 --> 00:17:46,800 Як вас звати? 527 00:17:46,800 --> 00:17:47,140 >> ЙОСИП: Джозеф. 528 00:17:47,140 --> 00:17:49,190 >> Девід Дж Малан: Йосип, Ви номер два. 529 00:17:49,190 --> 00:17:52,260 >> Серена: Серена, номер три. 530 00:17:52,260 --> 00:17:53,722 Стефан, номер чотири. 531 00:17:53,722 --> 00:17:54,430 СИНТИЯ: Синтія. 532 00:17:54,430 --> 00:17:57,548 Девід Дж Малан: Синтія, номер п'ять. 533 00:17:57,548 --> 00:17:58,452 [Нерозбірливо] 534 00:17:58,452 --> 00:17:59,618 Девід Дж Малан: [нерозбірливо]. 535 00:17:59,618 --> 00:18:00,391 Девід, номер шість. 536 00:18:00,391 --> 00:18:00,890 Метт: Метт. 537 00:18:00,890 --> 00:18:02,160 Девід Дж Малан: кількість Метта сім. 538 00:18:02,160 --> 00:18:02,850 І що ж? 539 00:18:02,850 --> 00:18:03,210 >> WAVERLY: Уеверлі. 540 00:18:03,210 --> 00:18:04,470 >> Девід Дж Малан: Уеверлі, номер вісім. 541 00:18:04,470 --> 00:18:04,970 Добре. 542 00:18:04,970 --> 00:18:06,510 Якщо ви could-- вигуки. 543 00:18:06,510 --> 00:18:08,820 Якщо ви все, як ваш Перше завдання, є 544 00:18:08,820 --> 00:18:10,820 восьмій пюпітри тут перед аудиторією. 545 00:18:10,820 --> 00:18:14,200 Якщо б ви могли помістити свої номери на Ці музичні виступає таким чином, 546 00:18:14,200 --> 00:18:16,560 що вони шикуються з ті ж номери на дошці. 547 00:18:16,560 --> 00:18:19,560 Так що самі виглядати по покласти ваші номери на цих музиці 548 00:18:19,560 --> 00:18:21,960 варто тут. 549 00:18:21,960 --> 00:18:25,980 Відмінно досі. 550 00:18:25,980 --> 00:18:26,600 >> Відмінно. 551 00:18:26,600 --> 00:18:26,890 ДОБРЕ. 552 00:18:26,890 --> 00:18:29,556 Так що тепер, ми збираємося запитати Питання в кілька різних способів. 553 00:18:29,556 --> 00:18:31,610 Як ми можемо йти про сортування ці люди тут? 554 00:18:31,610 --> 00:18:34,500 Тому що у нас було кілька підходів раніше, в результаті чого ми були 555 00:18:34,500 --> 00:18:36,360 вигляд робить дві різні відра. 556 00:18:36,360 --> 00:18:38,842 А потім ми, як правило, пірсингом речі разом. 557 00:18:38,842 --> 00:18:41,050 Як тільки ми побачили дві цифри який належав разом, 558 00:18:41,050 --> 00:18:41,975 покласти їх разом. 559 00:18:41,975 --> 00:18:43,350 Два листи, які належать разом. 560 00:18:43,350 --> 00:18:45,058 >> Але давайте подивимося, якщо ми не може оформити це, 561 00:18:45,058 --> 00:18:48,044 так що в кінцевому підсумку ми повинні деякі псевдо-код буде, 562 00:18:48,044 --> 00:18:49,710 за допомогою якого можна вирішити ці проблеми. 563 00:18:49,710 --> 00:18:51,870 Так що тепер, я дивився на ці цифри тут. 564 00:18:51,870 --> 00:18:55,030 І я бачу цілу купу помилок. 565 00:18:55,030 --> 00:18:57,750 У кінцевому рахунку, я хочу один на вліво і вісім на правій. 566 00:18:57,750 --> 00:19:00,650 >> І тому я, дивлячись на ці два, чотири і два. 567 00:19:00,650 --> 00:19:02,930 І в чому проблема, очевидно ,? 568 00:19:02,930 --> 00:19:04,261 Так. 569 00:19:04,261 --> 00:19:04,760 Так. 570 00:19:04,760 --> 00:19:07,160 Два явно йде перед чотирьох, так що ви знаєте, що? 571 00:19:07,160 --> 00:19:10,210 Дозвольте мені спочатку взяти жодній підхід, якщо ви будете, як і проблема 572 00:19:10,210 --> 00:19:13,790 встановити одно-- якщо ви пам'ятаєте з Стандартна редакція завдання один набір, 573 00:19:13,790 --> 00:19:16,820 де я тільки локально вирішити проблему що прямо тут переді мною 574 00:19:16,820 --> 00:19:17,690 і побачити, де вона веде мене. 575 00:19:17,690 --> 00:19:17,870 >> ДОБРЕ. 576 00:19:17,870 --> 00:19:20,161 Так два і чотири, дозвольте мені перейти вперед і просто поміняти вам два. 577 00:19:20,161 --> 00:19:22,400 Якщо ви можете фізично перемістити самі і ваша газета, 578 00:19:22,400 --> 00:19:25,040 Я, здається, отримали перерахувати в кращому стані. 579 00:19:25,040 --> 00:19:26,330 >> Тепер, вони гарні. 580 00:19:26,330 --> 00:19:28,480 Я збираюся рухатися далі, чотирьох і шести, виглядає добре. 581 00:19:28,480 --> 00:19:29,110 Не проблема. 582 00:19:29,110 --> 00:19:30,440 Шість і вісім, ОК. 583 00:19:30,440 --> 00:19:31,860 Вісім і один, ще одна проблема. 584 00:19:31,860 --> 00:19:34,750 Бо правда про вісім і однієї? 585 00:19:34,750 --> 00:19:36,990 Один приходить до восьми, і так, що ми повинні робити? 586 00:19:36,990 --> 00:19:38,090 Давайте поміняти ці два. 587 00:19:38,090 --> 00:19:39,316 Один і вісім. 588 00:19:39,316 --> 00:19:40,690 А тепер, я збираюся продовжувати. 589 00:19:40,690 --> 00:19:42,030 Я збираюся продовжувати дивитися вперед. 590 00:19:42,030 --> 00:19:42,840 І давайте подивимося, що станеться. 591 00:19:42,840 --> 00:19:44,680 Вісім і три, з Звичайно, в порядку. 592 00:19:44,680 --> 00:19:45,815 Давайте своп. 593 00:19:45,815 --> 00:19:46,940 Вісім і сім, звичайно. 594 00:19:46,940 --> 00:19:47,481 Вийшов з ладу. 595 00:19:47,481 --> 00:19:48,280 Давайте своп. 596 00:19:48,280 --> 00:19:49,940 Вісім років і п'ять, звичайно, давайте підкачки. 597 00:19:49,940 --> 00:19:50,560 Добре. 598 00:19:50,560 --> 00:19:51,880 Список сортується. 599 00:19:51,880 --> 00:19:53,060 так? 600 00:19:53,060 --> 00:19:54,280 >> ОК, очевидно, немає. 601 00:19:54,280 --> 00:19:55,860 Але це трохи краще, вірно? 602 00:19:55,860 --> 00:19:57,270 Тому що повідомлення, що сталося. 603 00:19:57,270 --> 00:20:01,749 Кожен раз, коли ми провели обмін, менше Кількість і тип проціджують, що шлях, 604 00:20:01,749 --> 00:20:03,790 і більше число перколюють цей шлях, або ми будемо 605 00:20:03,790 --> 00:20:06,880 почати говорити пропускають до вліво або барботируют вправо. 606 00:20:06,880 --> 00:20:10,080 >> Тепер, це не достатньо, тому що в кращому випадку число може 607 00:20:10,080 --> 00:20:11,990 перейшли одне місце вперед, або в гіршому випадку, 608 00:20:11,990 --> 00:20:13,880 ряд, можливо, переїхав на одну позицію далі. 609 00:20:13,880 --> 00:20:16,369 Таким чином, ви знаєте, що цей вид з працював дуже добре дотепер. 610 00:20:16,369 --> 00:20:17,410 Дозвольте мені спробувати ще раз. 611 00:20:17,410 --> 00:20:18,880 Два і чотири, вони ОК. 612 00:20:18,880 --> 00:20:20,180 Чотири і шість, вони ОК. 613 00:20:20,180 --> 00:20:21,790 Шість і один, вийшов з ладу. 614 00:20:21,790 --> 00:20:23,007 Отже, давайте поміняти вам два. 615 00:20:23,007 --> 00:20:25,840 А тепер зверніть увагу, що проблема-х починають отримувати трохи краще знову. 616 00:20:25,840 --> 00:20:27,006 Шість і три, вийшов з ладу. 617 00:20:27,006 --> 00:20:28,100 Давайте міняти вас два. 618 00:20:28,100 --> 00:20:29,730 Шість і сім, ви добре. 619 00:20:29,730 --> 00:20:32,230 Сім і п'ять, звичайно, в порядку. 620 00:20:32,230 --> 00:20:33,920 Сім і вісім, в порядку. 621 00:20:33,920 --> 00:20:36,470 А тепер, я, можливо, буде потрібно зробити це кілька разів. 622 00:20:36,470 --> 00:20:39,830 І справді, думаю, для себе можливо, скільки разів максимально 623 00:20:39,830 --> 00:20:41,330 може я повинен ходити взад і вперед? 624 00:20:41,330 --> 00:20:42,390 >> Ми повернемося до цього. 625 00:20:42,390 --> 00:20:43,700 Так два і чотири раніше ОК. 626 00:20:43,700 --> 00:20:44,940 Чотири і один, Ні. 627 00:20:44,940 --> 00:20:45,747 Отже, давайте своп. 628 00:20:45,747 --> 00:20:47,830 І знову, зверніть увагу, візуально один з бульбашок вид 629 00:20:47,830 --> 00:20:49,163 ліворуч, де він повинен бути. 630 00:20:49,163 --> 00:20:50,010 Чотири і три заміни. 631 00:20:50,010 --> 00:20:51,330 Чотири і шість. 632 00:20:51,330 --> 00:20:53,100 Шість і п'ять підкачки. 633 00:20:53,100 --> 00:20:53,959 Шість і сім. 634 00:20:53,959 --> 00:20:55,000 Сім і вісім хороші. 635 00:20:55,000 --> 00:20:55,500 >> Добре. 636 00:20:55,500 --> 00:20:58,460 Ми отримуємо ще краще. 637 00:20:58,460 --> 00:20:59,130 Отже, давайте подивимося. 638 00:20:59,130 --> 00:21:00,940 Тепер у нас є два і один. 639 00:21:00,940 --> 00:21:02,520 Звичайно, поміняти. 640 00:21:02,520 --> 00:21:07,520 Два і три, три і чотири, чотири і п'ять, шість і сім, сім і восьмій. 641 00:21:07,520 --> 00:21:08,020 Добре. 642 00:21:08,020 --> 00:21:08,730 І ви знаєте, що? 643 00:21:08,730 --> 00:21:11,190 Тому що я зробив одну зміну є, дозвольте мені зробити одну перевірку осудності. 644 00:21:11,190 --> 00:21:13,023 Дозвольте мені пройти весь шлях повернутися до початку. 645 00:21:13,023 --> 00:21:13,680 ДОБРЕ. 646 00:21:13,680 --> 00:21:14,750 Один з них, two-- да, бачите? 647 00:21:14,750 --> 00:21:15,870 Щось було не так. 648 00:21:15,870 --> 00:21:18,420 Три, чотири, п'ять, шість, сім, вісім. 649 00:21:18,420 --> 00:21:21,920 І в цьому останньому проході, є ви можете прямо зараз з моїм 650 00:21:21,920 --> 00:21:23,830 стверджуючи, що це сортується? 651 00:21:23,830 --> 00:21:24,330 ДОБРЕ. 652 00:21:24,330 --> 00:21:25,880 Візуально, це абсолютно вірно. 653 00:21:25,880 --> 00:21:28,410 Але функціонально, ніж так і просто так 654 00:21:28,410 --> 00:21:31,870 в цьому останньому проході, що дозволяє щоб підтвердити, що цей список дійсно 655 00:21:31,870 --> 00:21:32,660 відсортовано? 656 00:21:32,660 --> 00:21:34,477 >> Що я робити або не робити цього останнього пасу? 657 00:21:34,477 --> 00:21:35,810 АУДИТОРІЯ: Там не було ніяких змін. 658 00:21:35,810 --> 00:21:36,120 Девід Дж Малан: Вибачте? 659 00:21:36,120 --> 00:21:37,070 АУДИТОРІЯ: Немає змін. 660 00:21:37,070 --> 00:21:38,653 Девід Дж Малан: Там не було ніяких змін. 661 00:21:38,653 --> 00:21:41,947 Так що було б нерозумно з мого боку зробити це знову той же алгоритм 662 00:21:41,947 --> 00:21:43,780 якщо я не зробити будь зміни в перший раз. 663 00:21:43,780 --> 00:21:45,160 І держава не змінилася. 664 00:21:45,160 --> 00:21:47,576 Звичайно, я не збираюся робити будь-яких змін вдруге. 665 00:21:47,576 --> 00:21:49,820 І так, це тепер у безпеці сказати, список відсортований. 666 00:21:49,820 --> 00:21:52,069 >> І справді, це зараз те, що ми будемо, як правило 667 00:21:52,069 --> 00:21:56,900 Виклик бульбашкового сортування, в результаті чого попарно, вам виправити помилки знову, 668 00:21:56,900 --> 00:22:00,210 і знову, і знову, і вам тримати вперед і назад, 669 00:22:00,210 --> 00:22:03,370 ні і назад і вперед, поки ви не роблять такі свопи, на яких точка 670 00:22:03,370 --> 00:22:07,089 Ви можете бути впевнені, що, так, я закінчив фіксації всіх помилок. 671 00:22:07,089 --> 00:22:08,630 Давайте скидання і спробувати інший підхід. 672 00:22:08,630 --> 00:22:11,590 Якщо ви, хлопці, могли б повернутися в замовлення ви були хвилину тому, 673 00:22:11,590 --> 00:22:13,780 який виглядав, як це. 674 00:22:13,780 --> 00:22:17,640 Тепер, давайте розглянемо підхід, трохи більше, як іспит книги, 675 00:22:17,640 --> 00:22:21,122 в результаті чого ми були постійно вибравши букву алфавіту 676 00:22:21,122 --> 00:22:22,830 що ми якось хотів щоб мати справу з іншою. 677 00:22:22,830 --> 00:22:26,420 Може бути, це був високий лист, як А, або низької букви Z. 678 00:22:26,420 --> 00:22:28,170 >> Таким чином, кожен повернувся цього порядку. 679 00:22:28,170 --> 00:22:29,800 А тепер дозвольте мені зробити це. 680 00:22:29,800 --> 00:22:34,880 Давайте подивимося, я знаю, що є вісім цифр тут. 681 00:22:34,880 --> 00:22:37,410 Я збираюся йти вперед і просто свідомо вибрати 682 00:22:37,410 --> 00:22:38,520 найменші елементи. 683 00:22:38,520 --> 00:22:38,760 Вірно? 684 00:22:38,760 --> 00:22:39,801 Це, здається, інтуїтивно теж. 685 00:22:39,801 --> 00:22:42,560 Чому я не можу знайти найменший елемент, покласти його, де вона належить, 686 00:22:42,560 --> 00:22:45,280 а потім отримати наступний найменший елемент, поставити це, де це належить, і тільки повторити. 687 00:22:45,280 --> 00:22:46,820 >> Тому що інтуїтивно, який повинен працювати теж. 688 00:22:46,820 --> 00:22:48,441 Так чотирьох, це досить мале число. 689 00:22:48,441 --> 00:22:49,940 Я буду пам'ятати, де це. 690 00:22:49,940 --> 00:22:50,523 Почекай хвилинку. 691 00:22:50,523 --> 00:22:51,577 Два менше. 692 00:22:51,577 --> 00:22:53,910 Дозвольте мені тепер згадайте, коли два є, і забути про чотирьох. 693 00:22:53,910 --> 00:22:55,050 Ми будемо мати справу з цим пізніше. 694 00:22:55,050 --> 00:22:56,460 Шість, мені це не цікаво. 695 00:22:56,460 --> 00:22:57,810 Вісім, я не зацікавлений в. 696 00:22:57,810 --> 00:22:59,780 Один мій новий мале число. 697 00:22:59,780 --> 00:23:01,470 Так що я збираюся згадати, де ти є. 698 00:23:01,470 --> 00:23:02,534 Три, не цікавить. 699 00:23:02,534 --> 00:23:03,450 Сім, не цікавить. 700 00:23:03,450 --> 00:23:04,530 П'ять, не цікавить. 701 00:23:04,530 --> 00:23:07,390 >> Так, не падаючи етап у цьому році, 702 00:23:07,390 --> 00:23:09,890 Я збираюся захопити кількість одно-- і те, що знову ваше ім'я? 703 00:23:09,890 --> 00:23:10,150 >> АННАН: Аннан. 704 00:23:10,150 --> 00:23:11,220 >> Девід Дж Малан: Аннан. 705 00:23:11,220 --> 00:23:13,540 І якщо б ви могли приєднатися до мене в початок списку, 706 00:23:13,540 --> 00:23:14,870 давайте вам, де ви належите. 707 00:23:14,870 --> 00:23:16,080 Unfortunately-- що ваше ім'я? 708 00:23:16,080 --> 00:23:16,650 >> СТЕПАН: Стефан. 709 00:23:16,650 --> 00:23:18,191 >> Девід Дж Малан: Стефан знаходиться в дорозі. 710 00:23:18,191 --> 00:23:23,490 Тому, перш ніж Стефан вирішує цю Проблема, що ми повинні робити? 711 00:23:23,490 --> 00:23:25,412 Що ми робимо зі Стефаном? 712 00:23:25,412 --> 00:23:27,269 >> АУДИТОРІЯ: [нерозбірливо]. 713 00:23:27,269 --> 00:23:28,060 Девід Дж Малан: ОК. 714 00:23:28,060 --> 00:23:28,850 Таким чином, ми могли б зробити це. 715 00:23:28,850 --> 00:23:31,730 Ми могли б прийняти своєрідний Стефана і його чотири, і просто покласти його в змінній 716 00:23:31,730 --> 00:23:33,530 і провести на ній деяка кількість часу, 717 00:23:33,530 --> 00:23:35,220 тим самим звільняючи місце для номер один. 718 00:23:35,220 --> 00:23:36,280 І це не погано. 719 00:23:36,280 --> 00:23:39,270 Я міг би запропонувати, чому не ми просто покласти Стефана тут? 720 00:23:39,270 --> 00:23:41,610 Чому це може порушити одне ідей ми почали 721 00:23:41,610 --> 00:23:44,830 говорити про останній час, минулого тижня? 722 00:23:44,830 --> 00:23:45,330 Так? 723 00:23:45,330 --> 00:23:45,740 >> АУДИТОРІЯ: [нерозбірливо]. 724 00:23:45,740 --> 00:23:46,860 >> Девід Дж Малан: Там немає Індекс для нього. 725 00:23:46,860 --> 00:23:49,735 Якщо ви думаєте, це, дійсно, як Масив, це як негативний, 726 00:23:49,735 --> 00:23:52,900 так що немає насправді пам'ять тут, якщо це дійсно масив, 727 00:23:52,900 --> 00:23:55,090 як ми оголосили минулого тижня в лекції. 728 00:23:55,090 --> 00:23:56,250 Таким чином, ми не повинні робити цього. 729 00:23:56,250 --> 00:23:57,340 Ми могли б зберігати його в змінної. 730 00:23:57,340 --> 00:23:57,820 >> Чи ви знаєте, що? 731 00:23:57,820 --> 00:23:59,153 Я чув, хтось ще запропонувати це. 732 00:23:59,153 --> 00:24:01,020 Що ще ми можемо зробити зі Стефаном? 733 00:24:01,020 --> 00:24:03,770 Чому б нам просто не виселити його і покласти його на себе, де номер один було. 734 00:24:03,770 --> 00:24:05,170 Так що, якщо ви хочете піти туди. 735 00:24:05,170 --> 00:24:07,300 І справді, це досить хороше рішення. 736 00:24:07,300 --> 00:24:10,480 Тепер, з одного боку, я начебто з зробив проблему гірше. 737 00:24:10,480 --> 00:24:13,650 Чотири тепер далі від того, де це повинно бути. 738 00:24:13,650 --> 00:24:14,900 Вона повинна бути до цього половині. 739 00:24:14,900 --> 00:24:16,100 >> Але ви знаєте, що? 740 00:24:16,100 --> 00:24:17,630 Це можна було б невезіння. 741 00:24:17,630 --> 00:24:18,822 Можливо, номер вісім був тут. 742 00:24:18,822 --> 00:24:20,530 І так, може бути, ми б отримали пощастило, 743 00:24:20,530 --> 00:24:22,460 і штовхнув восьмій ближче до кінця. 744 00:24:22,460 --> 00:24:24,710 Таким чином, в кінці кінців, Це частково всі середні з. 745 00:24:24,710 --> 00:24:26,085 Нам не потрібно піклуватися про чотирьох. 746 00:24:26,085 --> 00:24:29,400 Все, що я дбаю про прямо зараз вибору найменшого елемента. 747 00:24:29,400 --> 00:24:32,030 >> А тепер, що я збираюся зробити, це забути про номер один 748 00:24:32,030 --> 00:24:35,160 постійно, тому що я знаю Список позаду мене тепер сортуються. 749 00:24:35,160 --> 00:24:36,720 Так що мій список був раніше розмір восьмій. 750 00:24:36,720 --> 00:24:37,720 Тепер, це розмір сім. 751 00:24:37,720 --> 00:24:40,340 Так моя проблема стає менше, хоча лінійно. 752 00:24:40,340 --> 00:24:43,022 Так що тепер, я збираюся вибрати ток найменший елемент, два. 753 00:24:43,022 --> 00:24:46,520 Шість, вісім, чотири, три, сім, п'ять. 754 00:24:46,520 --> 00:24:47,770 Це був найменший елемент. 755 00:24:47,770 --> 00:24:49,416 Так що я збираюся зробити with-- який був ваше ім'я? 756 00:24:49,416 --> 00:24:49,760 >> ЙОСИП: Джозеф. 757 00:24:49,760 --> 00:24:50,085 >> Девід Дж Малан: Джозеф? 758 00:24:50,085 --> 00:24:52,000 Ми збираємося, щоб залишити Йосипа на місці. 759 00:24:52,000 --> 00:24:54,842 Тепер, я збираюся робити вигляд, що ці хлопці добре are--, 760 00:24:54,842 --> 00:24:56,550 Я знаю, що ці два вже відсортовані. 761 00:24:56,550 --> 00:24:58,424 Давайте тепер зосередитися на Інша частина списку. 762 00:24:58,424 --> 00:25:00,080 Шість є поточним найменшим. 763 00:25:00,080 --> 00:25:01,190 Вісім більше. 764 00:25:01,190 --> 00:25:02,970 Чотири тепер ток маленький. 765 00:25:02,970 --> 00:25:04,762 Три тепер струму мала. 766 00:25:04,762 --> 00:25:07,720 І ось тепер, я збираюся вибрати три, які is-- що ваше ім'я знову? 767 00:25:07,720 --> 00:25:08,190 Серена: Серена. 768 00:25:08,190 --> 00:25:10,620 Девід Дж Малан: Серена, якби ви могли захопити ваш номер і своп with-- 769 00:25:10,620 --> 00:25:11,550 Калсанг: Калсанг. 770 00:25:11,550 --> 00:25:12,940 Девід Дж Малан: Калсанг. 771 00:25:12,940 --> 00:25:15,220 Повертайся, і ми збирається поміняти ці два. 772 00:25:15,220 --> 00:25:17,360 А тепер, давайте поставити це на автопілоті. 773 00:25:17,360 --> 00:25:21,589 Я збираюся піти і залишити його з вами, хлопці щоб вибрати наступні найменші елементи. 774 00:25:21,589 --> 00:25:22,380 Дун, сірувато, сірувато, сірувато. 775 00:25:22,380 --> 00:25:24,560 Номер чотири, що ви повинні робити? 776 00:25:24,560 --> 00:25:26,261 Відмінно. 777 00:25:26,261 --> 00:25:27,760 Тепер, я збираюся зробити ще один прохід. 778 00:25:27,760 --> 00:25:28,590 Дун, сірувато, сірувато, сірувато. 779 00:25:28,590 --> 00:25:31,465 Я бачу п`ять є наступним найменшим. 780 00:25:31,465 --> 00:25:32,840 Тепер, я збираюся взяти ще один прохід. 781 00:25:32,840 --> 00:25:33,631 Дун, сірувато, сірувато, сірувато. 782 00:25:33,631 --> 00:25:34,880 Шість є найменшим. 783 00:25:34,880 --> 00:25:35,520 Добре. 784 00:25:35,520 --> 00:25:36,585 Сім найменших. 785 00:25:36,585 --> 00:25:37,085 Без змін. 786 00:25:37,085 --> 00:25:38,630 Вісім найменших. 787 00:25:38,630 --> 00:25:39,170 Готово. 788 00:25:39,170 --> 00:25:43,900 >> Так що ми тільки що зробили итеративно вибравши один елемент за іншим 789 00:25:43,900 --> 00:25:47,230 це реалізувати те, що ми збирається оформити у виборі роду. 790 00:25:47,230 --> 00:25:49,120 І це, можливо, навіть простіше пояснити, 791 00:25:49,120 --> 00:25:51,310 в тому, що буквально все, що ви хочу зробити, це просто тримати 792 00:25:51,310 --> 00:25:54,700 вперед і назад за списком вибору, наступний найменший елемент, 793 00:25:54,700 --> 00:25:55,720 поки ви не закінчите. 794 00:25:55,720 --> 00:25:58,650 >> Так що це навіть простіше, можливо, інтуїтивно, ніж торік. 795 00:25:58,650 --> 00:26:00,020 Давайте спробуємо один останній. 796 00:26:00,020 --> 00:26:03,060 Якщо ви, хлопці, може скинути себе в наступних положеннях 797 00:26:03,060 --> 00:26:08,600 один останній раз, давайте подивимося, якщо ми не можемо Тепер оформити ще один підхід. 798 00:26:08,600 --> 00:26:12,857 Справді, хтось там би запропонувати 799 00:26:12,857 --> 00:26:14,440 як ще ми могли б йти про це? 800 00:26:14,440 --> 00:26:17,439 Без викинути слівця або роду відповідей, які вже відомі, 801 00:26:17,439 --> 00:26:19,689 просто інтуїтивно, що ми могли зробити? 802 00:26:19,689 --> 00:26:21,635 >> АУДИТОРІЯ: [нерозбірливо]. 803 00:26:21,635 --> 00:26:22,510 Девід Дж Малан: Так. 804 00:26:22,510 --> 00:26:24,620 Так що деякі великі інтуїція є. 805 00:26:24,620 --> 00:26:28,020 Хороші речі, здається, досі трапляються в комп'ютерній науці, коли ми ділимо 806 00:26:28,020 --> 00:26:30,832 і завоювати проблему поділу це в два рази і половина на половину. 807 00:26:30,832 --> 00:26:32,540 І так насправді, ми може почати робити це. 808 00:26:32,540 --> 00:26:35,754 І справді, що буде, ми будемо см, один з наших кращих рішень поки. 809 00:26:35,754 --> 00:26:37,420 Але давайте повернемося до того, що незабаром. 810 00:26:37,420 --> 00:26:40,500 Насправді, ми збираємося зробити що трохи пізніше на цьому тижні. 811 00:26:40,500 --> 00:26:42,180 Що ще ми могли б зробити, щоб вирішити цю проблему? 812 00:26:42,180 --> 00:26:44,647 Таким чином, кожен тут в здавалося б, випадковому порядку. 813 00:26:44,647 --> 00:26:45,230 Знаєш, що? 814 00:26:45,230 --> 00:26:48,320 Замість йти вперед і назад, взад і вперед, взад і вперед 815 00:26:48,320 --> 00:26:50,624 кожен раз, це відчуває себе подібно Я роблю багато ходити. 816 00:26:50,624 --> 00:26:52,790 Чому я не можу просто почати в початок списку, 817 00:26:52,790 --> 00:26:54,960 і просто поставити чотирьох, де вона належить? 818 00:26:54,960 --> 00:26:59,680 Отже, дозвольте мені припустити, що в даний момент мій список тільки цей перший елемент. 819 00:26:59,680 --> 00:27:04,937 Чотирьох сортуються в цей момент часу, якщо все, що я дбаю про те все тут? 820 00:27:04,937 --> 00:27:06,520 Це свого роду тривіально, чи не так? 821 00:27:06,520 --> 00:27:10,000 Як список, що містить один номер, і що номер чотири, очевидно, сортуються. 822 00:27:10,000 --> 00:27:13,070 >> Отже, дозвольте мені просто обмовити що цей список сортується. 823 00:27:13,070 --> 00:27:15,090 Але тепер у мене є все інше в цьому списку. 824 00:27:15,090 --> 00:27:17,240 Так що тепер, я стикаюся з два. 825 00:27:17,240 --> 00:27:21,690 Де два, очевидно, належать відносно чотирьох? 826 00:27:21,690 --> 00:27:22,580 Перед чотирьох. 827 00:27:22,580 --> 00:27:23,862 Так що я можу тут робити? 828 00:27:23,862 --> 00:27:24,820 Ваше ім'я знову? 829 00:27:24,820 --> 00:27:25,090 >> ЙОСИП: Джозеф. 830 00:27:25,090 --> 00:27:26,030 >> Девід Дж Малан: Йосип, якби ви могли відступити 831 00:27:26,030 --> 00:27:27,790 на мить з вашим номером. 832 00:27:27,790 --> 00:27:31,130 А тепер те, що повинно Стефан тут робити? 833 00:27:31,130 --> 00:27:33,720 Давайте перекласти Стефана сюди. 834 00:27:33,720 --> 00:27:35,520 А тепер, давайте Йосип прийшов сюди. 835 00:27:35,520 --> 00:27:39,660 А тепер, дозвольте мені заявити, що тут все сортується. 836 00:27:39,660 --> 00:27:42,474 Так, аналогічний результат, але Принципово інший підхід. 837 00:27:42,474 --> 00:27:44,140 Я навіть не дивився, що там внизу. 838 00:27:44,140 --> 00:27:46,310 Я просто продовжувати приймати елементи як вони передали мені, 839 00:27:46,310 --> 00:27:47,240 і боротьби з ними. 840 00:27:47,240 --> 00:27:48,330 >> Так що тепер, я бачу, номер шість. 841 00:27:48,330 --> 00:27:51,110 Де номер шість належать? 842 00:27:51,110 --> 00:27:53,250 У нас є два, чотири, шість. 843 00:27:53,250 --> 00:27:54,800 Точно, де вона зараз знаходиться. 844 00:27:54,800 --> 00:27:57,750 Так що давайте залишимо в спокої, що, і в даний час стверджують, що цій частині списку 845 00:27:57,750 --> 00:27:58,772 тепер сортуються. 846 00:27:58,772 --> 00:28:01,230 І так, це відчуває себе принципово відрізняється тим, що я просто 847 00:28:01,230 --> 00:28:05,230 переміщення за списком тут лінійно, і я ніколи не подвоєння тому. 848 00:28:05,230 --> 00:28:05,730 Так. 849 00:28:05,730 --> 00:28:06,230 Добре. 850 00:28:06,230 --> 00:28:08,190 Так восьмій, де ви належите? 851 00:28:08,190 --> 00:28:08,730 Саме тут. 852 00:28:08,730 --> 00:28:09,310 Ідеальний. 853 00:28:09,310 --> 00:28:10,210 Так що тепер, один. 854 00:28:10,210 --> 00:28:10,900 Ой-ой. 855 00:28:10,900 --> 00:28:13,010 Це відчуває, як ніби це буде дорого. 856 00:28:13,010 --> 00:28:15,690 Тепер, в попередньому алгоритмі, Я просто помінялися людей. 857 00:28:15,690 --> 00:28:18,648 Так що я поклав йому може повністю на початок, але потім переїхав Йосипа. 858 00:28:18,648 --> 00:28:21,450 Але, якщо я переїду Йосипа, тепер що буде так? 859 00:28:21,450 --> 00:28:24,250 >> Тепер, я начебто undone-- У мене приймати один крок вперед, а потім 860 00:28:24,250 --> 00:28:26,300 один крок назад, тому що тепер Джозеф буде в порядку. 861 00:28:26,300 --> 00:28:26,830 Так давайте зробимо це. 862 00:28:26,830 --> 00:28:29,150 Якщо б ви могли взяти номер один і крок назад на мить. 863 00:28:29,150 --> 00:28:30,490 Як ми можемо put--, що Ваше ім'я було знову? 864 00:28:30,490 --> 00:28:31,130 >> АННАН: Аннан. 865 00:28:31,130 --> 00:28:32,610 >> Девід Дж Малан: Аннан на місці? 866 00:28:32,610 --> 00:28:36,091 Що має відбутися щодо до двох, чотирьох, шести, восьми і? 867 00:28:36,091 --> 00:28:37,570 Всі вони повинні перемістити. 868 00:28:37,570 --> 00:28:42,590 Так що, якщо восьмій хотів перекласти , А потім шість, потім чотири, потім два. 869 00:28:42,590 --> 00:28:45,380 І тоді Аннан, якби ви хотів приїхати сюди, добре. 870 00:28:45,380 --> 00:28:47,760 Але тут, ми тільки вид заплатила 871 00:28:47,760 --> 00:28:49,510 в іншій точці в алгоритмі. 872 00:28:49,510 --> 00:28:52,550 У той час як останній раз з вибором сортувати і навіть бульбашкового сортування, 873 00:28:52,550 --> 00:28:54,700 Я йду назад і вперед, назад і вперед, 874 00:28:54,700 --> 00:28:58,360 який, безумовно, додавши, до Час-мудрий, і буквально поетапно. 875 00:28:58,360 --> 00:29:00,660 >> Сортування вставками, на перший погляд, виглядає, як ніби це 876 00:29:00,660 --> 00:29:05,150 супер розумнішими, в тому, що я просто повільний, поступовий прогрес, 877 00:29:05,150 --> 00:29:07,120 але я не збираюся це назад і вперед. 878 00:29:07,120 --> 00:29:09,410 Але якщо хтось дійсно із порядку, попередження 879 00:29:09,410 --> 00:29:10,840 всі роботи я просто повинен був зробити. 880 00:29:10,840 --> 00:29:14,750 Мені довелося переїхати половина списку просто, щоб звільнити місце для номер один. 881 00:29:14,750 --> 00:29:16,790 Так що це те ж саме кількість роботи досі його 882 00:29:16,790 --> 00:29:18,690 відчуває, просто інший тип роботи. 883 00:29:18,690 --> 00:29:19,370 >> Давайте продовжимо. 884 00:29:19,370 --> 00:29:22,657 Так що тепер ми знаємо, що кожен від одного до восьми сортуються. 885 00:29:22,657 --> 00:29:23,740 Ось, у мене є номер три. 886 00:29:23,740 --> 00:29:25,864 Якщо ви хочете, щоб забрати Номер три крок назад один. 887 00:29:25,864 --> 00:29:28,260 І те, що ви, хлопці, потрібно зробити? 888 00:29:28,260 --> 00:29:28,760 Так. 889 00:29:28,760 --> 00:29:33,070 Так що ще один, два, три кроки. 890 00:29:33,070 --> 00:29:36,010 Три одиниці часу, які просто стоять я, так що три можуть тепер підходять. 891 00:29:36,010 --> 00:29:37,460 Нарешті, сім. 892 00:29:37,460 --> 00:29:39,730 >> Давайте йти вперед і Ви крок назад. 893 00:29:39,730 --> 00:29:42,780 Це буде тільки коштувати нам одна одиниця часу, але це нормально. 894 00:29:42,780 --> 00:29:44,170 А тепер, п'ять збирається бути трохи дорожче. 895 00:29:44,170 --> 00:29:45,340 Якщо ви хочете зробити крок назад. 896 00:29:45,340 --> 00:29:48,380 Ми повинні рухатися восьмій, і сім, а шість. 897 00:29:48,380 --> 00:29:50,749 І тоді все буде тепер сортуються. 898 00:29:50,749 --> 00:29:52,290 Таким чином, велика рука, щоб наші добровольці тут. 899 00:29:52,290 --> 00:29:53,554 Дуже дякую. 900 00:29:53,554 --> 00:29:56,220 >> [Оплески] 901 00:29:56,220 --> 00:29:56,860 >> Дякую вам всім. 902 00:29:56,860 --> 00:29:57,520 Дякую вам всім. 903 00:29:57,520 --> 00:30:02,940 Отже, давайте подивимося, як тепер просто дорого все, що було. 904 00:30:02,940 --> 00:30:06,210 Давайте розглянемо, мабуть, Найпростіший з них, бульбашкова сортування. 905 00:30:06,210 --> 00:30:09,950 І я кажу простий, тільки тому, що Ви можете вирішити її з жадібністю, просто 906 00:30:09,950 --> 00:30:11,660 виправити попарно проблема. 907 00:30:11,660 --> 00:30:13,720 Закріпіть попарно проблеми Тут, знову і знову 908 00:30:13,720 --> 00:30:17,680 і знову, повторюючи як багато раз, як ви насправді потрібно. 909 00:30:17,680 --> 00:30:21,050 >> Так що виходить, що з бульбашкового сортування, добре, 910 00:30:21,050 --> 00:30:25,820 скільки кроків я повинен взяти на себе перший прохід цього алгоритму? 911 00:30:25,820 --> 00:30:30,850 Я міг би take-- давайте see-- один, два, три, чотири, п'ять, шість, сім. 912 00:30:30,850 --> 00:30:32,190 І є вісім елементів тут. 913 00:30:32,190 --> 00:30:35,280 Так як п мінус 1 до кроки отримати від початку списку 914 00:30:35,280 --> 00:30:36,380 в кінці списку. 915 00:30:36,380 --> 00:30:41,350 >> Але вибору-то, нагадаємо, що я знову і знову, вибираючи елементи 916 00:30:41,350 --> 00:30:44,590 і знову, що це маленький, Я ставлю його на місці, 917 00:30:44,590 --> 00:30:46,616 але тоді я не шукаю позаду мене знову. 918 00:30:46,616 --> 00:30:49,490 Так що я думаю, що це трохи більш ясним те, що в перший раз, я міг би 919 00:30:49,490 --> 00:30:52,680 повинні прийняти всі п мінус 1 кроки знайти найменший елемент. 920 00:30:52,680 --> 00:30:55,920 Тоді я поставити їх на місце, і я виселити хто був тут раніше. 921 00:30:55,920 --> 00:30:57,500 >> Але тоді я не повинен тримати дивлячись на цей елемент, 922 00:30:57,500 --> 00:30:59,040 тому що я знаю, що це Вже найменшим. 923 00:30:59,040 --> 00:31:01,581 Так що тепер, я можу дивитися на всього сім елементів, то шість елементів, 924 00:31:01,581 --> 00:31:03,290 потім п'ять елементів, то чотири елементи. 925 00:31:03,290 --> 00:31:06,900 І так математично, якщо п число елементів або цифр 926 00:31:06,900 --> 00:31:11,990 що ми почали з того, що ви можете собі що це те ж саме, п мінус 1, 927 00:31:11,990 --> 00:31:14,250 плюс мінус 2 п кроків, плюс мінус 3 п кроків, 928 00:31:14,250 --> 00:31:16,780 плюс мінус 4 п кроків, все аж до всього один крок. 929 00:31:16,780 --> 00:31:18,160 І я на моєму останньому людини. 930 00:31:18,160 --> 00:31:20,650 >> І якщо ви пам'ятаєте, що багато з книги або статистика математичні книги 931 00:31:20,650 --> 00:31:24,730 є ті формули, на твердій палітурці назад або перед ними, 932 00:31:24,730 --> 00:31:27,690 з'ясовується, що цієї серії може бути виражено більш просто 933 00:31:27,690 --> 00:31:28,857 мінус, як у п раз п 1 над 2. 934 00:31:28,857 --> 00:31:31,273 І це нормально, якщо це не на передньому краї свого розуму. 935 00:31:31,273 --> 00:31:32,420 Але це дійсно так. 936 00:31:32,420 --> 00:31:34,449 Це просто простий спосіб написання. 937 00:31:34,449 --> 00:31:36,240 І потім, якщо ви думаєте, повернутися до початковій школі, 938 00:31:36,240 --> 00:31:38,698 коли ви тільки починаєте множення речі з, це, звичайно ,, 939 00:31:38,698 --> 00:31:41,820 просто н квадраті мінус п ділиться на 2. 940 00:31:41,820 --> 00:31:44,772 Все, що я зробив, це розширити висловлювання там. 941 00:31:44,772 --> 00:31:46,730 І так давайте перепишемо це трохи по-іншому. 942 00:31:46,730 --> 00:31:49,780 Ось н квадраті розділити на 2 мінус п / 2. 943 00:31:49,780 --> 00:31:53,270 >> Отже, ще раз, я просто вид застосування деякі арифметичні правила є. 944 00:31:53,270 --> 00:31:57,140 Але зверніть увагу, в даний час, що найбільша термін в цьому виразі, так би мовити, 945 00:31:57,140 --> 00:31:58,540 є те, що п в квадраті. 946 00:31:58,540 --> 00:32:02,910 Так що, так, це п квадрат ділиться на 2, мінус п / 2. 947 00:32:02,910 --> 00:32:05,080 >> Але в цілому, якщо п буде велике значення, 948 00:32:05,080 --> 00:32:08,740 Я збираюся стверджувати, що п в квадраті буде домінуючим фактором. 949 00:32:08,740 --> 00:32:10,490 Це просто буде велика внесок 950 00:32:10,490 --> 00:32:12,877 на число кроків, ніж N / 2. 951 00:32:12,877 --> 00:32:13,960 Так що я маю на увазі під цим? 952 00:32:13,960 --> 00:32:16,795 Давайте спробуємо простий приклад, навіть хоча математика отримує трохи більшим. 953 00:32:16,795 --> 00:32:20,210 >> Отже, нехай у нас було 1 млн осіб на сцені, або 1 млн речей 954 00:32:20,210 --> 00:32:21,320 що ми хочемо, щоб розібратися. 955 00:32:21,320 --> 00:32:23,730 Давайте підключити мільйон в цій формулі точно 956 00:32:23,730 --> 00:32:27,230 щоб побачити, скільки кроків він приймає загальної сортувати мільйон елементи, використовуючи скажімо, 957 00:32:27,230 --> 00:32:28,560 Вибір роду. 958 00:32:28,560 --> 00:32:30,760 >> Таким чином, ми повинні були б ту ж формулу, як і раніше. 959 00:32:30,760 --> 00:32:34,120 Я підключити мільйон, так що я отримую мільйон квадрат поділяється на 2, 960 00:32:34,120 --> 00:32:35,990 мінус мільйон розділити на 2. 961 00:32:35,990 --> 00:32:40,180 Якщо я що математику в заздалегідь тут, у нас є 500 млрд 962 00:32:40,180 --> 00:32:47,460 мінус 500000, який дає нам +499999500000, 963 00:32:47,460 --> 00:32:49,270 що чертовски великий. 964 00:32:49,270 --> 00:32:54,370 >> Справді, якщо порівняти з підприємством 499000000000 999 млн 965 00:32:54,370 --> 00:33:01,210 500000 проти нашої первісної вартості, 500000000000, це так чертовски близько. 966 00:33:01,210 --> 00:33:06,850 Вірно? п квадраті розділити на 2 дає us-- або, скоріше, н квадраті розділити на 2 967 00:33:06,850 --> 00:33:08,370 дав нам 500 млрд. 968 00:33:08,370 --> 00:33:13,510 Це чертовски близько щоб 499,999,500,000, 969 00:33:13,510 --> 00:33:17,970 який повинен сказати, віднімання від 500000, або в більш загальному, віднімаючи від 970 00:33:17,970 --> 00:33:20,010 п квадраті, насправді не велика справа. 971 00:33:20,010 --> 00:33:22,490 У Російській квадрат робить ці число виросте дуже швидко. 972 00:33:22,490 --> 00:33:25,790 >> Тепер, це тільки важливе значення, оскільки як ми, як комп'ютерні вчених, 973 00:33:25,790 --> 00:33:29,350 як правило, не буде піклуватися так багато про нюанси цих формул 974 00:33:29,350 --> 00:33:31,400 і саме те, що точні відповіді. 975 00:33:31,400 --> 00:33:33,390 Ми піклуємося лише, що, ви знаєте, що? 976 00:33:33,390 --> 00:33:37,810 Зрештою, ця формула складає близько п квадрат. 977 00:33:37,810 --> 00:33:39,350 >> Так, ми поділу на 2 в там. 978 00:33:39,350 --> 00:33:41,360 Так, ми віднімаючи від п мінус 2. 979 00:33:41,360 --> 00:33:46,860 Але врешті-решт, термін що насправді шкодить нам і варто нам 980 00:33:46,860 --> 00:33:48,995 багато кроків, що квадрат термін. 981 00:33:48,995 --> 00:33:51,370 І так, що вчений-комп'ютерник збирається як правило, роблять 982 00:33:51,370 --> 00:33:54,160 це ігнорувати всі ті менші терміни, порядок 983 00:33:54,160 --> 00:33:56,900 і просто подивитися на той, який сприяє найбільш до вартості. 984 00:33:56,900 --> 00:34:00,530 >> І це приємно, тому що ми можемо Тепер поговоримо набагато більшої спільності 985 00:34:00,530 --> 00:34:02,470 про алгоритми, і може порівняти їх. 986 00:34:02,470 --> 00:34:04,550 І той факт, що я за допомогою цього висновку є навмисним. 987 00:34:04,550 --> 00:34:06,680 Коли я кажу про порядок з, я спеціально 988 00:34:06,680 --> 00:34:09,560 посилаючись на те називається великий О. І Big O 989 00:34:09,560 --> 00:34:14,090 це позначення, що комп'ютер Вчений використовує, щоб описати 990 00:34:14,090 --> 00:34:16,710 верхня межа на щось. 991 00:34:16,710 --> 00:34:21,150 >> Так що, якщо ви говорите, що алгоритм у великому O н квадрат, 992 00:34:21,150 --> 00:34:23,380 як я запропонував просто Хвилину тому, що кошти 993 00:34:23,380 --> 00:34:27,710 що з точки зору його експлуатації часу або його ефективність, 994 00:34:27,710 --> 00:34:30,090 вона займає порядку н квадраті кроки. 995 00:34:30,090 --> 00:34:31,420 Може бути, більше, може менше. 996 00:34:31,420 --> 00:34:33,435 Але це на порядок п в квадраті. 997 00:34:33,435 --> 00:34:34,560 І це верхня межа. 998 00:34:34,560 --> 00:34:36,530 Це не буде більш болючим, ніж це. 999 00:34:36,530 --> 00:34:40,800 Це не буде п кубі, або 2 до п, або щось набагато більше. 1000 00:34:40,800 --> 00:34:43,800 Це верхня межа на те, що, що вартість. 1001 00:34:43,800 --> 00:34:46,150 Тому, враховуючи, що, давайте Розглянемо кілька прикладів. 1002 00:34:46,150 --> 00:34:49,820 І це тільки кінцевий список дуже загальні часу проходження 1003 00:34:49,820 --> 00:34:52,870 Для алгоритмів, які призначається, щоб бути ілюструють деякі речі, які ми 1004 00:34:52,870 --> 00:34:53,600 бачив вже. 1005 00:34:53,600 --> 00:34:58,060 >> Так, наприклад, у випадку Вибір роду, що я стверджуючи, тут 1006 00:34:58,060 --> 00:35:02,250 працює, що вибір Сорти час на порядок п в квадраті. 1007 00:35:02,250 --> 00:35:06,260 У гіршому випадку, я буду мати ціла купа випадкових чисел тут. 1008 00:35:06,260 --> 00:35:08,600 І, як ми бачили математично, якщо я постійно ходити 1009 00:35:08,600 --> 00:35:11,310 за списком, через Список, вибравши наступний маленький 1010 00:35:11,310 --> 00:35:14,410 елемент знову і знову, якщо я насправді записати всі кроки 1011 00:35:14,410 --> 00:35:18,750 Я приймаю я запропонував formulaically перш, це близько п квадратів 1012 00:35:18,750 --> 00:35:20,370 кроки, які я приймаю. 1013 00:35:20,370 --> 00:35:24,520 >> І виходить, що міхур відсортуйте сортування вставками 1014 00:35:24,520 --> 00:35:27,370 так само, як повільно в гіршому випадку. 1015 00:35:27,370 --> 00:35:32,040 Розглянемо, наприклад, сортування вставками, найостанніший алгоритм ми мали справу з, 1016 00:35:32,040 --> 00:35:35,500 який змусив нас подивитися на елемент, а потім вставте його там, де він належить. 1017 00:35:35,500 --> 00:35:38,720 А потім ми дивилися на наступний елемент, і вставляється там, де він належить. 1018 00:35:38,720 --> 00:35:40,990 >> Так вважають кращий можливий сценарій. 1019 00:35:40,990 --> 00:35:45,590 Припустимо, я мої добровольці шикуються буквально, як це, від одного до восьми, 1020 00:35:45,590 --> 00:35:47,440 вже відсортовані. 1021 00:35:47,440 --> 00:35:51,300 Скільки кроків є сортування вставками збирається зробити, щоб розібратися вісім чоловік, 1022 00:35:51,300 --> 00:35:55,640 якщо вони прибувають на сцені дивлячись, як це? 1023 00:35:55,640 --> 00:35:57,410 >> Вісім чоловік вже відсортовані. 1024 00:35:57,410 --> 00:35:58,760 І я використовую вставки роду. 1025 00:35:58,760 --> 00:36:02,180 Це останній з алгоритмів. 1026 00:36:02,180 --> 00:36:03,640 Ну, давайте відтворити дуже швидко. 1027 00:36:03,640 --> 00:36:05,504 Так що, якщо я починаю тут, я бачу один. 1028 00:36:05,504 --> 00:36:06,420 Де ж можна належать? 1029 00:36:06,420 --> 00:36:07,730 Він належить тут. 1030 00:36:07,730 --> 00:36:08,330 Я бачу два. 1031 00:36:08,330 --> 00:36:09,660 Де двоє належать? 1032 00:36:09,660 --> 00:36:10,260 Саме тут. 1033 00:36:10,260 --> 00:36:10,900 Я бачу зо три. 1034 00:36:10,900 --> 00:36:11,920 Де три належать? 1035 00:36:11,920 --> 00:36:12,480 Саме тут. 1036 00:36:12,480 --> 00:36:13,100 >> Я бачу чотири. 1037 00:36:13,100 --> 00:36:13,600 Саме тут. 1038 00:36:13,600 --> 00:36:15,660 П'ять, шість, сім, вісім. 1039 00:36:15,660 --> 00:36:17,320 Там немає причин, щоб повторюватися. 1040 00:36:17,320 --> 00:36:21,260 І так, скільки кроків є те, що через п? 1041 00:36:21,260 --> 00:36:23,870 Це на порядок п кроки, вірно? п мінус 1. 1042 00:36:23,870 --> 00:36:27,567 Але я взяв лінійний номер кроків, і тепер я зробив. 1043 00:36:27,567 --> 00:36:28,900 Так що це кращий випадок, хоча. 1044 00:36:28,900 --> 00:36:29,983 Що можна сказати про гіршому випадку? 1045 00:36:29,983 --> 00:36:32,730 Що вісім минулого там, і сім були там, 1046 00:36:32,730 --> 00:36:35,840 і один і два були тут, так що список дійсно були назад? 1047 00:36:35,840 --> 00:36:38,300 >> Ну, те, що відбувається насправді якщо це число? 1048 00:36:38,300 --> 00:36:41,300 І ми будемо робити тільки пару прикладів. 1049 00:36:41,300 --> 00:36:49,300 Що робити, якщо, дійсно, номер вісім тут, і number-- вигуки. 1050 00:36:49,300 --> 00:36:52,660 1051 00:36:52,660 --> 00:36:56,430 Так що, якщо, дійсно, кількість Вісім повністю тут, 1052 00:36:56,430 --> 00:36:57,790 і я використовую вставки роду? 1053 00:36:57,790 --> 00:36:58,290 >> ДОБРЕ. 1054 00:36:58,290 --> 00:37:00,280 Я стверджую, на даний момент він знаходиться в місці. 1055 00:37:00,280 --> 00:37:03,152 Але тепер, seven-- де ж самі сім йти? 1056 00:37:03,152 --> 00:37:04,360 Звичайно, це йде тут. 1057 00:37:04,360 --> 00:37:06,760 Так що я повинен рухатися восьмій над одному місці. 1058 00:37:06,760 --> 00:37:08,554 Тепер шостій, де це йде? 1059 00:37:08,554 --> 00:37:09,220 Ну, все в порядку. 1060 00:37:09,220 --> 00:37:13,150 Тепер, я повинен рухатися восьмій над місце, і сім над місцем, 1061 00:37:13,150 --> 00:37:14,440 і тоді я плюхнутися шість. 1062 00:37:14,440 --> 00:37:16,870 >> Таким чином, перший раз, це вартість мені один крок, щоб виправити становище, 1063 00:37:16,870 --> 00:37:18,570 то це коштувало мені два кроки, щоб виправити становище. 1064 00:37:18,570 --> 00:37:20,370 Скільки кроків це збирається зробити, щоб виправити 1065 00:37:20,370 --> 00:37:22,720 речі, щоб поставити п'ять у потрібному місці? 1066 00:37:22,720 --> 00:37:23,340 Три. 1067 00:37:23,340 --> 00:37:29,520 Тому що тепер я повинен рухатися один, два, три. 1068 00:37:29,520 --> 00:37:32,430 Скільки кроків він збирається взяти покласти чотири в потрібному місці? 1069 00:37:32,430 --> 00:37:36,040 4 плюс 5, плюс 6 плюс 7. 1070 00:37:36,040 --> 00:37:40,260 >> І так це математично ідентичні те, що ми описали для вибору роду. 1071 00:37:40,260 --> 00:37:42,130 У нас є ця серія ось тільки зростає. 1072 00:37:42,130 --> 00:37:45,650 1 плюс 2 плюс 3 плюс 4, або, навпаки, плюс 7 червня 1073 00:37:45,650 --> 00:37:52,610 плюс 5 плюс 4 додає на сьогодні Цілі в порядку п в квадраті. 1074 00:37:52,610 --> 00:37:57,640 >> Отже, дозвольте мені передбачають також, що бульбашкового сортування також у п квадраті. 1075 00:37:57,640 --> 00:38:01,340 Тому що з бульбашкового сортування, кожен раз я йду за списком, 1076 00:38:01,340 --> 00:38:03,100 Я приймаю приблизно, скільки кроків? 1077 00:38:03,100 --> 00:38:06,260 Кожен раз, коли я буквально ходьби від туди потрапити? 1078 00:38:06,260 --> 00:38:07,960 Приблизно п кроків. 1079 00:38:07,960 --> 00:38:12,650 Але скільки разів я міг би потрібно йти за списком? 1080 00:38:12,650 --> 00:38:13,920 >> Ну, приблизно п раз. 1081 00:38:13,920 --> 00:38:15,680 Може п мінус 1, але приблизно в п раз. 1082 00:38:15,680 --> 00:38:16,430 Ну, чому ж? 1083 00:38:16,430 --> 00:38:19,560 Ну, з бульбашкового сортування, якщо ми починаємо з бульбашкового сортування, 1084 00:38:19,560 --> 00:38:23,570 зі списком в гіршому ситуація, яка знову повністю 1085 00:38:23,570 --> 00:38:25,550 у зворотному напрямку, то, що станеться? 1086 00:38:25,550 --> 00:38:28,830 Я йду за списком, і номер одним належить весь шлях туди. 1087 00:38:28,830 --> 00:38:33,280 >> Але з бульбашкового сортування, наскільки робить один рухатися на моєму першому проході за списком? 1088 00:38:33,280 --> 00:38:36,620 Скільки місця він отримує ближче до правильного місця? 1089 00:38:36,620 --> 00:38:37,240 Тільки один. 1090 00:38:37,240 --> 00:38:40,281 Так що, якщо вас вид причина через це, кожен раз, коли через цей алгоритм, 1091 00:38:40,281 --> 00:38:41,880 Давида, що приймають близько п кроків. 1092 00:38:41,880 --> 00:38:44,940 Але скільки проходить через список його 1093 00:38:44,940 --> 00:38:49,060 збирається взяти для одного міхура ліворуч, де вона належить? 1094 00:38:49,060 --> 00:38:51,840 >> Він повинен рухатися, як, п простору таким чином. 1095 00:38:51,840 --> 00:38:57,960 Так що, щоб зробити сортування списку, Я повинен ходити взад і вперед п раз. 1096 00:38:57,960 --> 00:39:01,540 І кожен раз, я дивлячись на п елементів. 1097 00:39:01,540 --> 00:39:05,410 Так що російські речі п раз на порядок п в квадраті. 1098 00:39:05,410 --> 00:39:07,220 >> Тепер ми побачимо, в деяких шортів, що 1099 00:39:07,220 --> 00:39:10,440 вбудовані в наступної проблеми CS50 в встановити, інший підхід в них, 1100 00:39:10,440 --> 00:39:13,490 але зараз, давайте просто розглянемо деякі інші поточні часи, 1101 00:39:13,490 --> 00:39:16,840 особливо якщо взяти ті сортування небагато часу, щоб зануритися в. 1102 00:39:16,840 --> 00:39:21,790 Що таке алгоритм ми вже бачили що бере на себе порядку п кроків? 1103 00:39:21,790 --> 00:39:27,560 >> Що слід прийняти лінійний номер кроків, які ми бачили дотепер? 1104 00:39:27,560 --> 00:39:29,350 Що це? 1105 00:39:29,350 --> 00:39:30,480 Пошук телефонний довідник. 1106 00:39:30,480 --> 00:39:31,390 Перший алгоритм. 1107 00:39:31,390 --> 00:39:31,560 Вірно? 1108 00:39:31,560 --> 00:39:33,650 Де ми лінійно пошук Майк Сміт? 1109 00:39:33,650 --> 00:39:34,150 Дійсно. 1110 00:39:34,150 --> 00:39:37,180 Від нульової тижня, коли я почав перетворюючи одну сторінку в той час, 1111 00:39:37,180 --> 00:39:40,095 і я навіть сказав, що це був вид алгоритму лінійної почуття, 1112 00:39:40,095 --> 00:39:42,720 і у нас було що картинка на дошка з прямою червоної лінії 1113 00:39:42,720 --> 00:39:44,678 і прямої жовтий лінія, це були дійсно 1114 00:39:44,678 --> 00:39:46,810 алгоритми, які у великій O п. 1115 00:39:46,810 --> 00:39:50,680 >> Тому що, щоб знайти Майка Сміта в телефоні Книга російських сторінок, в гіршому випадку, 1116 00:39:50,680 --> 00:39:52,422 може взяти мене н кроки. 1117 00:39:52,422 --> 00:39:53,630 Що про прийняття відвідуваність? 1118 00:39:53,630 --> 00:39:55,790 Один два три чотири п'ять шість. 1119 00:39:55,790 --> 00:39:59,420 Що час роботи цього Алгоритм для прийняття відвідуваності? 1120 00:39:59,420 --> 00:40:03,070 Великий О п, тому що в теорії я повинен вказати всіх в кімнаті. 1121 00:40:03,070 --> 00:40:05,861 >> Тепер, як в сторону, те, що про другий оптимізації з нуля тиждень? 1122 00:40:05,861 --> 00:40:08,117 Два, чотири, шість, вісім, 10, 12. 1123 00:40:08,117 --> 00:40:10,200 Комп'ютер вчений буде реалізувати, зачекайте хвилину, 1124 00:40:10,200 --> 00:40:12,320 це близько п ділиться на два етапи. 1125 00:40:12,320 --> 00:40:12,820 Вірно? 1126 00:40:12,820 --> 00:40:14,444 Тому що я роблю дві людини одночасно. 1127 00:40:14,444 --> 00:40:17,015 Але ми збираємося ігнорувати ці молодші члени, 1128 00:40:17,015 --> 00:40:19,140 і ми тільки збираємося викинути розділити на 2, 1129 00:40:19,140 --> 00:40:21,830 і просто сказати, великий виведення п для цього алгоритму, а також. 1130 00:40:21,830 --> 00:40:22,760 >> Як щодо цього? 1131 00:40:22,760 --> 00:40:26,170 Ми пропускаємо деякі з них, але те, що був алгоритм, який був журнал п? 1132 00:40:26,170 --> 00:40:29,900 Це зайняло приблизно увійти п кроків? 1133 00:40:29,900 --> 00:40:30,870 Розділяй і володарюй. 1134 00:40:30,870 --> 00:40:31,369 Точно. 1135 00:40:31,369 --> 00:40:33,900 Як, наприклад телефонної книги в нульовий тижня і сьогодні вранці, 1136 00:40:33,900 --> 00:40:36,191 де ми розділили проблеми знову і знову, і знову. 1137 00:40:36,191 --> 00:40:39,070 Ми звернули його на дошці в тиждень нулю при зігнутої зеленою лінією, 1138 00:40:39,070 --> 00:40:41,460 і ми сказали, що це був день логарифмічна алгоритм. 1139 00:40:41,460 --> 00:40:44,970 >> І справді, число кроків, вона, потрібно, щоб виконати розділяй і володарюй, 1140 00:40:44,970 --> 00:40:48,610 або бінарний пошук, як ми почнемо називаючи його, як в телефонній книзі, 1141 00:40:48,610 --> 00:40:50,680 на порядок журналі і кроків. 1142 00:40:50,680 --> 00:40:52,470 І це трохи дивно одне. 1143 00:40:52,470 --> 00:40:54,910 >> Що робить крок, або, більш конкретно 1144 00:40:54,910 --> 00:40:56,240 постійне число кроків? 1145 00:40:56,240 --> 00:40:58,865 Може бути, це двоє, може бути, це три, але вчений просто 1146 00:40:58,865 --> 00:41:01,423 спрощує його як Big O 1, деяка константа число кроків. 1147 00:41:01,423 --> 00:41:04,256 Щось ви могли б зробити, що бере постійну кількість кроків? 1148 00:41:04,256 --> 00:41:08,030 1149 00:41:08,030 --> 00:41:10,930 >> Що час роботи ляскаючи? 1150 00:41:10,930 --> 00:41:11,920 Постійне час. 1151 00:41:11,920 --> 00:41:12,420 Вірно? 1152 00:41:12,420 --> 00:41:15,490 Мовляв, те, що час роботи робити що-небудь, що бере тільки один 1153 00:41:15,490 --> 00:41:18,570 Операція, як друкувати F Hello World. 1154 00:41:18,570 --> 00:41:24,110 Це може бути названо постійна часу, якщо менше кут випадку з F друк, 1155 00:41:24,110 --> 00:41:28,260 Що може час роботи друку F насправді бути? 1156 00:41:28,260 --> 00:41:28,790 І чому? 1157 00:41:28,790 --> 00:41:30,550 Що н вимірювання в цьому випадку? 1158 00:41:30,550 --> 00:41:32,251 >> АУДИТОРІЯ: [нерозбірливо]. 1159 00:41:32,251 --> 00:41:33,250 Девід Дж Малан: Точно. 1160 00:41:33,250 --> 00:41:34,900 Кількість символів ми хочемо, щоб надрукувати. 1161 00:41:34,900 --> 00:41:36,191 Так що це дуже контексту. 1162 00:41:36,191 --> 00:41:39,910 Сьогодні ми зосередилися багато на букви і цифри тут на дошці. 1163 00:41:39,910 --> 00:41:43,540 Але це може бути також символи в реальну рядок. 1164 00:41:43,540 --> 00:41:46,420 Ось і виходить, є інший міра, яка почне піклуватися про, 1165 00:41:46,420 --> 00:41:48,530 і це навпроти великого О, так би мовити. 1166 00:41:48,530 --> 00:41:50,120 >> Це омега позначення. 1167 00:41:50,120 --> 00:41:53,380 У той час як більша виведення означає, що це, то Верхня межа на біговій часу? 1168 00:41:53,380 --> 00:41:55,580 Максимально, скільки часу може щось взяти? 1169 00:41:55,580 --> 00:41:59,250 Omega-- шкода, що це продовжує прибувати up-- є протилежністю, що 1170 00:41:59,250 --> 00:42:02,960 в результаті чого це нижня межа на кількість часу щось може зайняти. 1171 00:42:02,960 --> 00:42:10,480 >> Так. Наприклад, те, що алгоритм який приймає завжди н в квадраті кроки? 1172 00:42:10,480 --> 00:42:15,600 Ну, один з алгоритмів ми бачили Сьогодні, насправді, може бути, що, як добре. 1173 00:42:15,600 --> 00:42:16,720 Сортувати Вибір. 1174 00:42:16,720 --> 00:42:18,270 Вибір роду досить безглуздо. 1175 00:42:18,270 --> 00:42:21,760 Навіть якщо algorithm-- вибачте, навіть якщо масив вже відсортовані, 1176 00:42:21,760 --> 00:42:24,150 Вибір роду збирається продовжувати йти за списком 1177 00:42:24,150 --> 00:42:28,907 щоб переконатися, що він має найменше елемент знову і знову, і знову. 1178 00:42:28,907 --> 00:42:31,740 І хоча ви, люди в Глядачі знають, що, почекай хвилинку, 1179 00:42:31,740 --> 00:42:33,948 Ви вже прийнятий найменший елемент, комп'ютер 1180 00:42:33,948 --> 00:42:37,300 не знає, що, поки вона виглядає весь шлях через список. 1181 00:42:37,300 --> 00:42:40,240 Аналогічним чином, нижня межа, що може бути також прийняті до уваги 1182 00:42:40,240 --> 00:42:42,000 може бути лінійний час. 1183 00:42:42,000 --> 00:42:48,260 >> Скільки часу потрібно, щоб Сортувати п елементів в краще 1184 00:42:48,260 --> 00:42:52,420 Справа використовуючи щось на зразок міхура роду? 1185 00:42:52,420 --> 00:42:54,280 Припустимо, що ваш список вже відсортований. 1186 00:42:54,280 --> 00:42:56,696 Ми сказали, бульбашкова сортування бере на порядок п квадраті кроки. 1187 00:42:56,696 --> 00:42:59,640 Але що, якщо це вже відсортовані? 1188 00:42:59,640 --> 00:43:02,310 Що робити, якщо ви розумієте, після один прохід по масиву 1189 00:43:02,310 --> 00:43:03,540 що ви не зробили жодного свопи? 1190 00:43:03,540 --> 00:43:05,970 Ви повинні продовжувати робити більше проходить? 1191 00:43:05,970 --> 00:43:06,470 >> Немає. 1192 00:43:06,470 --> 00:43:10,340 Таким чином, нижня межа бульбашкового сортування можна сказати, бути лінійною. 1193 00:43:10,340 --> 00:43:11,830 Омега п. 1194 00:43:11,830 --> 00:43:14,450 І ми можемо дивитися на решта них, а також. 1195 00:43:14,450 --> 00:43:17,990 Отже, давайте поглянемо на тільки візуалізації тут 1196 00:43:17,990 --> 00:43:20,790 щоб побачити, як вони відрізняються. 1197 00:43:20,790 --> 00:43:24,592 Я збираюся піти сюди в це сторінка, яка доступна на веб-сайті С50, в 1198 00:43:24,592 --> 00:43:27,550 але це буде біль, щоб отримати роботу, так як він використовує технологію під назвою 1199 00:43:27,550 --> 00:43:30,560 Java-аплети, який є в значній мірі підтримується в ці дні, 1200 00:43:30,560 --> 00:43:32,730 принаймні, Chrome і деяких інших. 1201 00:43:32,730 --> 00:43:37,070 >> І дозвольте мені йти вперед і прискорити цей і пояснити, що відбувається. 1202 00:43:37,070 --> 00:43:40,840 Це демонстрація міхура сортувати, перший алгоритм, ми дивилися. 1203 00:43:40,840 --> 00:43:43,950 І це візуалізація, що кожен з цих стрижнів являє собою число. 1204 00:43:43,950 --> 00:43:45,710 Чим більше бар, тим більше число. 1205 00:43:45,710 --> 00:43:47,520 Чим менше бар, чим менше число. 1206 00:43:47,520 --> 00:43:50,353 І те, що ви можете побачити візуально, навіть хоча це буде дуже швидко, 1207 00:43:50,353 --> 00:43:53,699 є те, що червона смуга, як мене, ходити взад і вперед фіксації проблеми. 1208 00:43:53,699 --> 00:43:56,740 Ви можете бачити, що чим більше елементів дійсно б'ється праворуч, 1209 00:43:56,740 --> 00:43:59,650 і менше елементів які б'ється зліва. 1210 00:43:59,650 --> 00:44:01,870 І тут, якщо ми насправді виглядають більш тісно, 1211 00:44:01,870 --> 00:44:04,330 ми можемо насправді підрахувати кількість порівнянь і обмінів 1212 00:44:04,330 --> 00:44:05,350 що були зроблені. 1213 00:44:05,350 --> 00:44:07,360 >> Але замість цього, давайте подивимося на другому алгоритмі 1214 00:44:07,360 --> 00:44:11,240 ми дивилися на раніше з нашою волонтери, вибір сортування. 1215 00:44:11,240 --> 00:44:13,500 Візуально він має дуже різні ефект. 1216 00:44:13,500 --> 00:44:16,820 Але це, знову ж таки, дуже інтуїтивним, в що ми тримаємо вибору наступного маленький 1217 00:44:16,820 --> 00:44:18,660 елемент, і ми отримали трохи пощастило. 1218 00:44:18,660 --> 00:44:20,110 Це відчував принципово швидше. 1219 00:44:20,110 --> 00:44:22,840 Але якщо ми побігли це знову і знову і знову з великою кількістю входів, 1220 00:44:22,840 --> 00:44:26,680 ми побачимо, що насправді це ще у великій O п квадраті. 1221 00:44:26,680 --> 00:44:29,920 >> Давайте зробимо один останній тут, сортування вставками, 1222 00:44:29,920 --> 00:44:33,180 який був третім алгоритм ми дивилися на, і відкликання 1223 00:44:33,180 --> 00:44:36,700 що це одна справа з елементи, як це стикається їх, 1224 00:44:36,700 --> 00:44:39,290 Але тоді, може бути, зрушення речі, щоб звільнити місце, 1225 00:44:39,290 --> 00:44:41,660 вставки елементів, де вони належать. 1226 00:44:41,660 --> 00:44:45,330 >> І це теж закінчується даючи Остаточний результат. Тепер всі три з них 1227 00:44:45,330 --> 00:44:46,490 відчував себе досить швидко. 1228 00:44:46,490 --> 00:44:48,740 І справді, я побіг їх на досить хороший кліп. 1229 00:44:48,740 --> 00:44:52,510 Але принципово, всі вони досить жахливо, чесно кажучи. 1230 00:44:52,510 --> 00:44:56,960 Всі ці алгоритми досі які працюють у великому O п квадраті 1231 00:44:56,960 --> 00:44:59,270 прийняти зовсім небагато час для запуску в кінці кінців. 1232 00:44:59,270 --> 00:45:01,920 >> І дійсно, ми бачимо, і відчуваю, що це, нарешті, 1233 00:45:01,920 --> 00:45:04,090 якщо тягнути цю третю і останню демо. 1234 00:45:04,090 --> 00:45:05,840 Це ще одна візуалізації, що відбувається, 1235 00:45:05,840 --> 00:45:08,500 показати бульбашкового сортування ліворуч, Вибір роду в середині, 1236 00:45:08,500 --> 00:45:13,410 і щось, як один з наших Рука піднімає раніше запропонував, 1237 00:45:13,410 --> 00:45:15,020 об'єднати то справа. 1238 00:45:15,020 --> 00:45:16,937 Розділяй і володарюй Стратегія праворуч. 1239 00:45:16,937 --> 00:45:19,520 І це, насправді, те, що ми будемо дивитися на середу. 1240 00:45:19,520 --> 00:45:21,990 Але давайте час ці балотуватися паралельно. 1241 00:45:21,990 --> 00:45:26,765 Це приблизно те ж саме кількість Елементи, все працює в той же час. 1242 00:45:26,765 --> 00:45:30,940 1243 00:45:30,940 --> 00:45:34,440 Пузир роду проти вибору Сортувати проти злиття роду. 1244 00:45:34,440 --> 00:45:36,760 >> Тепер вони все працює У теорії, в той же час. 1245 00:45:36,760 --> 00:45:39,830 Процесор працює на з тією ж швидкістю, але ви 1246 00:45:39,830 --> 00:45:44,014 може відчувати себе, як нудно це дуже швидко стане, 1247 00:45:44,014 --> 00:45:45,930 і тільки, як швидко, коли ми вводимо трохи тиждень 1248 00:45:45,930 --> 00:45:49,330 алгоритми Зеро може ми прискорити. 1249 00:45:49,330 --> 00:45:51,760 >> А тепер давайте порівняємо це в останній формі. 1250 00:45:51,760 --> 00:45:55,710 Я збираюся йти вперед на сайт CS50, де 1251 00:45:55,710 --> 00:45:59,020 у нас є цей заключний посилання на сьогодні, де хтось в Інтернеті 1252 00:45:59,020 --> 00:46:03,960 люб'язно воєдино відео, захоплює те, що різне сортування 1253 00:46:03,960 --> 00:46:07,510 алгоритми звучати. 1254 00:46:07,510 --> 00:46:09,577 Це свого роду вставки. 1255 00:46:09,577 --> 00:46:12,072 >> [ЗВУКОВИЙ СИГНАЛ] 1256 00:46:12,072 --> 00:46:13,070 1257 00:46:13,070 --> 00:46:16,850 >> Причому ви претендуєте частоту заснована на висоті бар бар. 1258 00:46:16,850 --> 00:46:19,826 Це свого роду міхур. 1259 00:46:19,826 --> 00:46:21,822 >> [Викривленням ЗВУКОВИЙ СИГНАЛ] 1260 00:46:21,822 --> 00:46:33,299 1261 00:46:33,299 --> 00:46:45,774 >> Далі йде is-- на наступному is-- вибір роду, 1262 00:46:45,774 --> 00:46:48,820 де знову, ми вибору наступний найменший елемент, 1263 00:46:48,820 --> 00:46:51,820 і ми можемо бачити, як він росте зліва направо. 1264 00:46:51,820 --> 00:47:01,120 1265 00:47:01,120 --> 00:47:04,000 >> Злиття сортувати, наш переможець досі сьогодні. 1266 00:47:04,000 --> 00:47:09,659 1267 00:47:09,659 --> 00:47:12,450 Зверніть увагу, як це ділення речі в [нерозбірливо] половину і чверті. 1268 00:47:12,450 --> 00:47:17,510 1269 00:47:17,510 --> 00:47:21,660 Гном роду, які ми не маємо говорили, і створює візуально 1270 00:47:21,660 --> 00:47:24,450 і audally трохи різна форма і звук. 1271 00:47:24,450 --> 00:47:27,060 1272 00:47:27,060 --> 00:47:30,160 Перехід вперед і назад, очищення речі. 1273 00:47:30,160 --> 00:47:32,230 Крім того, перевірити пірамідальної сортування на веб-сайті цього хлопця. 1274 00:47:32,230 --> 00:47:36,100 1275 00:47:36,100 --> 00:47:36,810 >> І це все. 1276 00:47:36,810 --> 00:47:38,210 Ми побачимо вас наступного разу. 1277 00:47:38,210 --> 00:47:42,647 1278 00:47:42,647 --> 00:47:48,334 >> [Свист І МУЗИКА] 1279 00:47:48,334 --> 00:50:24,839