>> СПИКЕР 1: Привет всем!
Добро пожаловать в раздел.
Так рада, что так многие из вас как здесь, и каждый, кто смотрит онлайн.
Так, как обычно Добро пожаловать.
Я надеюсь, что вы все были прекрасны выходные, полные отдыха, релаксации.
Это было красиво вчера.
Так что, я надеюсь, вам понравилась на открытом воздухе.
>> Итак, сначала пару объявлений.
Классификация.
Так, большинство из вас должен был получить по электронной почте от меня о вашем царапинам Pset,
а также классификации для Pset 1.
Так, только пара вещей.
Обязательно используйте check50 в style50.
Они предназначены, чтобы быть Ресурсы для вас, ребята,
чтобы убедиться, что вы получаете как можно больше очков, как вы можете
без нужды терять их.
Так, такие вещи, как стиль очень важны.
Мы собираемся снять для него.
Некоторые из вас, возможно, уже заметил, что от вашего Pset.
И check50 просто действительно простой способ, чтобы убедиться,
что мы на самом деле возвращения того, что должен быть возвращен пользователю,
и что все работает правильно.
>> На втором ноте, убедитесь, что ваш загрузки вещей в нужную папку.
Это делает мою жизнь только Немного сложнее
если вы загружаете Pset 2 в Pset 1 потому что, когда я скачать вещи,
они не скачать правильно.
И я знаю, что это немного шаткий в системе, чтобы привыкнуть к,
но просто супер осторожны, если только для меня,
так что, когда вы получаете письма на как 2 утра и я градация.
Если не вызвать у меня есть, чтобы посмотреть все вокруг для вашего Pset.
Прохладный.
>> Я знаю, что это рано, но я полностью были взяты врасплох
по эссе, это из-за этого в пятницу, то мои профессора были просто нравится, о да.
Помните, у вас есть эссе за пятницу.
Так, я знаю, никто не любит думать о промежуточных выборах,
но ваш первый викторина на 15 октября которые октября начинает на этой неделе.
Так, это может быть раньше чем вы ожидали все.
Так что вы не бросили врасплох, когда Я уже раздел на следующей неделе, что о,
ваш тест на следующей неделе, я думал, Я хотел бы дать вам немного больше
из руководителей сейчас.
>> Так, установлено, ваша проблема, номер три.
Как люди читали спец из любопытства?
Хорошо.
Мы получили несколько.
Вид вниз из прошлого неделю, но это нормально.
Я знаю, что это было красиво вне.
Так Break Out.
Определенно, после вы сделали сегодня прочитал вашу спецификацию по крайней мере,
попробуйте, как скачивание Код распределения и работает
как в первый инициал вещь, что они спрашивают вас.
Так как мы используем Код распределения и библиотека
что мы только using-- --Она ​​только Во второй раз мы сделали это Pset,
сумасшедшие вещи могут произойти с Вашей машины,
и вы хотите, чтобы найти, что прямо сейчас по сравнению с позже.
>> Потому что, если это в четверг вечером или это В среду вечером, и почему-
Ваш прибор просто не хочу работать с библиотекой
или с распределением Код, который средства
Вы не можете даже начать делать кодирование.
Потому что вы не можете проверить чтобы увидеть, если он работает.
Ваш не собираюсь быть в состоянии чтобы увидеть, если он собирает.
Вы хотите, чтобы заботиться о тех, в начале неделю, когда вы все еще можете написать мне
или один из других ТФ, и мы можем получить те фиксированной.
Потому что те вопросы, что собираются, чтобы остановить вас
от каких-либо реального прогресса.
Это не так, как одна ошибка, что Вы можете только отчасти пропустить.
Если у вас возникли проблемы с вашим Прибор или код распределение,
Вы действительно хотите, чтобы что принято заботиться о скорее раньше, чем позже.
Так что даже если вы не собираетесь на самом деле начать кодирование, загрузить дистрибутив
Код, прочитать спецификацию, убедитесь все работает там.
Хорошо?
Если вы можете просто сделать это, я обещаю вам жизнь будет легче.
И так вы, вероятно, сделать это прямо сейчас не так ли?
Хорошо.
Таким образом, любые вопросы там?
Любые логистические вещи?
Все хорошо?
Хорошо.
>> Отказ от ответственности для тех из Вы в комнате и на сайте.
Я собираюсь пытаться переключить между PowerPoint в приборе
потому что мы собираемся быть делать некоторые кодирование
сегодня по многочисленным просьбам из анонимного Предложение опрос я разослал на прошлой неделе.
Таким образом, мы будем делать некоторые кодирования.
Так что, если вы, ребята, тоже хочу чтобы запустить ваши приборы,
и вы должны есть по электронной почте от меня, с файлом образца.
Пожалуйста, не стесняйтесь сделать это.
>> Так, мы собираемся говорить о GDB, который является отладчик.
Это поможет вам вид выяснить, где
дела идут не так в вашем коде.
Это просто способ для вас шаг по коду, как это происходит,
и иметь возможность распечатать переменные или посмотреть, что происходит на самом деле
под капот стихи программу просто работает, это как разломов,
и вы, как, не имея представления, что только что произошло здесь.
Я не знаю, что линия его не удалось в.
Я не знаю, где пошло не так.
Так, GDB будет помогать вам в этом.
Кроме того, если вы решите продолжить да, и принять 61,
это будет очень, очень бы ваш лучший друг, потому что я могу вам сказать,
потому что я собираюсь через этого класса.
>> Мы будем смотреть на двоичном Поиск, который, если вы, ребята, помните
Отличный пример телефонная книга Зрелище из класса.
Мы будем реализации, что и ходить через что немного больше,
а затем мы собираемся через четыре различные виды, которые Bubble,
Выбор, вставки, и объединить.
Прохладный.
Так, GDB, как я уже говорил, это отладчик.
И это своего рода большой вещи, большие функции или команды
что вы используете в GDB, и буду ходить Вы через демо ней в секунду.
>> Таким образом, это не просто собираюсь остаться реферат.
Я постараюсь и сделать его как бетон насколько это возможно для вас, ребята.
Так, сломать.
Это будет прорыв либо как, некоторое число, которое
представляет собой строку в вашей программе, или вы можете назвать функцию.
Так что, если вы говорите, сломать основной, он остановится на главной,
и пусть вы идете через эту функцию.
>> Точно так же, если у вас есть какая-то внешняя функционировать как своп или Cube,
что мы смотрели на прошлой неделе.
Если вы говорите, нарушит одну из тех, всякий раз, когда ваша программа попадает, что,
это буду ждать тебя, чтобы скажите ему, что делать.
Прежде, чем это будет просто выполнить так вам может на самом деле шаг внутри функции
и посмотреть, что происходит.
Так, следующий, просто пропускает Следующая строка, переходит функций.
Шаг.
Это все немного абстрактный.
Так, я только собираюсь бежать через них, но вы увидите их в использовании в секунду.
>> Шаг в зависимости.
Так как я уже говорил, как с своп, это было бы
позволяют на самом деле, как будто ты как физически активизации внутри,
Вы можете связываться с этими переменными, печать то, что они, видите, что происходит.
Список будет буквально печати из окружающего кода.
Так что, если вы вроде забыть где вы находитесь в вашей программе,
или вам интересно что происходит вокруг него,
это будет просто распечатать сегмент из нравятся пять или шесть линий вокруг него.
Таким образом, вы можете сориентироваться о том, где вы находитесь.
>> Распечатать некоторые переменные.
Так что, если у вас есть ключ, как в Цезаря, что мы будем смотреть на.
Вы можете сказать, печати Key в любой момент.
Это вам скажу, что это значение так что, может быть, где-то по пути,
Вы переписал свой ключ.
Вы действительно можете сказать, что из-за Вы можете фактически наблюдать это значение.
>> В местных жителей, всего принтами из ваших локальных переменных.
Так, в любое время вы в цикле, и вы просто хотите, чтобы увидеть, как, ой.
Какова моя я?
Что это ключевая ценность что я инициализировать здесь?
Что такое сообщение в этой точке?
Это будет просто распечатать все из тех, так что вам
не должны индивидуально говорят, печати I. печати сообщение.
Печать Key.
А потом Дисплей.
То, что это делает, как вы шаг в рамках программы,
это просто чтобы убедиться, что это отображение некоторых определенную переменную
в каждой точке.
Так что вы also-- --Она ​​это вид ярлыка где
Вы не должны продолжать идти, как, ой.
Печать Key или печати I. Это просто автоматически сделает это за вас.
>> Так, с тем, что мы собираемся чтобы видеть, как это идет.
Я собираюсь попробовать и переключатель в мой прибор.
Смотрите, если я могу сделать это.
Все.
Мы просто собираемся, чтобы отразить его.
Там нет ничего, с ума на моем ноутбуке в любом случае.
Хорошо.
Это должен быть этот.
Это настолько крошечные.
Давайте посмотрим, если мы можем сделать это.
>> Хорошо.
Алиса, очевидно, борется здесь чуть-чуть,
но мы получим ее в Momento.
Хорошо.
Мы просто собираемся увеличить это.
Хорошо.
Может все вроде видели?
Может быть, немного?
Я знаю, это немного мала.
Вы не можете достаточно выяснить как сделать это больше.
Если кто-нибудь знает.
Кто-нибудь знает, как сделать его больше?
Хорошо.
Мы собираемся свернуть с него.
Не имеет значения, в любом случае, потому что это просто что код, который вы, ребята, должны
есть.
>> Что более важно, является терминал здесь.
И здесь мы имеем Почему так мало?
Настройки.
О.
Правда Айк.
Как это?
Из там.
Так лучше для всех?
Хорошо ,.
Прохладный.
>> Вы знаете, когда вы находитесь в CS технические трудности класса
являются своего рода частью the-- Так, давайте проясним это.
Хорошо.
Так, прямо здесь, в разделе, которые мы имели здесь.
Цезарь представляет собой исполняемый файл.
Так что я сделал это.
Так, одна вещь, чтобы понять, с GDB является что он работает только на исполняемых файлах.
Таким образом, вы не можете запустить его на dotsy.
Вы должны реально сделать Убедитесь, что ваш код компилируется,
и что он на самом деле может работать.
>> Итак, убедитесь, что если это не так компиляции, получить его для компиляции,
так что вы можете рода проходят через него.
Итак, для начала GDB, все, что вам делать, Глория типа GDB, а затем просто
файл, который вы хотите.
Я всегда опечатки Цезаря.
Но вы хотите, чтобы убедиться, так как это исполняемый,
Точка вспышки Ти так что означает, что вы идете
запустить CSI вы собираетесь выполнить это файлы либо с помощью отладчика.
Хорошо.
Так, вы что, вы получаете этот вид тарабарщина.
Это просто все вещи о отладчика.
Вы действительно не нужно беспокоиться об этом прямо сейчас.
И, как вы видите, у нас есть это открытые круглые скобки, ВВП, близкие круглые скобки,
и только отчасти похож наша командная строка, не так ли?
>> Итак, что же мы хотим do-- --So, Первое, что
это мы хотим выбрать место, чтобы разбить его.
Так, есть одна ошибка В этой программе Цезарь
что я представляю, что мы собираемся выяснить.
Это Что она делает, это он принимает на вход Barfoo заглавными буквами, и почему-
это не меняет А. Это просто оставляет только она, все остальное правильно,
но вторая буква Остается неизменным.
Так, мы собираемся, чтобы попытаться выяснить, почему это.
Так, первое, что вы, как правило, хочу сделать, когда вы начинаете на GDB
является выяснить, где разбить его.
>> Так Цезарь является довольно короткая программа.
Мы просто должны одну функцию, не так ли?
Что наша функция в Цезаря?
Там только одна функция, Главное правильно?
Главная функция для всех ваших программ.
Если у вас не было Main, я мог бы быть немного волновался сейчас,
но я надеюсь, что вы все были Main там.
Итак, что мы можем сделать, это мы можем просто разорвать Main, как и что.
Так, он говорит, ОК.
Мы ставим нашу останова один есть.
>> Так, в настоящее время помнить, Цезарь занимает одно командной строке аргументов право
и мы не сделали, что еще нигде.
Итак, что же вы делаете, когда Вы на самом деле идти работать
программа, любая программа, что ты работает в GDB, который нуждается командной строки
Аргументы, что вы собираетесь вход при первом запуске ее запуска.
Так, в данном случае, мы делаем Запуск с ключом в три раза.
И это будет на самом деле начать.
>> Так что, если вы видите здесь, у нас есть Если RC не равно 2.
Так что, если вы, ребята, у всех есть что файл, который я разослал до
Вы увидите, что это как Первая линия наша главная функция, не так ли?
Это проверка того, если у нас есть правильное количество аргументов.
Так что, если вам интересно, если RC правильно,
Вы можете сделать что-то так же, как для печати RC.
RC равен двум, который что мы ожидали, не так ли?
>> Так, мы можем идти дальше, и продолжать до конца.
Так, у нас есть некоторые клавиши там.
И мы можем распечатать наш ключ чтобы убедиться, что это правильно.
Интересно.
Не совсем то, что мы ожидали.
Так, одна вещь, чтобы понять, с GDB также, является
что это не пока вы не попали Далее, что линия, что вы только что видели
на самом деле выполнены.
Так, в этом случае ключ не был назначен еще.
Так, Key некоторое значение мусора что вы видите на дне там.
Отрицательный $ 120-- --Она ​​одного миллиарда и что-то странные вещи правильно?
Это не тот ключ, который мы ожидали.
Но если мы попали Далее, а затем мы попробуйте и ключ печати, это три.
>> Все это видели?
Так что, если вы получаете что-то что вы, как, ждать.
Это полностью не так, и я не знаю,
как это будет происходить, потому что все, что я хочу сделать, это назначить номер, переменная,
попробуйте нажать Далее, попробуйте печать это снова, чтобы увидеть, если это работает.
Потому что это только собирается выполнить и фактически назначить что-то после вас
хит Далее.
Сделать смысл для всех?
Угу?
>> СПИКЕР 2: Когда вы случайным номера, что это значит?
>> СПИКЕР 1: Это просто случайный.
Это просто мусор.
Это просто что-то, что ваш Компьютер случайным образом присвоить.
Прохладный.
Итак, теперь мы можем двигаться через, и так Теперь у нас есть этот простой текстовый GetString.
Итак, позвольте мне просто ввести что произойдет, когда мы попали Далее здесь.
Наша GDB вид исчезает, не так ли?
Это потому, что GetString Теперь выполнение, не так ли?
Так, когда мы увидели обычный текст равен GetString, открытые круглые скобки и круглые скобки,
и мы попали Далее, что имеет фактически выполнено сейчас.
Так, он ждет нам входного что-то.
>> Так, мы собираемся ввести нашу еду, которая является то, что он терпит неудачу, как я сказал вам,
и что как раз говорит, что это закончил работу, что закрыты
Кронштейн означает, что это выхода из этого цикла.
Так, мы можем ударить Далее, и сейчас, как я что вы все знакомы с Цезарем,
это, что эта линия собирается делать.
Это для Int я равна 0, N равен STRLEN, простой текст, а затем
Я меньше п, я, плюс, плюс.
Что это петля собираетесь делать?
Откройте ваше сообщение.
Прохладный.
Так, давайте начнем это делать.
>> Так, если это условие совпадают, для нашего первого?
Если это B, это обычный текст И. Мы можно получить информацию о наших местных жителей.
Таким образом, я равен нулю, а если шесть, который мы ожидаем, и наш ключ три.
Все, что имеет смысл, не так ли?
Эти цифры все именно то, что они должны быть.
Так, напевать?
СПИКЕР 3: У меня есть случайные числа для шахты.
СПИКЕР 1: Ну, мы можем check-- --Мы может поговорить о том, что в одну секунду.
Но вы должны получать это.
Так что, если у нас есть капитал В нашей первой,
это условие должно поймать его, не так ли?
Так что, если мы попали Далее, мы видим, что это Если на самом деле выполняет.
Потому что, если вы следуете вместе в коде,
эта линия здесь, где обычный текст я заменяется этой арифметики,
выполняется только в If условие правильного право?
>> GDB только собираюсь показать вам, вещи, которые на самом деле исполнители.
Так что если это условие Если не было выполнено, это просто хочу, чтобы перейти к следующей строке.
Хорошо?
Так, у нас есть что.
Этот кронштейн означает, что это закрыт из этой петли теперь.
Так, он собирается начать снова.
Так же, как, что.
Так, что мы можем получить информацию о наших местных жителей здесь,
и мы видим, что наша первая Письмо изменилось, не так ли?
Это сейчас E, как и должно быть.
Так, мы можем продолжать.
>> И у нас есть этот чек.
И эта проверка должна работать, не так ли?
Это А. Это должно быть изменено три буквы вперед.
Но если вы заметили, мы получить что-то другое.
Таким образом, в этом случае здесь, он поймал это и так эта линия выполнена,
которые изменены наш B. Но, в этом случае здесь,
у нас есть, что он просто пропустил его, и пошел в [? L Сифф. ?]
Так что-то там происходит.
То, что это говорит вам, что, мы знаем, что он должен поймать здесь,
но это не так.
Может кто-нибудь посмотреть, что наш Проблема в том, в этой строке?
Это очень минут, что.
И вы также можете посмотреть на коде.
Он также line-- забыть то, что линия это в there-- но это в [неразборчиво].
Да?
>> СПИКЕР 4: Это на больше чем страницу, если вы читаете это в книге.
СПИКЕР 1: Точно.
Так, отладчик не мог сказать, Вы что, но отладчик
может вам вниз к линии что вы знаете, не функционирует.
И иногда, когда особенно позже в семестр, когда
Вы имеете дело с сотней, с сто несколько строк кода, и вы
не знаю, где это не удается, это отличный способ сделать это.
Так, мы нашли наш ошибка.
Вы можете это исправить в файле, а затем вы можете запустить его снова,
и все будет работать отлично.
И, самое важное, это это может показаться, ОК.
Да.
Прохладный.
Вы знали, что вы ищете.
Таким образом, вы знали, что делать.
>> GDB может быть супер полезно, потому что вас можно распечатать все эти вещи, которые вы
не будет.
Это гораздо полезнее, чем PRINTF.
Как многие из вас использовать как PRINTF отчетности
чтобы выяснить, где ошибка была, не так ли?
Так, с этим, вы не должны продолжать возвращаться,
и нравится комментируя в PRINTF или комментирования,
и выяснить, что Вы должны быть печати.
Это на самом деле просто позволяет пошагово, распечатать вещи
как вы проходите, так, вы можете наблюдать, как они меняются в режиме реального времени,
как вашей программе работает.
>> И для этого надо немного Немного привыкнуть.
Я очень рекомендую просто вид быть немного разочарованы с ним
прямо сейчас.
Если вы проводите час в течение на следующей неделе обучения, как использовать GDB,
Вы избавите себя так много времени в дальнейшем.
И буквально. мы говорим это людям каждый год,
и я помню, когда я взял класс, я был бы, мне будет хорошо.
Нет.
Pset 6 загорелись и я был как, я собираюсь учиться
как использовать GDB, потому что я не знаю, что здесь происходит.
>> Так что, если вы не торопитесь, так использовать его на более мелкие программ
что вы собираетесь быть работать, как работает
через что-то вроде Visionare, как это.
Или, если вы хотите дополнительную практику, я уверен, что Я мог придумать багги программ,
для отлаживать, если вы хотите.
>> Но если вы просто занять некоторое время, чтобы получить привык к нему, просто поиграйте с ним,
это будет действительно служить вам хорошо.
И это действительно один из те вещи, которые вы просто
должны попробовать, и пачкать руки с, прежде чем вы на самом деле понять это.
Я действительно только понял его один раз У меня было отлаживать вещи с ним,
и это гораздо приятнее иметь представление о том, как отлаживать скорее раньше, чем позже.
Хорошо.
Прохладный.
Я знаю, что это вроде как ускоренный курс GDB,
и я, безусловно, работать на получение это смотреть больше в следующий раз.
Прохладный.
>> Так что, если мы вернемся к нашему PowerPoint.
Будет ли это работать?
АДД.
Да.
Хорошо.
Так что, если вы когда-нибудь понадобится любой из те, опять же, есть список.
Так Двоичный поиск, который все помнит великую зрелище Давида
разрывая телефонные книги в половине.
Я действительно не получить телефонные книги больше,
потому как где ты получить телефонные книги в эти дни?
Я действительно не знаю.
Двоичный поиск.
Помнит ли кто- Как бинарный поиск работы?
Любой вообще?
Да?
СПИКЕР 5: Вы знаете, когда Вы смотрите на которых половина
это было бы в, Исходя из этого, и избавиться от другой половины.
>> СПИКЕР 1 Ровно.
Так, бинарный поиск, это отчасти a-- --мы нравится называть это разделяй и властвуй.
Итак, что же вы будете делать это Вы будете выглядеть в середине,
и вы увидите, если он соответствует то, что вы ищете.
А если это не так, то вы пытаетесь выяснить, он собирается оставить
половина или правая половина.
Так, это может быть, если вы ищете на что-то, что это алфавитный,
Вы видите, о.
Приходит ли Эллисон до М?
Да.
Так, мы собираемся посмотрите на первую половину.
>> Или это может быть как с числами.
Все, что вы можете сравнить, это могут быть отсортированы.
Вы можете использовать бинарный поиск на.
Так, кто-нибудь помнит это График или что это такое?
Это асимптотической сложности.
Таким образом, этот график только описывает, как долго он
принимает вас, чтобы решить проблему, как Вы увеличить количество вещей
что вы используете.
>> Так, у нас есть N, который является линейное время.
Если N за два, что немного лучше, еще растет очень быстро.
А потом мы Войдите, который является что мы считаем бинарный поиск.
Если мы замечаем, как вашей проблемы становится намного и намного больше,
Время, которое требуется вам ее решить на самом деле не увеличить, что много.
Это как сопоставимы Здесь в начале.
Ты как, в порядке.
Ничего тут не действительно от того, который мы используем,
но вы выйти на миллион, миллиард.
Вы пытаетесь найти some-- --you're пытаясь найти иголку в стоге сена.
>> Я думаю, что вы хотите эту проблему.
Вы хотите, чтобы эта сложность, а не линейной, поскольку для всех вас
знаю, что вы собирались быть поиск через каждый человек игла, вещь сена,
пытаясь отыскать иголку.
И это не слишком интересно, на мой взгляд.
Я быстро нравится.
Мне нравится эффективным.
И как трудолюбивые студенты вы Ребята, вы знаете, работать умнее,
не сложнее вещь типа, как вам может сделать эти алгоритмы.
>> Так, мы собираемся ходить только через небольшой пример.
Я думаю, что вы, ребята, должны иметь Рука на бинарный поиск,
но в случае, если кто немного нечеткая, хотите, чтобы укрепить его,
мы собираемся, чтобы просто пойти через примера здесь.
Так, мы ищем, если массив содержит семь.
>> Так, первое, что мы делаем, искать в середине, не так ли?
А также вы собираетесь быть кодирования Двоичный поиск в только второй.
Таким образом, это будет весело.
Таким образом, мы с нетерпением в средние маленькие массивы 3.
3 Соответствует ли 7?
Не правда ли.
Это шесть.
Таким образом, это менее или больше, чем семь?
Меньше чем.
Да.
Хорошие парни работы.
Я чувствую, что я хотел, я должен есть конфеты, потому что я
хочу бросить его во дворы.
Это то, что я собираюсь делать на следующей неделе.
Он будет держать вас, ребята резкий.
>> Так, мы выбрасываем, что Первая половина, не так ли?
это было меньше, чем.
мы знаем, что все, на этой левой стороны
будет меньше, чем мы на самом деле ищем.
Таким образом, нет никакой необходимости обратить на это внимание.
Просто забудьте об этом.
Итак, теперь мы смотрим на нашу справа, и мы смотрим на середине там,
и теперь это девять.
Так, 9 is-- --Everyone?
Больше, чем то, что мы ищу, не так ли?
Так, мы собираемся бросить от все вправо.
Вот так.
Теперь, все, что мы остались с одним.
Так мы проверяем, это один, что мы ищем? это.
Мы нашли, что мы хотели.
Таким образом, мы сделали.
Билинейные Поиск.
>> И если вы заметили, мы было семь входов там.
Это только нам, как три раза, но если вы делаете, как миллиард,
Вы, ребята, знаете, сколько шагов было бы принять, если у нас было четыре миллиарда вещи?
Любые догадки?
Это 32.
32 шагов, чтобы найти что-то в четыре миллиарда
элемент массива из степеней двойки.
Так два это 32, это до четырех миллиардов.
>> Так довольно сумасшедшим, как вы все еще в как достаточно небольшого числа шагов
найти что-то в четыре миллиарда элементов.
Так на этой ноте, мы собираюсь кодировать это
так вы, ребята, может на самом деле вид посмотреть, как это работает.
Ладно, так что вы, ребята, можете закодировать.
Я собираюсь позволить вам, ребята говорить на немного.
Познакомьтесь с людьми вокруг вас, что является что кто-то хотел от последней секции.
>> Так что знать людей вокруг вас.
Поговорите для немного.
И все, что я хочу от вас Ребята сейчас просто
попытаться создать набросок псевдокоде.
Хорошо?
Вау.
Все, что я хочу от вас, ребята это ты просто хочу, чтобы заполнить это пока случае.
Так я поставил эти верхняя и нижняя границы которой
представляют собой начало и конец нашего массива.
И вы собираетесь на самом деле цикл по и выяснить
что мы делаем в этом время цикла.
>> Так что если вы можете выяснить out-- меня есть намек there-- каковы дела
что мы имеем здесь?
Так что, если вы хотите, чтобы выяснить, случаи, мы будем псевдокод тех
и тогда мы будем действительно закодировать их.
И это будет, я думаю, мы надеемся, это будет
быть немного легче, чем вы ожидаете.
Потому что это не так уж много кода, на самом деле, что это действительно круто.
>> Мм-хм?
>> СТУДЕНТ: [неразборчиво]?
ПРЕПОДАВАТЕЛЬ: Да.
Существовал что-то найти в середине.
>> СТУДЕНТ: Таким образом, мы можем использовать его.
Хорошо.
>> ПРЕПОДАВАТЕЛЬ: Прекрасно.
Так что первое, что нам нужно сделать.
Так найти середину.
Великая.
Так что у вас есть представление о том, как мы могли бы на самом деле найти середину с кодом?
>> СТУДЕНТ: Да.
п над 2?
ПРЕПОДАВАТЕЛЬ: Так п над 2.
Так что главное помнить, что Ваши верхние и нижние границы изменения.
Мы продолжаем сужая участие из массива мы надеемся.
Так п над 2 будет работать только для первой вещи мы делаем.
Так что, верхний и нижний во внимание, как мы могли бы получить, что средний элемент?
Потому что мы хотим, чтобы середина между верхней и нижней, не так ли?
Мм-хм?
>> СТУДЕНТ: [неразборчиво].
>> ПРЕПОДАВАТЕЛЬ: Итак, мы имеем некоторую середину.
И это будет верхняя плюс ниже более 2.
Удивительный.
Там мы идем.
Одна линия вниз.
Вы, ребята, на вашем пути.
Так что теперь у нас есть наш среднего, то, что мы хотим сделать?
Просто в целом.
Вам не нужно кодировать его.
Да.
СТУДЕНТ: [неразборчиво]?
ПРЕПОДАВАТЕЛЬ: Так что это плюс, потому что ты найти среднее между двумя
из них.
Так что если вы думаете о них, как вид увеличения в с боков,
думаю об этом, когда вы приближаетесь средний, вы хотите так.
Так что, если вы были по обе стороны от средний, и у нас есть как 5 и 7.
При добавлении их вместе вам получить 12, вы разделите на 2, 6.
>> Иногда это трудно объяснить, почему это работает,
но если вы работаете через пример иногда,
это поможет вам понять, если она должна быть плюс или минус.
Да.
>> СТУДЕНТ: [неразборчиво] ровно посередине
если они был случай, когда есть много меньших количествах
и как один большого количества?
>> ПРЕПОДАВАТЕЛЬ: Все, что Вам нужно это середина массива.
Так что, если у вас была куча небольших количествах а затем один действительно большое количество
в конце концов, это не имеет значения.
Все, что имеет значение в том, что они сортируются, вы просто
хочу посмотреть на середине массив, потому что вы все еще
нарезки вашу проблему в два раза.
Прохладный.
Так что теперь у нас есть средний, что мы будем делать дальше?
>> СТУДЕНТ: Сравнение.
ПРЕПОДАВАТЕЛЬ: сравнить.
Так сравнивать средний для value_wanted.
Прохладный.
Итак, вы видите здесь у нас есть это значение мы хотим здесь.
Помните, что это массив.
Так средний относится к индексу.
Таким образом, мы хотим сделать значения середине.
Не забывайте, если вы хотите сравнить, двойные равных.
Вы делаете один равняется вы просто хочу, чтобы переназначить его,
а затем, конечно, это будет значение, которое вы хотите.
Так что не делайте этого.
>> Итак, мы собираемся, чтобы увидеть, если значения в середине
равна стоимости мы хотим.
Не забывайте свои брекеты.
Dropbox должен уйти.
Так что же нам делать в этом случае?
Если это то, что мы хотим вернуться?
Мы пытаемся сказать.
>> СТУДЕНТ: Распечатайте.
>> ПРЕПОДАВАТЕЛЬ: Ну, мы не хочу, чтобы распечатать.
Так что это Ьоо здесь, поэтому мы хочу вернуться истинным или ложным.
Мы говорим, это число [? АСР? ?] Таким образом, если она есть,
мы только что вернулись правда ли.
Если я могу записать верно.
>> СТУДЕНТ: Почему бы вам не вернуться к нулю?
ПРЕПОДАВАТЕЛЬ: Таким образом, вы могли возвратить нуль, если вы хотели.
Но в данном случае, потому что наша функция возвращает логическое значение,
мы должны вернуться истинным или ложным.
СТУДЕНТ: Когда ты говоря логическое выражение,
Вы можете установить его равным ложь?
Как если я хочу сказать, если это условие не выполняется, как это верхняя равняется ложь.
Будет ли это понимать, если вы просто положить ложь на другую сторону?
ПРЕПОДАВАТЕЛЬ: Да.
Так на самом деле, если вы когда-либо что-то делать
как сверху или ниже, что возвращает истину или ложь
и это на самом деле плохой стиль скажем равна равна правда или равных
равняется ложь.
Вы хотите использовать этот результат как сам, как ваш чек.
Не то, что я хотел.
Это то, что я хотел.
Таким образом, в случае, если вы спрашиваете о чем-то, как сохранить это в с.
>> Так что, если у нас есть Int основной (пустоту) и что-то вроде этого.
И у вас есть, если есть верхняя какой вход и ты
с просьбой, если вы можете сделать что-то вроде этого?
Не так ли?
СТУДЕНТ: я пытался сделать это [неразборчиво].
Потому что, если it's--
ПРЕПОДАВАТЕЛЬ: справа.
Итак, вы хотите, чтобы это было ложным, не так ли?
СТУДЕНТ: Да.
ПРЕПОДАВАТЕЛЬ: Так что в этом случае вы хочу, чтобы это выполнить, если это не так.
Так здорово, что у вас там такое.
Так что помните восклицание Точка отрицает вещи?
Это говорит [неразборчиво] означает не.
Так что, если мы посмотрим на только что эта часть здесь, вы бы
сказать, что имеет значение ложь, как вы хотите, чтобы он.
Не ложное истинно, которые значит это выполнить.
Имеет ли это смысл?
СТУДЕНТ: Да.
ПРЕПОДАВАТЕЛЬ: Awesome.
Хорошо.
Таким образом, мы могли бы просто вернуться правда в этом случае.
Так что теперь у нас есть два других случаев в этом случае.
Каковы наши два других случая?
Давайте просто делать это таким образом.
Итак, давайте начнем с еще если значения в середине
меньше, чем значение мы хотим.
Таким образом, наша ценность в середине меньше чем значение, что мы ищем.
>> Итак, какие границы сделать вас думаю, что мы хотим, чтобы обновить?
Верхний или нижний?
Верхний?
Так на чьей стороне массива мы собираемся быть глядя на?
>> СТУДЕНТ: Нижний.
>> ПРЕПОДАВАТЕЛЬ: Мы будем чтобы смотреть на левой.
Так еще, если мало значение меньше.
Так вашем среднего значения здесь меньше, чем то, что мы хотим.
Поэтому мы хотим, чтобы взять Правая сторона массиве.
Таким образом, мы собираемся обновить наш нижняя граница.
Таким образом, мы будем переназначать нашего ниже.
И что вы думаете ниже должна быть?
СТУДЕНТ: среднее значение?
ПРЕПОДАВАТЕЛЬ: Так средний value--
СТУДЕНТ: Плюс 1.
ПРЕПОДАВАТЕЛЬ: --plus 1.
Может кто-нибудь сказать мне, почему у нас есть, что плюс 1?
>> СТУДЕНТ: [? Нет значения?] Более равна ей.
>> ПРЕПОДАВАТЕЛЬ: справа.
Потому что мы уже знаем, что наша среднее значение не равно
это, и мы хотим, чтобы исключить его от всех последующих поисков.
Если вы забыли, что плюс 1, это понравится цикл бесконечно.
И вы просто попасть в бесконечный цикл, а затем вы будете сегментации
и дела идут плохо.
Так всегда убедитесь, что вы не в том числе значение, что вы только что
посмотрел на.
Таким образом, мы заботимся о том, что с плюсом 1.
>> Так что теперь у нас есть последнее условие которые я всегда ради безопасности
Вы можете проверить здесь, иначе, если значение в средний больше, чем значение
мы хотим.
Это означает, что мы хотим левая рука наполовину.
Так какой из них мы собираемся обновить?
Верхний.
И что это за один собирался равняться?
Средний минус 1, потому что, Конечно, мы хотим,
чтобы убедиться, что мы не глядя на этого среднего значения снова.
А то у нас его.
Это так.
Вот и все, бинарный поиск.
Это не так уж плохо, не так ли?
Это как 10 строк Код с пробелами.
Так, очень мощный, очень полезно, вы будете быть с использованием его в одном из ваших последующих psets.
Может быть, это не один, но позже.
Так изучать его.
Люблю это.
Это будет относиться к вам хорошо.
Так кто-нибудь есть какие-либо вопросы по бинарного поиска?
Да.
>> СТУДЕНТ: это имеет значение ли ли ваш н четным или нечетным?
>> ПРЕПОДАВАТЕЛЬ: Нет.
Потому что мы бросили его в середину, как INT, это будет просто обрезать его.
Так он будет оставаться целое, и это будет в конце концов разобраться в всем.
Таким образом, вы не должны беспокоиться об этом.
Все хорошо?
Удивительный.
Прохладный.
Так, вы, ребята, получил это.
Слайд-шоу.
Так как мы говорим о, я знаю, Дэвид упомянул сложности автономной работы.
>> Таким образом, в лучшем случае, это просто один, который мы называем постоянное время.
Может кто-нибудь сказать мне, почему это может быть?
Какой тип сценария будет, что влечет за собой?
Мм-хм.
>> СТУДЕНТ: [неразборчиво] first--
ПРЕПОДАВАТЕЛЬ: Так средний являясь Первый элемент, который мы подходим к, не так ли?
Так что либо массив из одного или все, что мы ищем только
случается, прямо по середине.
Так что это наш лучший случай.
Вы получаете в реальных проблем, вероятно, не собирается достичь [неразборчиво], что часто.
А как насчет нашей худшем случае?
Наш худший случай журнала н.
И что должен делать со всем Полномочия два вещи, которые я говорил о.
>> Таким образом, в худшем случае это будет означать, что мы должны были нарезать массив вниз
пока он не был элементом один.
Так что нам пришлось колоть его пополам столько раз, сколько мы возможно могли.
Вот почему это журнал н потому Вы просто разделять на два.
Так предположения, вещи, которые вы нужно знать, если вы когда-либо
собираетесь использовать бинарный поиск.
Ваши элементы должны быть отсортированы.
Они должны быть отсортированы, потому что это единственный способ
может знать, если вы сможете выкинуть половину из него.
>> Если у вас это перемешаны мешок чисел и вы говорите,
ОК, я собираюсь проверить середину Количество и число Я ищу
меньше, чем, я просто хочу, произвольно выкинуть половину.
Вы не знаете, если ваша Цифры в этой другой половине.
Ваш список должен быть отсортирован.
Кроме того, это может быть идти вперед немного,
но вы должны иметь произвольный доступ.
Вы должны быть в состоянии просто перейти на эту среднего элемента.
Если у вас есть, чтобы пройти через что-то
или это займет у вас дополнительные шаги чтобы добраться до этого среднего элемента,
это не войти н больше, потому что Вы добавляете больше работы в нем.
И это сделает немного больше смысла в две недели,
но я только отчасти хотел бы предварить, дать вам, ребята представление о то, что
прийти.
Но те два важные допущения
что вам нужно для бинарного списка.
Убедитесь, что он отсортирован.
Это большой для Вы, ребята, прямо сейчас.
И на что мы можем пойти в Остальные наши сортов.
Так четыре sorts-- пузырь, вставка, выбор, и слияние.
Они все круто.
Если вы, ребята, решили взять CS 124, Вы узнаете о всевозможных сортов.
И если вы поклонник XKCD, есть это действительно здорово комикс про
как действительно неэффективных видов, которые я очень рекомендую вам идти смотреть.
Одним из них является, как паническое рода, которые как, ой нет, вернуть массив случайных.
Shutdown система.
Оставьте.
Так вызывающим юмор всегда хорошо.
>> Так кто-нибудь помнит вид из как только общее представление
о том, как работает пузырьковой сортировки.
Вы помните?
>> СТУДЕНТ: Да.
>> ПРЕПОДАВАТЕЛЬ: Пойти на это.
>> СТУДЕНТ: Так что вы собираетесь через и если он больше, то нужно поменять местами два.
>> ПРЕПОДАВАТЕЛЬ: Мм-хм.
Точно.
Таким образом, вы просто перебрать.
Вы проверить два числа.
Если один перед больше чем тот, впоследствии,
Вы просто обменять их таким образом, чтобы в Таким образом, все более высокими номерами
пузырь вверх к концу списка и все меньшее число пузырь вниз.
>> Он покажет вам, ребята здорово звуковой эффект сортировка видео?
Это круто.
Так как Роберт просто сказал, алгоритма что вы просто перемещаться по списку,
обмен соседние значения если они не в порядке.
А потом просто повторять пока вы не делать какие-либо свопы.
Так не плохо, не так ли?
Так что мы просто иметь быстрый пример.
Так это будет сортировать их в порядке возрастания.
Поэтому, когда мы проходим через первый Время, мы смотрим через восемь
и шесть, очевидно, не для того, что мы поменять их местами.
>> Так что смотрите на следующей.
Восемь и четыре не в порядке.
Поменять их.
А потом восемь и два, поменять их местами.
Там мы идем.
Таким образом, после первого прохода, вы знаете, что ваш самый большой номер
будет полностью в верхней, потому что это просто
будет постоянно больше, чем все остальное
и это только собирается пузыря всю дорогу до конца там.
Значит ли это, имеет смысл для всех?
Прохладный.
>> Итак, мы смотрим на нашу втором проходе.
Шесть и четыре, переключатель.
Шесть и два, переключатель.
И теперь у нас есть несколько вещей в порядке.
Таким образом, для каждого прохода, что мы сделать через весь наш список,
мы знаем, что, как, что многие номера в конце будет были отсортированы.
Так мы делаем третий проход, который является одним подкачки.
И тогда на наш четвертый пройти, у нас есть нулевые слотов.
И поэтому мы знаем, что наш массив был отсортирован.
>> И это большая вещь с пузырьковой сортировки.
Мы знаем, что, когда мы имеют нулевые свопы, что
означает, что все, находится в полном порядке.
Это своего рода, как мы проверяем.
Таким образом, мы также собираемся кодировать пузырь рода, которые также не в том, что плохо.
Ни один из них не так уж плохо.
Я знаю, что они могут показаться немного страшно.
Я знаю, когда я взял класс, даже когда я
преподавал класс для первый раз в прошлом году,
Я был, как, как я могу это сделать?
Это имеет смысл в теории, но как мы на самом деле это сделать?
Именно поэтому я и хочу, чтобы идти через код с вами, ребята здесь.
Так что у меня псевдокод для вас, ребята на этот раз.
Так что имейте это в виду, как мы собираемся перейти в течение.
Поэтому у нас есть какой-нибудь счетчик, что отслеживает наши свопы,
потому что нам нужно, чтобы убедиться, что мы проверяем, что.
И мы итерации весь массив как мы только что сделали с этим примером.
Если элемент, прежде чем больше элемент после, где мы находимся,
мы обменять их и мы увеличиваем OUR Счетчик потому что как только мы поменять,
мы хотим, чтобы наш счетчик знаю, что.
Любые вопросы есть?
Что-то, кажется, смешно здесь.
СТУДЕНТ: Вы установить счетчик на ноль каждый раз, когда вы идете через петлю?
Вы не продолжать назад к нулю каждый раз?
ПРЕПОДАВАТЕЛЬ: Не обязательно.
Так что же происходит у нас пройти здесь.
Так что в то время, помните, что это будет выполнять один раз в обязательном порядке.
Так это будет установлено счетчик равен нулю,
то это будет для перебора.
Как оно проходит по, она обновит счетчик.
Как он обновляет счетчик, когда это будет сделано, когда он достиг конца массива,
если наш список не отсортирован, Счетчик были обновлены.
>> Так то оно проверяет состояние и говорит, хорошо, это счетчик больше нуля.
Если это так, сделать это снова.
Вы хотите сбросить, так что, когда вам пройти через, счетчик равен нулю.
Если вы идете через отсортированный Массив, ничего не меняется,
это не удается, и вы вернуться отсортированный список.
Значит ли это, имеет смысл?
СТУДЕНТ: Это может в немного.
ПРЕПОДАВАТЕЛЬ: ОК.
Если есть какая-либо другая Вопрос, который приходит.
Да.
>> СТУДЕНТ: Что бы функция быть для перекачки элементы?
>> ПРЕПОДАВАТЕЛЬ: Таким образом, мы можем на самом деле писать что если мы собираемся прямо сейчас.
Прохладный.
Так на этой ноте, Элисон собирается Чтобы вернуться обратно в прибор.
Это будет весело.
И у нас есть наш славный пузырьковая сортировка вещь здесь.
Так что я уже сделал на велосипеде через массив.
У нас есть наши свопы, которые равны нулю.
Поэтому мы хотим, чтобы поменять прилегающих элементы, если они вышли из строя.
Поэтому первое, что мы должны делаем, перебора нашего массива.
>> Итак, как вы думаете, мы могли бы перебора нашего массива?
У нас есть для, и я равна 0.
Мы хотим, чтобы я быть меньше чем п минус 1 минус к.
И я объясню, что в секунду.
Так что это оптимизация здесь, где, помню, как я сказал, после каждого прохода
через массив мы знаю, что все, что это on--
>> Таким образом, после одного прохода мы знаю, что это сортируется.
После двух проходов мы знаем что все это сортируется.
После трех проходов мы знаю, что это сортируются.
Так Кстати я итерации через массив здесь,
будет это делать обязательно идти только через то, что мы знаем, это несортированный.
Хорошо?
Вот только оптимизация.
Вы могли бы написать его наивно просто перебора всего,
это было бы просто занять больше времени.
С этого четыре цикла это просто хороший оптимизация
потому что мы знаем, что после того, как каждый полный итерации по массиву здесь,
как каждый полный петли здесь, мы знаем, что более из этих элементов одного
будут отсортированы в конце.
>> Таким образом, мы не должны беспокоиться о них.
Значит ли это, имеет смысл для всех?
Это здорово маленькая хитрость?
Таким образом, в этом случае, если мы итерации,
мы знаем, что мы хотим, чтобы проверить, Массив п и п + 1 в порядке.
Хорошо.
Так вот псевдокод.
Мы хотим, чтобы проверить, если массив н и н плюс 1 в порядке.
Так что, возможно, у нас там?
Это будет какой-то условный.
Это будет, если.
>> СТУДЕНТ: Если массив п менее массива н плюс 1.
ПРЕПОДАВАТЕЛЬ: Мм-хм.
Ну, меньше или больше, чем.
СТУДЕНТ: Больше.
Тогда мы хотим поменять их местами.
Точно.
Так что теперь мы попадаем в то, что Механизм для перекачки их?
Таким образом, мы прошли через эту кратко, тип функции подкачки на прошлой неделе.
Кто-нибудь помнит, как он работал?
Таким образом, мы не можем просто передать их, не так ли?
Потому что один из них будет теряться.
Если мы сказали, равна Б, а тот равна A, все внезапно оба
просто равна B.
>> Итак, что мы должны сделать, это мы есть временную переменную вот
собирается провести один из наших-то время мы находимся в процессе перекачки.
Так что у нас есть, мы будем иметь некоторое Int Температура равна to-- можно назначить
в зависимости от того, что вы хотите, просто убедитесь, что вы отслеживать it--
поэтому в данном случае, я собираюсь назначить его на массиве н плюс 1.
Так что происходит, чтобы вместить все Значение в этом втором блоке
что мы смотрим на.
>> И тогда мы можем сделать, это мы можем пойти вперед, а также переназначать массив н плюс 1,
потому что мы знаем, что есть это значение хранится.
Это также является одним из большой things-- Я не знаю, если кто из вас
были проблемы, когда при переключении два строк кода вдруг все работало.
Заказать очень важно в CS.
Поэтому убедитесь, что вы диаграмме вещи, если это возможно
относительно того, что происходит на самом деле.
Так что теперь мы собираемся переназначить массива п плюс 1,
потому что мы знаем, что есть это значение хранится.
>> И мы можем назначить, что в массиве н а в данном случае массив я.
Слишком много переменных.
Хорошо.
Так что теперь мы переведены массив, который я плюс 1 равным, что находится в массиве I.
И теперь мы можем вернуться и назначить массив я к чему?
Любой?
>> СТУДЕНТ: 10.
>> ПРЕПОДАВАТЕЛЬ: 10.
Точно.
И последнее.
Если мы поменялись это сейчас, Что мы должны сделать?
Что одно дело что собирается рассказать нам
если мы когда-либо прекратить эту программу?
Что говорит нам, что мы есть отсортированный список?
Если мы не выполняют никаких свопов, не так ли?
Если свопы равна нулю в конце этого.
Поэтому, когда вы выполнить обмен, как мы только что сделал здесь, мы хотим обновить свопы.
И я знаю, что было Вопрос ранее о можешь
использовать ноль или один, а из истинными или ложными.
И вот что это делает здесь.
Таким образом, это говорит если не свопы.
Так что, если свопы равна нулю, что is-- я всегда получить мои истины и мои falses перепутали.
Мы хотим, чтобы нам оценить чтобы верно и это не так.
Так что, если это ноль, то это ложь.
Если вы отрицать его [? бац?] становится правдой.
Итак эта линия выполняет.
>> Истины и ложь, и нули и единицы получить с ума.
Просто, если вы медленно ходить через него будет иметь смысл.
Но вот что это немного кусок кода здесь делает.
Таким образом, это проверяет, мы сделали никаких свопов.
Так что, если это что-нибудь, кроме нулю, это будет ложь
и все это является собирается выполнить снова.
Прохладный?
>> СТУДЕНТ: Что перерыв сделать?
>> ПРЕПОДАВАТЕЛЬ: Перерыв просто ломает тебя из петли.
Таким образом, в данном случае это было бы так же, как завершить программу
и вы бы просто есть свой отсортированный список.
СТУДЕНТ: Восхитительно.
ПРЕПОДАВАТЕЛЬ: Я сожалею?
СТУДЕНТ: Потому что раньше мы б написал 1 над написана нулю
представить, что если что будет работать или нет.
>> ПРЕПОДАВАТЕЛЬ: Да.
Таким образом, вы можете вернуться к нулю или 1.
В этом случае, потому что мы на самом деле не делать что-либо с помощью функции,
мы просто хотим, чтобы сломать.
Мы действительно не заботятся об этом.
Тормозная также хорошо, если он используется для выхода из
из четырех петель или условий, которые Вы не хотите, чтобы выполнение.
Это займет вас из них.
Это что-то вроде нюанс вещи.
Я чувствую, что есть много ручной завивки,
как вы узнаете об этом в ближайшее время.
>> Но вы узнаете об этом в ближайшее время.
Я обещаю.
Хорошо.
Так же все получают пузырьковой сортировки?
Не слишком плохо.
Перебора, своп вещи с помощью Переменная температура, и мы все же тут?
Прохладный.
Удивительный.
Хорошо.
Вернуться к PowerPoint.
Любые вопросы в целом о них до сих пор?
Прохладный.
Мм-хм.
>> СТУДЕНТ: [неразборчиво] Int основной обычно.
Вы должны иметь, что для этого?
>> ПРЕПОДАВАТЕЛЬ: Таким образом, мы просто искали просто по фактической алгоритма сортировки.
Если вы имели его в течение как большой программы,
Вы бы иметь Int основной где-то.
В зависимости от того, где вы использовать этот алгоритм,
было бы определить, что возвращается к ней.
Но для нашего случая, мы строго глядя на то, как это делает на самом деле
перебора массива.
Таким образом, мы не беспокоиться об этом.
>> Таким образом, мы говорим о лучшем случае и худшие сценарии для бинарного поиска.
Так что это также важно сделать что для каждого из наших сортов.
Так что вы думаете, это худший Дело времени выполнения пузырьковой сортировки?
Вы, ребята, помните?
>> СТУДЕНТ: N минус 1.
ПРЕПОДАВАТЕЛЬ: N минус 1.
Значит, есть н минус 1 сравнения.
Так одно дело понимать, что на первой итерации,
мы идем до конца, мы сравним эти two-- так вот 1.
Эти два, три, четыре.
Таким образом, после одной итерации мы уже есть четыре сравнений.
Когда я говорю о времени выполнения и п.
N представляет собой количество сравнений как функция от того, сколько элементов
у нас есть.
Хорошо?
>> Так мы идем до конца, у нас есть четыре.
В следующий раз, вы знаете, мы не должны позаботиться об этом.
Мы сравниваем эти два, эти двое, эти двое,
и если у нас не было, что оптимизация с четырьмя петли, что я написал,
Вы бы сравнивать здесь в любом случае.
Таким образом, вы должны были бы запустить через массив
и сделать п сравнений н раз, потому что каждый раз, когда мы
запустить через это мы вроде одно.
>> И каждый раз, когда мы сталкиваемся с помощью массив, мы делаем п сравнений.
Таким образом, наша среда для этого на самом деле н квадрат, который
гораздо хуже, в нашем войти конце, потому что, что
значит, если у нас было четыре миллиард элементы, это
собирается взять нас четыре миллиарда квадрат вместо 32.
Так не лучше среда, но для некоторых вещей,
Вы знаете, если вы в течение определенный диапазон элементов
пузырьковая сортировка может быть штраф, чтобы использовать.
>> Хорошо.
Так что теперь, что это лучший случай выполнения?
СТУДЕНТ: Ноль?
Или 1?
>> ПРЕПОДАВАТЕЛЬ: Так 1 будет одним сравнение.
Право.
>> СТУДЕНТ: N минус 1?
>> ПРЕПОДАВАТЕЛЬ: Так что, да.
Так н минус 1.
Всякий раз, когда у вас есть такое понятие, как п минус 1, мы, как правило, просто высадить его
и мы просто скажем, п, потому что вы есть сравнить каждый из these-- каждой пары.
Поэтому было бы н минус 1, который мы мы просто скажем, примерно н.
Когда вы имеете дело с выполнения, все в приближает.
До тех пор, как экспонента правильно, вы очень хорошо.
>> Вот как мы с ней боремся.
Так что в лучшем случае это п, означает, что список уже отсортирован,
и все, что мы сделать, это запустить через и убедитесь, что это сортируются.
Прохладный.
Хорошо.
Итак, как вы видите здесь, мы просто есть еще несколько графиков.
Так п квадрат.
Fun.
Гораздо хуже, чем п, как мы видим, и гораздо, гораздо хуже, чем журнала 2n.
И тогда вы также получаете в журналах журналов.
И вы берете 124, вы получите в как лог звезды, которая, как сумасшедший.
Так что если вы заинтересованы, поиск журнала звезда.
Это забавно.
Поэтому у нас есть этот великий график.
Просто головы, это замечательный график, чтобы иметь
для среднесрочной перспективе, потому что мы долго бы задать вам эти редеет.
Так просто головы, есть это на Среднесрочный на хорошем шпаргалку
есть.
Таким образом, мы просто смотрели на пузырьковой сортировки.
В худшем случае, п квадрат, лучший случай, п.
И мы собираемся смотреть на других.
>> И как вы можете видеть, только тот, который действительно хорошо
является сортировка слиянием, которые мы получим в почему.
Итак, мы собираемся пойти в Следующий here-- выбор рода.
Помнит ли кто-нибудь, как Выбор рода работал?
Пойти на это.
>> СТУДЕНТ: В основном идут через Порядок и создать новый список.
И так же, как вы кладете элементы в, положить их в правильном месте
в новом списке.
>> ПРЕПОДАВАТЕЛЬ: Так что звуки больше похоже вставки рода.
Но вы действительно близки.
Они очень похожи.
Даже я путаю иногда.
Перед этой части я был как, ждать.
Хорошо.
Так что вы хотите сделать выбор рода,
как вы можете думать, об этом и пути
Я убеждаюсь, что стараюсь не получить путаю, это проходит через
и он выбирает наименьшее число, и это
ставит, что в начале списка.
Это меняет его с той первой месте.
Они на самом деле есть пример для меня.
Удивительный.
Так просто способ думать о it-- выбора рода, выберите наименьшее значение.
И мы собираемся проходят через примера
что я думаю, что поможет, потому что Я думаю, что визуальные всегда помочь.
Итак, мы начинаем с чем-то что полностью без сортировки.
Красный будет несортированный, зеленый будут отсортированы.
Это все будет иметь смысл в секунду.
>> Таким образом, мы пройти и мы итерации от начала и до конца.
И мы говорим: ОК, 2 наш маленький номер.
Таким образом, мы собираемся взять 2, и мы собираемся чтобы переместить его на фронт нашего массива
потому что это Наименьшее число у нас есть.
Так вот что это делает здесь.
Это просто будет поменять эти два.
Так что теперь мы сортируются часть и несортированный часть.
И то, что хорошо помнить о выборе рода
это мы только выбора от неотсортированной части.
>> Отсортированный часть вы просто оставить в покое.
Мм-хм?
>> СТУДЕНТ: Как это знаю, что это самый маленький, не сравнивая его
к каждому другому значению в массиве.
ПРЕПОДАВАТЕЛЬ: Он делает сравнить его.
Нам нравится пропустил его.
Это просто вообще в целом.
Да.
Когда мы пишем код, я что вы будете более удовлетворены.
Но вы храните этот первый Элемент как наименьшее.
Вы сравните, и вы сказать, в порядке, это меньше?
Да.
Держите его.
Вот это меньше?
Нет?
>> Это ваш маленький, переназначить его на значение.
И вы будете гораздо счастливее когда мы идем через код.
Так мы идем до конца, мы поменять его, так то мы смотрим на этот несортированным части.
Итак, мы собираемся, чтобы выбрать три отъезде.
Мы собираемся поставить его на на конец отсортированного нашей части.
И мы просто будем продолжать делать что, делая это, и делать это.
Так что это наш вид псевдокоде здесь.
Мы закодировать его здесь в секунду.
Но только что-то ходить через на высоком уровне.
Вы собираетесь перейти от я равна от 0 до н минус 2.
Это еще одна оптимизация.
Не волнуйтесь об этом слишком много.
Итак, как вы говорили.
Как говорил Иаков, как мы отслеживать то, что наш минимум?
Как мы знаем?
Мы должны сравнить все в нашем списке.
>> Так минимальная равна я.
Это просто говорю в данном случае Индекс нашей минимального значения.
Итак, что это собирается перебора и она идет от J равна я плюс 1.
Таким образом, мы уже знаем, что это наш первый элемент.
Нам не нужно, чтобы сравнить его с себя.
Таким образом, мы начинаем сравнивать его с рядом один, который является, почему это я плюс 1 до п
минус 1, которое является конец массива там.
И мы сказали, что если массив на J является менее массива мин,
Затем мы переназначить где наши минимальные показатели является.
>> И если мин не равен I, как в котором мы уже были здесь.
Так как когда мы впервые сделали это.
В этом случае, было бы начать с нулю, это будет в конечном итоге два.
Так мин не будет равна я, в конце концов.
Это позволяет нам знать, что мы должны поменять их местами.
Я чувствую, что на конкретном примере поможет гораздо больше, чем это.
Так что я буду кодировать это с вами, ребята прямо сейчас, и я думаю, что это будет лучше.
>> Сорта, как правило, работает таким образом в том, что это часто лучше просто увидеть их.
Итак, что мы хотим сделать, это сначала мы хотели наименьшая
элемент в его позиции в массиве.
Именно то, что Иаков говорил.
Вы должны сохранить что-то.
Таким образом, мы собираемся начать здесь итерации по массиву.
Мы собираемся сказать, что это наш Первый раз, чтобы начать с.
Таким образом, мы будем иметь Int маленький равна массива в I.
>> Так что, одно заметить, каждый Время это цикл выполняется,
мы начинаем еще один шаг вперед вместе.
Когда мы начинаем смотреть на этот.
В следующий раз мы перебора, мы начинаем в этом
и присвоения его нашим наименьшее значение.
Так что это очень похоже на пузырьковой сортировки где мы знаем, что после одного прохода,
это последний элемент сортируется.
С выбора рода, это как раз наоборот.
>> На каждом проходе, мы знаем, что Первый сортируется.
После второго прохода, Вторая будут отсортированы.
И, как вы видели на примерах слайд, наша сортируются часть просто продолжает расти.
Так, установив наш маленький друг для массивов я, все, что он делает
является сжимая что мы смотрим на того,
чтобы свести к минимуму количество сравнений мы делаем.
Имеет ли это смысл для всех?
Вам нужен мне, чтобы пробежать, что снова медленнее или разными словами?
Я счастлив.
Хорошо.
>> Таким образом, мы хранения Значение в этом пункте,
но мы также хотим, чтобы хранить индекс.
Итак, мы собираемся хранить Положение наименьшая
один, который только собирается быть, я.
Так что теперь Иаков удовлетворен.
У нас есть вещи, хранящиеся.
И теперь мы должны смотреть через без сортировки часть массива.
Таким образом, в данном случае это будет наша несортированный.
Это я.
Хорошо.
>> Итак, что мы собираемся сделать будет для петли.
Всякий раз, когда вам нужно перебора массива,
Ваш ум может пойти для петли.
Таким образом, для некоторых Int к equals-- что мы думаем
К собирается равняться начать?
Это то, что мы поставили как наша маленькая ценность, и мы хотим, чтобы сравнить его.
Что мы хотим, чтобы сравнить его с?
Это собирается быть это следующий, не так ли?
Поэтому мы хотим, K, чтобы инициализировать чтобы я плюс 1, чтобы начать.
>> И мы хотим, чтобы к в этом случае мы уже размер хранятся здесь,
так что мы можем просто использовать размер.
Размер будучи размер массива.
И мы просто хотим, чтобы обновить K на единицу каждый раз.
Прохладный.
Так что теперь мы должны найти наименьший элемент здесь.
Так что, если мы перебора, мы хочу сказать, если массив на к
меньше нашего маленького value-- это где мы на самом деле
отслеживания того, что это самый маленький here--
Затем мы хотим передать что наша маленькая величина.
>> Это означает, что, ну, мы перебора здесь.
Независимо от значение здесь не наш маленький вещь.
Мы не хотим его.
Мы хотим, чтобы переназначить его.
Так что, если мы переназначение его, что делать Вы думаете, может быть в этом коде здесь?
Мы хотим, чтобы переназначить маленький и положение.
Так что это самый маленький в настоящее время?
СТУДЕНТ: Array к.
ПРЕПОДАВАТЕЛЬ: Array к.
И то, что это положение сейчас?
Что индексы наша наименьшее значение?
Это просто к.
Так массива К, К, они совпадают.
Таким образом, мы хотели передать это.
А потом, когда мы обнаружили, что наш маленький, так в конце этого для петли
Здесь мы нашли то, что наш маленький значение, так что мы просто поменять его.
В этом случае, как говорят наши Наименьшее значение здесь.
Это наша наименьшее значение.
>> Мы просто хотим, чтобы поменять его здесь, который является что это функция подкачки на дне
сделал, который мы только что написали вместе пару минут назад.
Так оно и должно выглядеть знакомым.
И тогда это будет просто перебирать через пока он не достигнет упора
до конца, а это значит, что вас имеют нулевые элементы, которые без сортировки
а все остальное было разобраться.
Сделать смысл?
Чуть более конкретно?
Код помощь?
>> не СТУДЕНТ: Для размера, вы никогда действительно определить или изменить его,
как это узнать?
>> ПРЕПОДАВАТЕЛЬ: Так одно дело заметить здесь является размер внутр.
Так мы говорим в этом sort-- рода есть функция в этом case-- это
Выбор рода, он прошел В с функцией.
Так что, если он не был принят в, вы могли бы сделать что-то
как с длиной массива или вы бы перебора
чтобы найти длину.
Но потому что это прошло в, мы можем просто использовать его.
Вы просто предположим, что пользователь дал вам правильный размер, что
на самом деле представляет размер вашего массива.
Прохладный?
>> Если вы, ребята, есть какие-либо проблемы с этим или хотите больше практики кодирования виды
по своему усмотрению, вы должны перейти к study.cs50.
Это инструмент.
У них есть проверки, что Вы можете фактически писать.
Они делают псевдокод.
Они имеют больше видео и слайды в том числе и я использую здесь.
Так что если вы все еще чувствуете немного нечеткой, попробуйте это.
Как всегда, пришел поговорить со мной, тоже.
Вопрос?
>> СТУДЕНТ: Вы хотите сказать, размер определено ранее?
ПРЕПОДАВАТЕЛЬ: Да.
Размер предварительно определена с точностью здесь в объявлении функции.
Таким образом, вы предположить, что это было принято в пользователем, и для простоты,
мы будем считать, что Пользователь дал нам правильный размер.
Прохладный.
Так вот выбор рода.
Ребята, я знаю, сегодня мы узнали много.
Это плотная данные для раздела.
Так с этим, мы собираемся пойти в сортировку вставками.
>> Хорошо.
Поэтому, прежде чем, что мы должны сделать, наш анализ выполнения здесь.
Таким образом, в лучшем случае, предоставляется, так как я показал вам,
таблица я уже вид отдал его.
Но лучше всего дело времени выполнения, что мы думаем?
Все отсортировано.
N в квадрате.
Любой, есть объяснение почему вы думаете?
>> СТУДЕНТ: вы сравниваете through--
ПРЕПОДАВАТЕЛЬ: справа.
Ты сравнения через.
На каждой итерации, несмотря на то, мы уменьшая это один,
Вы все еще ищете через все, чтобы найти самые маленькие.
Таким образом, даже если ваша наименьшее значение Здесь в начале,
Вы все еще сравнивая его против всего остального
чтобы убедиться, что это самое малое.
Таким образом, вы будете в конечном итоге работает через примерно н квадрате раз.
Хорошо.
И то, что в худшем случае?
Также п квадрате, потому что вы собираетесь чтобы делать ту же самую процедуру.
Так, в данном случае, выбор вроде есть что-то
что мы называем ожидаемое время выполнения.
Таким образом, в других, мы просто знаем, верхние и нижние границы.
В зависимости от того, как с ума нашего Список или как несортированный это,
они различаются между п или п квадрата.
Мы не знаем.
>> Но из-за выбора рода имеет то же самое худшее и лучшее дело, что говорит нам, что
независимо от того, какой тип ввода мы есть, является ли это полностью
сортируются или полностью обратная сортируются, это
собирается взять такое же количество времени.
Так что в этом случае, если вы помните из нашей таблицы,
он на самом деле имеет значение, что эти два вида не имеют,
который, как ожидается, во время выполнения.
Итак, мы знаем, что всякий раз, когда мы бежим выбора рода,
это гарантированно запустить н квадрате время.
Там нет изменчивость есть.
Это просто ожидал.
И, опять же, если вы хотите узнать, Более того, принять CS 124 весной.
Хорошо.
Мы видели это.
Прохладный.
Так вставок.
И я, вероятно, проложить через это.
Я не позволю тебе ребята кодировать его.
Мы просто пройти через это.
Так вставок добр из похож на выбор рода
в том, что у нас есть и несортированный и сортируют часть массива.
>> Но то, что отличается тем, что как мы проходим через один за другим,
мы просто взять любой номер является следующим в наш несортированный,
и правильно сортировать его в нашем массиве.
Это будет иметь больше смысла с примера.
Так что все начинается как несортированный, точно так же как с выбора сорта.
И мы собираемся, чтобы уладить это в порядке возрастания, как мы были.
Так на нашем первом проходе мы берем первое значение
и мы говорим, хорошо, вы Теперь в списке по себе.
>> Потому что вы находитесь в списке самостоятельно, вы сортируются.
Поздравляем быть Первый элемент в этом массиве.
Вы уже отсортированы все по своему усмотрению.
Так что теперь мы сортируются и несортированный массив.
Так что теперь мы возьмем первый.
Что происходит между здесь и в том, что мы говорим:
Хорошо, мы будем смотреть на Первое значение нашей несортированным массива
и мы собираемся ввести его в своей правильное место в массиве.
>> Итак, что мы делаем, мы берем 5 и мы говорим, хорошо, 5 больше 3,
так что мы просто вставьте его право справа, что.
Мы хорошо.
Итак мы переходим к нашей следующей.
И мы берем 2.
Мы говорим, хорошо, 2 меньше чем 3, так что мы знаем, что это
должен быть в Фронт нашем списке теперь.
Так что мы делаем, мы нажимаем 3 и 5 вниз и мы движемся 2 в тот первый слот.
Таким образом, мы просто вставив его в правильное место это должно быть.
>> Тогда мы посмотрим на наш Следующий, и мы говорим, 6.
ОК, 6 больше, чем все в нашем массиве,
так что мы просто пометить его до конца.
А потом мы смотрим на 4.
4 меньше, чем 6, это меньше, чем 5, но это больше, чем 3.
Так что мы просто вставить его прямо в посередине между 3 и 5.
Таким образом, чтобы сделать что немного немного более конкретными,
вот вроде Идея о том, что произошло.
Таким образом, для каждого несортированным элемента, мы определить, где в отсортированном части
это.
>> Так имея в виду, в сортируются и несортированный,
мы должны пройти через и фигура , где она вписывается в массиве.
И мы вставляем его, сдвигая элементы справа от него вниз.
А потом мы просто держать не перебор, пока мы
есть полностью отсортированный список где несортированный теперь равно нулю
и отсортированный занимает Совокупность нашем списке.
Так, опять же, чтобы сделать вещи еще более конкретное, у нас есть псевдокода.
>> Поэтому в основном для я это равна 0 до п минус 1,
вот только длина нашего массива.
Мы имеем некоторый элемент, который равен Первый массив или первые показатели.
Мы ставим J, равную.
Таким образом, хотя J больше нулю, а массив, J минус 1
больше, чем элемент, так что все, что делает
убедившись, что Ваше J действительно представляет
без сортировки часть массива.
>> Так, пока еще есть вещи, сортировать и J минус один is-- что
является элементом ее?
J никогда не определяется здесь.
Это своего рода раздражает.
Хорошо.
В любом случае.
Так J минус 1, вы проверяете элемент перед ним.
Вы хотите сказать, что, в порядке, это элемент до куда бы я ни am-- давайте
на самом деле сделать это.
Так скажем, это как на нашем втором проходе.
Так что я будет равна 1, которая находится здесь.
>> Таким образом, я намерен быть равен 1.
Это было бы 2, 4, 5, 6, 7.
Хорошо.
Таким образом, наш элемент в данном случае будет равна 4.
И у нас есть некоторое J Вот будет равна 1.
О, J является уменьшая.
Вот что это такое.
Так J равна I, так что это говорится, что, как мы движемся вперед,
мы только убедившись, что мы не более
индексации этот путь, когда мы пытаемся вставить вещи в нашем упорядоченном списке.
>> Поэтому, когда J равен 1, в этом случае и Массив J минус одно-- так массив J минус 1
2 в этом case-- если это больше, чем элемент,
Затем все это делает смещается вещи вниз.
Так, в данном случае, массив J минус один Массив будет нулевым, который является 2.
2 не больше, чем 4, так что это не выполняется.
Так сдвиг не съезжать.
Что это делает здесь просто перемещение отсортированный массив вниз.
В этом случае, на самом деле, мы может do-- давайте сделаем это 3.
Так что, если мы хотим идти через с этот пример, мы сейчас здесь.
Это сортируется.
Это несортированный.
Прохладный?
Так я равен 2, так наш элемент равен 3.
И наша J равна 2.
Таким образом, мы с нетерпением через и мы сказать, в порядке, это массив J минус один
больше, чем элемента что мы смотрим?
И да, не так ли?
4 больше, чем 3 и J 2, так что этот код выполняется.
>> Так что теперь, что мы делаем массив на 2, так прямо здесь, мы поменять их местами.
Таким образом, мы просто сказать: ОК, массив на 2 теперь будет 3.
И J собирается равняться J минус 1, который равен 1.
Это ужасно, но вы, ребята, получите эту идею.
J теперь равна 1.
И массив J только собирается быть равна нашего элемента, который был 4.
Я стер что-то я не должен есть или miswrote-то,
но вы, ребята, получите эту идею.
>> Это двигаться в п.
И потом, если бы это было, это было бы петля снова, и это было бы сказать, в порядке, J = 1 теперь.
И массив J минус 1 теперь 2.
Есть 2 меньше, чем наши элемента?
Нет?
Это означает, что мы в вставляется этот элемент
в правильном месте в нашем массиве.
Тогда мы можем взять это, и мы говорим, ОК, наш упорядоченный массив здесь.
И это было бы взять этот номер 6 и быть как, в порядке, составляет 6 меньше, чем это число?
Нет?
Прохладный.
У нас все хорошо.
>> Сделайте это снова.
Мы говорим, 7.
Является 7 меньше, чем в конце нашей массиве?
Нет.
Так что мы в порядке.
Так что это будет отсортирован.
В основном все это делает Разве это говорит дубль
Первый элемент Ваш несортированный массив,
выяснить, где он идет в массиве.
И это только заботится свопов, чтобы сделать это.
Вы в основном просто поменяв пока это не в нужном месте.
Визуальный образ, что вы движется все вниз, делая это.
>> Так что это как половина пузырьковой сортировки в стиле.
Проверьте исследование 50.
Я очень рекомендую попытку закодировать это на свой собственный.
Если у вас есть какие-либо вопросы или вы хотите см пример кода для вставки рода,
пожалуйста, дай мне знать.
Я всегда вокруг.
Так худшем случае выполнения и лучший случай выполнения.
Как вы парень увидел из-за стола, я уже показал вам, что это как н в квадрат и н.
>> Так вроде уходить от того, что мы говорили о наших предыдущих родах, худшее
Дело в том, что во время выполнения, если это полностью Unsorted,
мы должны сравнить все эти п раз.
Мы делаем кучу сравнений потому что, если это в обратном порядке,
мы собираемся сказать, в порядке, это это то же самое, это хорошо,
и этот должен будет сравниваться против первого перенести обратно.
И, как мы получим к конец хвоста, у нас есть
сравнивать, сопоставлять, и сравнить против всего.
>> Так он оказался примерно н квадрат.
Если это правильно, то вы сказать, в порядке, 2, вы хорошо.
3, вы по сравнению с 2.
Ты хорош.
4, вы просто сравните с хвостом.
Ты хорош.
6, по сравнению с хвоста, вы прекрасны.
Таким образом, для каждого места, если это уже сортируются, вы делаете одно сравнение.
Так что это просто п.
И потому, что у нас есть лучший случай выполнения п и худшем случае выполнения п
квадрат, у нас нет никакой ожидаемого выполнения.
>> Все зависит от хаос нашем списке нет.
И снова, другой График и другой стол.
Так различий между видами.
Я просто хочу, чтобы ветер через, я чувствую, что мы говорили подробно
о том, как они всех видов из изменяться и связать вместе.
Так сортировки слиянием является последним Я буду утомлять вас, ребята с.
У нас есть довольно красочную картину.
Так сливаются рода является рекурсивный алгоритм.
Так что вы, ребята, знаете, что рекурсивная функция?
>> Кто-нибудь хочет сказать?
Вы хотите попробовать?
Так рекурсивная функция является просто функция, которая называет себя.
Так что, если вы, ребята, знакомы с последовательностью Фибоначчи,
который считается рекурсивным потому вы берете две предыдущие
и добавить их вместе чтобы получить следующий.
Так рекурсивной, я всегда думаю, рекурсии как как спираль
так что вы, как по спирали вниз в него.
Но это всего лишь функция которая называет себя.
>> И, на самом деле, очень быстро я может показать вам, как это выглядит.
Так рекурсивный здесь, если мы посмотрим, что это рекурсивный способ суммировать массив.
Так что все, что мы делаем, у нас есть функция суммы
Сумма, которая принимает размер и массив.
И если вы заметили, размер уменьшается на единицу каждый раз.
И все это делает, если х равно zero-- так что если размер массива
равна zero-- возвращается ноль.
>> В противном случае это подводит это Последний элемент массива,
а затем принимает сумму остальная часть массива.
Так что это просто разбить его на все более мелкие проблемы.
Короче говоря, рекурсия, Функция, которая называет себя.
Если это все, что вы вышли из этого, это то, что рекурсивная функция.
Если взять 51, вы получите очень, очень удобно с помощью рекурсии.
Это действительно здорово.
Это имело смысл в подобном 3 утра однажды ночью.
И я подумала: почему не я не использую это?
>> Таким образом, для сортировки слиянием, в основном что он собирается сделать, это это
собираюсь разбить его и разбить его вниз, пока это не просто отдельные элементы.
Отдельные элементы легко отсортировать.
Мы видим, что.
Если у вас есть один элемент, это уже считается отсортированный.
Так на входе п элементов, если п меньше, чем 2,
просто вернуть, потому что это означает, что это либо 0, либо 1, как мы уже видели.
Те, считаются отсортированные элементы.
>> В противном случае разорвать его пополам.
Сортировать первую половину, отсортировать второй половина, а затем объединить их вместе.
Почему это называется сортировка слиянием.
Таким образом, мы имеем здесь мы будем сортировать эти.
Так мы продолжаем иметь их до тех пор, пока размер массива равен 1.
Поэтому, когда это 1, мы просто вернуться потому что это упорядоченный массив,
и это упорядоченный массив, и это упорядоченный массив, мы все разобрались.
Итак, что мы делаем, мы начать слияние их вместе.
>> Так как вы можете думать о слияние
Вы просто удалите меньше Количество каждого из массивов суб
и просто добавить его в сложившейся массива.
Так что, если вы посмотрите здесь, когда у нас есть эти наборы у нас есть 4, 6 и 1.
Когда мы хотим объединить эти, мы смотрим на этих первых двух
и мы говорим, хорошо, 1 меньше, он идет на фронт.
4 и 6, нет ничего, чтобы сравнить это, просто пометить его до конца.
>> Когда мы объединяем эти два, мы просто взять меньший один из этих двух,
так что это 1.
А теперь возьмем Меньшее из этих двух, так 2.
Меньше этих двух, 3.
Меньше этих двух, 4, 5, 6.
Таким образом, вы просто стягивая их.
И потому, что у них есть отсортированы ранее,
Вы только один из них Сравнение каждый раз там.
Так больше кода здесь, просто представление.
Таким образом, вы начинаете в середине и вы как бы левый и правый
а затем вы просто объединить тех.
>> И мы не имеем код для слияния прямо здесь.
Но, опять же, если вы идете на учиться 50, он будет там.
В противном случае пришел поговорить со мной если вы до сих пор путают.
Так здорово, что здесь является то, что лучше всего так, в худшем случае, и ожидается, среда
все в журнале п, гораздо лучше, чем мы
видно для остальной части наших сортов.
Мы видели н квадрате и то, что мы на самом деле
получить здесь п войти н, который является большим.
>> Посмотрите, как много лучше, что есть.
Такой хороший кривая.
Так гораздо более эффективным.
Если вы когда-нибудь может, использование сортировка слиянием.
Это поможет вам сэкономить время.
С другой стороны, как мы уже говорили, если вы вниз в этой нижней области,
это не делает, что особой разницы.
Вы получаете до тысячи и тысячи входов,
вы определенно хотите более эффективный алгоритм.
И, опять же, наша прекрасная таблица всех виды, что вы, ребята узнали сегодня.
>> Так что я знаю, это был плотный день.
Это не обязательно происходит чтобы помочь вам с вашей PSET.
Но я просто хочу сделать оговорку что эта часть не только о psets.
Весь этот материал является справедливым игра для ваших промежуточных выборах.
А также, если вы продолжать с CS, это действительно важные основы
что вы должны были бы знать.
Так несколько дней будет немного больше PSET помощь,
но через несколько недель будет гораздо более реальное содержание
что может показаться не супер полезной для вас прямо сейчас,
но я обещаю, если вы будете продолжать на будет очень, очень полезно.
>> Так вот именно для раздела.
Вниз к проводу.
Я сделал это в течение одной минуты.
Но там вы идете.
И у меня будет пончики или конфеты.
Кто-нибудь аллергия на что-нибудь, кстати?
Яйца и молоко.
Так что пончики не?
Хорошо.
Шоколад нет?
Starburst.
Starbursts хороши.
Хорошо.
Мы собираемся иметь Starburst на следующей неделе, то.
Это то, что я получу.
Вы, ребята, есть большая неделя.
Прочитайте спецификацию.
>> Дайте мне знать, если у вас есть какие-либо вопросы.
Pset два сорта должны быть к вам на четверг.
Если у вас есть какие-либо вопросы о том, как я классифицируются что-то
или почему я классифицируются что-то, как я так, пожалуйста, напишите мне, приходят поговорить со мной.
Я чуть с ума в этом неделю, но я обещаю,
Я до сих пор ответить в течение 24 часов.
Так есть большой неделю, все.
Удачи на PSET.