Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

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

72 ГЛАВА 3
не останется (как в примере с неудачным поиском). Если у нас есть n элемен- тов, это может произойти не больше, чем lgn раз; следовательно, двоичный поиск имеет сложность вида O(lgn).
Это довольно впечатляющее преимущество перед последовательным по- иском, даже если он самоорганизующийся. Поиск по миллиону элементов займет не больше 20 шагов. С другой стороны, ста шагов хватит на то, чтобы найти любой элемент в списке длиной 2 100
≈ 1,27 × 10 30
, что больше одного
нониллиона.
Поразительная эффективность двоичного поиска сравнима разве что с его известностью. Это интуитивный алгоритм. Но, несмотря на свою про- стоту, он вновь и вновь вызывает затруднения при реализации его в компью- терных программах. Это связано не с самим двоичным поиском, а скорее с тем, как мы переводим алгоритмы в настоящий компьютерный код с по- мощью языков программирования. Программисты постоянно становятся жертвами коварных ошибок, которые закрадываются в их реализации. И это касается не только новичков: иногда даже программистам мирового класса не удается реализовать этот алгоритм как следует.
Чтобы понять, откуда берутся эти ошибки, подумайте о том, как мы нахо- дим средний элемент в списке на первом этапе алгоритма. Вот простой под- ход: середина между m-м и n-м элементами равна (m + n) / 2; если результат не натуральное число, он округляется. Это правильный принцип, основан- ный на элементарной математике, поэтому он применим везде.
Везде, кроме компьютеров. Компьютеры обладают ограниченными ре- сурсами, к которым относится и память. Поэтому на компьютере невозможно представить любые числа; некоторые из них просто слишком большие. Если компьютер накладывает ограничение на максимальный размер чисел, с ко- торыми он может работать, то m и n должны быть меньше этого лимита. Ко- нечно, (m + n) / 2 вписывается в допустимый диапазон, но, чтобы вычислить это значение, нам нужно сначала выполнить m + n и затем поделить на два,
и эта сумма может превысить установленное ограничение! Это называется
переполнением: выход за пределы допустимых значений. Поэтому у вас может возникнуть ошибка, которая, как вы считали, вам не страшна. Результатом будет не среднее значение, а что-то совсем другое.
Осознав эту опасность, вы можете легко от нее защититься. Средний эле- мент нужно вычислять не как (m + n) / 2, а как m + (m — n) / 2. Результат тот же, но без переполнения. Теперь, когда вы знаете, в чем загвоздка, это ре- шение кажется простым, но любой может быть пророком задним числом.

Конечно, эта книга посвящена алгоритмам, а не программированию, но позвольте автору поделиться опытом с теми, кто пишет или хочет пи- сать компьютерные программы. Не отчаивайтесь, если вам когда-либо при- дется лихорадочно размышлять над строчкой кода, которая делает не то, чего вы от нее ожидали. Не волнуйтесь, если на следующий день окажется, что ошибка все это время была прямо у вас перед носом. Как же вы могли ее не за- метить? Вы не одиноки. Это случается со всеми, даже с лучшими из нас.
Двоичный поиск требует, чтобы элементы были отсортированы. Поэтому, чтобы воспользоваться его преимуществами, нам нужно сначала научиться эффективно сортировать элементы. Таким образом мы плавно переходим к следующей главе, в которой вы узнаете, как сортировать вещи с помощью алгоритмов.

74 ГЛАВА 4
ГЛАВА 4
СОРТИРОВКА
Конституция США гласит, что раз в десять лет должна проходить перепись населения, чтобы распределить налоги и представителей между разными штатами. Первая перепись после Американской революции состоялась в 1790 году, и с тех пор ее проводят каждое десятилетие.
На протяжении следующих ста лет после 1790 года население США стре- мительно выросло — с 4 миллионов во время первой переписи до более чем
50 миллионов в 1880 году. Но вместе с этим возникла проблема: время, ухо- дившее на подсчеты, достигло восьми лет. Когда в 1890 году пришел черед следующей переписи, население выросло еще сильнее. Если бы этот процесс проходил как раньше, он, скорее всего, не был бы завершен до следующей пе- реписи 1900 года.
В то время в Бюро переписи населения США работал Герман Холлерит, мо- лодой выпускник Горной школы при Колумбийском университете (он окон- чил обучение в 1879 году в возрасте 19 лет). Зная о насущной проблеме с нехваткой времени, он пытался придумать, как ускорить этот процесс с по- мощью механических устройств. Холлерит вдохновился тем, как кондукторы записывали данные пассажиров, пробивая дыры в их железнодорожных би- летах; он изобрел способ записи информации о переписи населения с исполь- зованием перфокарт. Затем эти карты можно было обработать табулято-
рами — электромеханическими машинами, которые считывали пробитые дыры и проводили на их основе вычисления.
Табулятор Холлерита применялся в переписи 1890 года и позволил сокра- тить время подсчетов до шести лет; оказалось, что население США выросло примерно до 63 миллионов человек. Холлерит представил свое изобретение
Королевскому статистическому обществу, отметив: «Не следует считать, что эта система все еще находится на стадии экспериментов. Эти машины под- считали более 100 000 000 перфокарт по нескольку раз, и это создало широкое поле для проверки их возможностей». После проведения переписи Холлерит

