Лекции

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

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

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

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

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

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

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

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

Если с лекциями и теорией все пошло, как надо, вы без труда ответите на проверочные вопросы: Почему бинарный поиск требует отсортированного массива? Почему оценка сортировки пузырьком равна O(n2)? Почему оценка сортировки вставками — это Ω(n)? Как работает сортировка выбором?

Итак, начинаем. Обратите внимание, find.c вызывает search, функцию, объявленную в helpers.h. К сожалению, мы забыли реализовать эту функцию полностью в helpers.c! Надо отметить, что мы могли бы поместить содержимое helpers.h и helpers.c в один find.c...

Настало время поиграть! Большинство людей знакомы с головоломкой «Пятнашки». Если формализовать, «Пятнашки» — это двумерное поле 4х4, в этом поле расположены не 16, а 15 квадратиков, то есть один слот остается пустым. Каждый из квадратиков пронумерован и может двигаться внутри поля по горизонтали или вертикали...

По ссылкам ниже вы найдете весь код, который был написан Дэвидом Маланом и его ассистентами во время видеолекций третьей недели.