И последнее замечание: если у вас уже есть опыт программирования, почитайте о бинарных деревьях поиска! Эти структуры данных кратко описаны в последней главе.
Шпаргалка
• Бинарный поиск работает намного быстрее простого.
• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
• Скорость алгоритмов не измеряется в секундах.
• Время выполнения алгоритма описывается ростом количества операций.
• Время выполнения алгоритмов выражается как «O-большое».
2. Сортировка выбором
В этой главе
• Вы познакомитесь с массивами и связанными списками — двумя основными структурами данных, которые используются буквально везде. Мы уже использовали массивы в главе 1 и будем использовать их почти в каждой главе книги. Массивы чрезвычайно важны, уделите им внимание! Впрочем, иногда вместо массива лучше воспользоваться связанным списком. В этой главе объясняются плюсы и минусы обеих структур данных, чтобы вы могли решить, какой вариант лучше подходит для вашего алгоритма.
• Вы изучите свой первый алгоритм сортировки. Многие алгоритмы работают только с отсортированными данными. Помните бинарный поиск? Он применяется только к предварительно отсортированному списку. В большинстве языков существуют встроенные алгоритмы сортировки, так что вам редко приходится писать свою версию «с нуля». Однако алгоритм сортировки выбором поможет перейти к алгоритму быстрой сортировки, описанному в следующей главе. Алгоритм быстрой сортировки очень важен, и вам будет проще разобраться в нем, если вы уже знаете хотя бы один алгоритм сортировки.
Что необходимо знать
Чтобы понять ту часть этой главы, которая относится к анализу эффективности, необходимо понимать смысл понятия «O-большое» и логарифмов. Если вы совершенно не разбираетесь в этих вопросах, лучше вернуться и прочитать главу 1. «O-большое» будет использоваться в оставшихся главах книги.
Как работает память
Представьте, что вы пришли в театр и хотите оставить свои личные вещи в гардеробе. Для хранения вещей есть специальные ящики.
В каждом ящике помещается один предмет. Вы хотите сдать на хранение две вещи, поэтому требуете выделить вам два ящика.
И вы оставляете свои две вещи.
Готово, можно идти на спектакль!
В сущности, именно так работает память вашего компьютера. Она представляет собой нечто вроде огромного шкафа с множеством ящиков, и у каждого ящика есть адрес.
fe0ffeeb — адрес ячейки памяти.
Каждый раз, когда вы хотите сохранить в памяти отдельное значение, вы запрашиваете у компьютера место в памяти, а он выдает адрес для сохранения значения. Если же вам понадобится сохранить несколько элементов, это можно сделать двумя основными способами: воспользоваться массивом или списком. В следующем разделе мы обсудим массивы и списки, их достоинства и недостатки. Не существует единственно верного способа сохранения данных на все случаи жизни, поэтому вы должны знать, чем различаются разные способы.
Массивы и связанные списки
Иногда в памяти требуется сохранить список элементов. Предположим, вы пишете приложение для управления текущими делами. Описания задач должны храниться в виде списка в памяти.
Что использовать — массив или связанный список? Для начала попробуем сохранить задачи в массиве, потому что этот способ более понятен. При использовании массива все задачи хранятся в памяти непрерывно (то есть рядом друг с другом).
Теперь предположим, что вы захотели добавить четвертую задачу. Но следующий ящик уже занят — там лежат чужие вещи!
Представьте, что вы пошли в кино с друзьями и нашли места для своей компании, но тут приходит еще один друг, и ему сесть уже некуда. Приходится искать новое место, где смогут разместиться все. В этом случае вам придется запросить у компьютера другой блок памяти, в котором поместятся все четыре задачи, а потом переместить все свои задачи туда.