СОРТИРОВКА 75
основал частную компанию под названием Hollerith Electric Tabulating System.
В 1924 году после череды переименований и слияний она превратилась в International Business Machines ().
В наши дни сортировка стала настолько вездесущей, что мы ее почти не за- мечаем. Всего несколько десятилетий назад в офисах были громадные карто- теки с папками, и корпоративный персонал следил за тем, чтобы они храни- лись в нужном порядке (алфавитном или хронологическом). Для сравнения: всего одним щелчком мыши все письма в нашем почтовом ящике можно от- сортировать по таким критериям, как тема, дата и отправитель. Наши кон- такты хранятся в отсортированном виде на цифровых устройствах без како- го-либо внимания с нашей стороны; всего пару лет назад нам приходилось самостоятельно организовывать наши контакты в записных книжках.
Вернемся к переписи населения в США. Сортировка была одним из пер- вых примеров автоматизации офисной работы и одним из первых приме- нений цифровых вычислительных машин. За это время разработано множе- ство разных алгоритмов сортировки. Целый ряд из них активно используется в программировании, предлагая разные сравнительные преимущества и не- достатки, хотя некоторые не применяются на практике. Сортировка — это настолько фундаментальный аспект работы компьютеров, что в любой книге, посвященной алгоритмам, им всегда отводится отдельное место. И именно благодаря их большому разнообразию можно оценить важную сторону дея- тельности компьютерных специалистов и программистов. В их распоряже- нии находится множество инструментов, и некоторые из них подходят для одной и той же задачи. Представьте себе набор отверток: плоских, кресто- образных, шестигранных, квадратных и т. д. У всех у них одно и то же на- значение, но для определенных болтов нужны подходящие отвертки. Иногда плоская отвертка подходит для крестообразного болта; но обычно в каждой ситуации следует выбирать соответствующий инструмент. То же самое с сор- тировкой. Все сортировочные алгоритмы занимаются упорядочиванием, но каждый из них предназначен для определенных задач.
Прежде чем приступать к исследованию этих алгоритмов, давайте попро- буем объяснить, что именно они делают. Очевидно, что они что-то сортируют, но здесь сразу же напрашивается вопрос: что мы имеем в виду под сортиров-
кой данных?
Предполагается, что у нас есть набор взаимосвязанной информации, ко- торую обычно называют записями. Это, к примеру, могут быть электронные письма в нашем почтовом ящике. Мы хотим организовать эти данные так, чтобы они находились в удобном для нас порядке. Эта перестановка должна

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

СОРТИРОВКА 77
учитывать определенное свойство или свойства данных. В нашем примере с письмами упорядочивание может быть основано на дате получения (хро- нологический порядок) или имени отправителя (алфавитный порядок). Это можно делать по возрастанию, от старых писем к новым, или по убыванию, от новых писем к старым. Результатом процесса сортировки должны быть те же данные, которые были на входе; говоря техническим языком, это дол- жна быть перестановка исходных данных, то есть те же элементы, только в другом порядке, без каких-либо изменений.
Свойство, по которому мы сортируем информацию, обычно называется
ключом. Ключ может быть атомарным, если его нельзя разложить на части, или составным, если он основан на нескольких свойствах. Если нам нужно отсортировать письма по дате доставки, достаточно атомарного ключа (дату можно разбить на год, месяц и день, и она может также содержать точное время доставки, однако нам это неважно). Но мы также можем захотеть, чтобы письма были отсортированы сначала по имени отправителя, и чтобы все письма каждого отправителя шли в порядке доставки. Сочетание даты и отправителя представляет собой составной ключ для нашей сортировки.
В качестве ключа для сортировки можно использовать любое свойство — главное, чтобы его значение можно было упорядочить. Среди прочего это, естественно, относится к числам. Если нам нужно отсортировать инфор- мацию о продажах по количеству проданных товаров, наш ключ будет це- лым числом. Если ключи текстовые, такие как имена отправителей писем, мы обычно используем лексикографический порядок. Чтобы иметь возмож- ность упорядочить наши данные, алгоритмы сортировки должны знать, как их сравнивать, но способ сравнения может быть любым (главное, чтобы он был корректным).
Начнем исследование методов сортировки с двух алгоритмов, которые могут быть вам знакомы, так как они, наверное, являются самыми интуи- тивно понятными. Их применяют для упорядочивания разных вещей даже люди, которые ничего не знают об алгоритмах.

