Лекції

Помните разорванный телефонный справочник из самой первой лекции CS50? На третьем уровне он возвращается! Возвращается, чтобы сделать фразу «эффективность алгоритмов» не пустым звуком, а пояснить на примере. Все программисты думают о скорости работы программы и о том, сколько памяти она при этом «съест».

Как вы помните, чтобы найти слово в словаре, нужно, чтобы информация была отсортирована по алфавиту. Иначе в худшем случае нам придётся пересмотреть весь словарь! Пришла пора узнать, как научить компьютер сортировать данные. А ещё в этой лекции Дэвид расскажет, что подразумевается под эффективностью алгоритма.

Одна программа может работать медленнее другой не из-за неэффективности, а по причине медлительности ОС, несовместимости с оборудованием, занятости памяти ПК… Для измерения эффективности алгоритмов придумали универсальные концепции, и они выдают результат независимо от среды, в которой запущена программа.

Когда вы открываете веб-браузер, ищете страничку, информацию, друзей в соцсетях, вы совершаете поиск, точно так же, как при попытке найти нужную пару обуви в магазине. Вы наверняка замечали, насколько сильно упорядоченность влияет на то, как вы ищете. Если все рубашки лежат в шкафу, найти среди них нужную обычно проще, чем среди разбросанных.

Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса. Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть. 

Вы уже знаете, что для бинарного поиска необходимо, чтобы массив был отсортирован. Таким образом, если у нас есть неотсортированный массив, в котором нужно найти некий элемент, у нас есть два варианта действий...

GDB относится к «умным» программам-отладчикам, то есть таким, которые «понимают» код и умеют выполнять его построчно, менять значения переменных, устанавливать контрольные точки и условия остановки… Словом, делать всё для того, чтобы разработчик мог проверить правильность работы своей программы.

Алгоритм сортировки слиянием интересен тем, что он рекурсивный, то есть вызывает сам себя. "Слияние" чуть более эффективно, нежели "пузырёк" или "вставки". Кроме того, Дэвид Малан поведает, что скрыто «под капотом» у программы и пояснит цепочку «исходный код – компилятор – объектный код».

Есть массив чисел. Нужно его отсортировать. Для простоты будем считать, что мы сортируем целые числа в порядке возрастания (от меньшего к большему). Существует несколько известных способов провернуть этот процесс. Плюс, вы всегда можете пофантазировать на тему и придумать модификацию алгоритма.

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

Основная идея алгоритма сортировки вставками — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части.

Этот алгоритм — рекурсивный, он разбивает одну большую задачу сортировки на подзадачи, выполнение которых делают его ближе к решению изначальной большой задачи. Основная идея — разделение неотсортированного массива на две части и сортировка отдельных половинок по рекурсивному принципу.