78 ГЛАВА 4
Следует признать, что это довольно тривиальный пример; мы имеем дело с числами от одного до десяти. Но такое упрощение позволит нам сосредото- читься на логике сортировки.
Для начала мы пройдемся по всем элементам, возьмем меньший из них и переместим его в начало. Минимальное число равно 1, поэтому его следует сделать первым. Но эта позиция уже занята, поэтому нам нужно куда-то деть число 4, которое в ней сейчас находится; мы не можем его просто выбросить.
Его можно поменять местами с наименьшим значением: минимум переме- щается в самое начало, а то число, которое находилось там изначально, зани- мает освободившуюся позицию. Таким образом из этого списка, где мини- мум закрашен черным,
4 6
10 7
9 3
2 8
5
получается следующий,
1 6
10 4
7 9
3 2
8 5
где минимум закрашен белым, указывая на то, что он находится в правиль- ной, упорядоченной позиции.
Теперь мы повторяем то же самое для всех чисел, кроме уже найденного минимума, то есть начиная со второй позиции и дальше (серые числа). На- ходим их минимум (2) и меняем его местами с первым из неотсортирован-
ных чисел (6).
1 6
10 4
7 9
3 8
5 1
2 10 4
7 9
3 6
8 5
И снова делаем то же самое, перебирая элементы, начиная с третьей по- зиции. Находим минимум (3) и меняем его местами с тем элементом, кото- рый сейчас находится на третьем месте (10).
1 2
10 4
7 9
6 8
5 1
2 3
4 7
9 10 6
8 5

СОРТИРОВКА 79
Если продолжить в том же духе, число 4 останется на месте, так как оно уже находится в правильной позиции. Затем мы поместим в нужную пози- цию число 5.
1 2
3 4
7 9
10 6
8 1
2 3
4 5
9 10 6
8 7
На каждом этапе у нас остается все меньше и меньше элементов, среди ко- торых нужно искать минимальный. В конце мы найдем наименьший элемент из двух оставшихся, и на этом сортировка будет закончена.
Этот подход называется сортировка выбором, поскольку каждый раз из неотсортированных элементов выбирается минимальный и помещается туда, где он должен быть. Как и любой другой сортировочный алгоритм, ко- торый мы здесь рассмотрим, сортировка выбором отлично справляется с элементами, у которых одинаковый порядок. Если при поиске по неотсор- тированным элементам находится больше одного минимума, мы просто вы- бираем любой из них, а другие найдутся на следующих этапах и будут поме- щены рядом с ним.
Сортировка выбором — довольно прямолинейный алгоритм. Но можно ли его назвать хорошим? Внимательно присмотритесь к тому, что он делает: он последовательно проходится по всем элементам, которые нужно отсортиро- вать, и каждый раз пытается найти минимум среди оставшихся неотсорти- рованных элементов. Если количество элементов n, сложность сортировки выбором составит O(n
2
). Этот подход не плохой сам по себе; такая сложность является приемлемой. Мы можем решать огромные задачи (то есть сортиро- вать много элементов) за разумное количество времени.
Но дело в том, что именно по причине большого значения сортировки для нее были созданы другие, более быстрые алгоритмы. Сортировка выбором не так уж и плоха, но обычно, если у нас есть большое количество элементов, мы отдаем предпочтение другим, более совершенным методам. С другой сто- роны, сортировка выбором проста для понимания, и ее легко можно реализо- вать на компьютере эффективным образом. Поэтому она совершенно точно не ограничивается академическим интересом; ее действительно применяют на практике.
То же самое можно сказать о другом простом сортировочном алгоритме, который мы сейчас опишем. Как и в случае с сортировкой выбором, для его