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

80 ГЛАВА 4
понимания не нужно разбираться в компьютерах. На самом деле именно так многие люди сортируют свои игральные карты.
Представьте, что вы участвуете в карточной игре с десятью картами (на- пример, вы можете играть в Румми). Вы выбираете одну карту за другой и сортируете их в своей руке. Допустим, карты разделены по старшинству, начиная с младшей.
2 3 4 5 6 7 8 9 J Q K A
На самом деле во многих играх (включая Румми) туз может быть как младшей, так и старшей картой, но здесь мы исходим из того, что порядок всегда один.
Вы начинаете с одной карты и затем получаете еще девять.
4
В качестве второй карты вам попалась шестерка.
6 4
Шестерка вполне может находиться рядом с четверкой, поэтому вы остав- ляете ее как есть и берете следующую карту. Вам попалась двойка.
6 2
4
На этот раз, чтобы упорядочить ваши карты, вам нужно поместить двойку слева от четверки, то есть сместить четверку и шестерку на одну позицию вправо. После этого вам выпадает следующая карта, тройка.
6 4
3 2
Вы вставляете ее между двойкой и четверкой. Следующая карта, девятка, уже находится в правильной позиции.
4 3
6 9
2

СОРТИРОВКА 81
Дальше вам могут попасться такие карты, как 7, Q, J, 8 и 5. В конце у вас получится отсортированный набор.
Каждая новая карта вставляется в правильную позицию по отношению к предыдущей, уже упорядоченной. По этой причине данный подход назы- вается сортировкой вставками, и он подходит для любого рода объектов, не только для карт.
Сортировку вставками, как и сортировку выбором, довольно просто реализовать. Оказывается, она имеет ту же сложность: O(n
2
). Но у нее есть одна особенность: как вы могли видеть на примере нашей карточной игры,
нам не нужно заранее знать элементы, которые мы сортируем. В сущности, мы упорядочиваем их по мере поступления. Это означает, что сортировку вставками можно использовать в ситуациях, когда элементы передаются в виде какого-то потока прямо на лету. Нам уже встречался подобный алго- ритм при обсуждении графов на примере задачи с турниром в главе 2. Он называется онлайн-алгоритмом. Если нам нужно отсортировать неизвест- ное количество элементов или мы должны предоставить упорядоченный список по требованию в любой момент времени, сортировка вставками — подходящий выбор.
Поразрядная сортировка
Давайте вернемся к Холлериту. В его табуляторах не использовалась ни сор- тировка выбором, ни сортировка вставками. Вместо них применялся пред- шественник метода, который до сих пор находится в употреблении, — по-
разрядная сортировка. Если вам интересен первый в истории пример автоматизированного упорядочивания данных, уделите некоторое время, чтобы понять, как это работает. Интересно также то, что при сортировке дан- ным методом не происходит сравнения упорядочиваемых элементов друг с другом. По крайней мере, не полностью (подробнее об этом чуть ниже).
Кроме того, поразрядная сортировка представляет не только исторический интерес, так как она до сих пор прекрасно работает. Кому не понравится по- чтенный, но в то же время практичный алгоритм?
Проще всего поразрядную сортировку проиллюстрировать на примере все тех же игральных карт. Представьте, что у вас есть полная перетасован- ная колода, и вы хотите ее отсортировать. Чтобы это сделать, колоду можно разделить на 13 стопок, по одной для каждого достоинства. Мы проходимся по колоде, выбираем по одной карте и кладем ее в соответствующую стопку.

82 ГЛАВА 4
У нас получится 13 стопок по четыре карты в каждой: одна со всеми тузами, другая со всеми двойками и т. д.
A
2 3
4 5
6 7
8 9
10
J
Q
K
Затем мы собираем все стопки вместе, размещая каждую следующую снизу. Таким образом у нас в руках окажется полная, частично отсортиро- ванная колода. Первые четыре карты будут тузами, следующие четыре будут двойками и так далее вплоть до королей.
Теперь создадим четыре новых стопки, по одной для каждой масти. Мы пройдемся по всем картам, откладывая каждую из них в соответствующую стопку. У нас получится четыре стопки. Поскольку достоинства уже были от- сортированы, в каждой стопке окажутся карты одной масти, упорядоченные по старшинству.
A
A
A
A
Чтобы закончить сортировку, остается просто собрать карты стопка за стопкой.
Это основная идея поразрядной сортировки. Мы не сравнивали все карты между собой. Сравнение было частичным: сначала по достоинству, затем по масти.
Конечно, если бы поразрядная сортировка годилась только для карт, она не стоила бы нашего внимания. Давайте посмотрим, как она работает с це- лыми числами. Представьте, что у нас есть следующий набор значений.
926 742 151 612 961 162 261 760 639 532 364 165 970 412 417 855 245 317 568 812 709 787 496 5
97 577 845 53 274 590 840 981 686
Следует позаботиться о том, чтобы все числа имели одинаковое количе- ство разрядов. Поэтому при необходимости добавляем слева ноли, превращая

СОРТИРОВКА 83 5 в 005, 97 в 097 и 53 в 053. Перебираем все наши числа и разделяем их на де- сять групп по крайней справа цифре.
760 970 590 840 151 961 261 981 742 612 162 532 412 812 053 364 274 165 855 245 005 845 926 496 686 417 317 787 097 577 568 639 709
Мы сделали числа чуть светлее, чтобы сигнализировать о том, что они ча- стично упорядочены; в каждой группе находятся значения с одним и тем же младшим разрядом. В первой группе числа заканчиваются на ноль, во вто- рой — на один, а в последней — на девять. Мы собираем эти десять групп, двигаясь слева направо и добавляя каждую следующую снизу от предыдущей
(числа в группах ни в коем случае не должны перемешаться). Затем мы разде- ляем их на десять других групп, используя вторую цифру справа. Получится следующее.
005 709 612 412 812 417 317 926 532 639 840 742 245 845 151 053 855 760 961 261 162 364 165 568 970 274 577 981 686 787 590 496 097
На этот раз все числа в первой группе имеют одинаковый предпослед- ний разряд, равный нолю; во второй группе предпоследняя цифра равна 1, то же самое с остальными группами. В то же время числа в каждой группе уже

84 ГЛАВА 4
отсортированы по последнему разряду, так как именно это мы сделали, когда объединили их на первом этапе.
Снова собираем группы и перераспределяем числа, на этот раз используя третий разряд справа.
005 053 097 151 162 165 245 261 274 317 364 412 417 496 532 568 577 590 612 639 686 709 742 760 787 812 840 845 855 926 961 970 981
Теперь элементы в каждой группе начинаются с одной и той же цифры; при этом они отсортированы по второму и третьему разрядам (второй и пер- вый этапы). Чтобы закончить сортировку, достаточно объединить группы в последний раз.
Поразрядная сортировка подходит для слов, любых алфавитно-цифровых символов и целых чисел. В информатике последовательность алфавитно-ци- фровых символов называется строкой. Этот подход работает со строками; строка может состоять из цифр, как в нашем примере, но необязательно. Ко- личество групп для алфавитно-цифровых строк равно количеству букв в ал- фавите (например, 26 для английского алфавита), но проводимые операции будут точно такими же. Отличительная сторона поразрядной сортировки со- стоит в том, что строки всегда воспринимаются в качестве алфавитно-цифро- вых последовательностей, а не чисел, даже если они состоят из одних цифр.
Если еще раз взглянуть на наш пример, можно заметить, что нас не интере- совали конкретные значения; каждый раз мы работали с отдельным разря- дом числа. Точно так же мы извлекали бы символы из слова, двигаясь справа налево. Вот почему этот подход еще называют методом сортировки строк.
Но не думайте, что среди всех представленных здесь методов сортировки только поразрядный умеет упорядочивать строки. Все они могут это делать.
Главное, чтобы сами символы, из которых эти строки состоят, могли быть упорядочены. Компьютер воспринимает человеческие имена как строки, поэтому их можно сортировать, ведь буквы могут быть расставлены в ал- фавитном порядке, а имена можно сравнивать лексиграфически. Назва- ние «сортировка строк» связано с тем, что поразрядная сортировка работает со всеми ключами как со строками, даже с числами. Другие методы, пред- ставленные в этой главе, разделяют понятия чисел и строк и сравнивают их

СОРТИРОВКА 85
соответствующим образом. В наших примерах цифровые ключи использу- ются сугубо для удобства.
Поразрядную сортировку делает эффективной тот факт, что она обра- батывает элементы цифра за цифрой (или символ за символом). Если нам нужно упорядочить n элементов, каждый из которых состоит из w цифр или символов, сложность алгоритма составит O(wn). Это намного лучше, чем сложность O(n
2
), присущая сортировке выбором и вставками.
Таким образом мы снова возвращаемся к табуляторам. Табулятор работал похожим образом, сортируя перфорированные карты. Представьте, что у вас есть набор карт по десять столбцов в каждой. Отверстия в каждом столбце обо- значают цифру. Устройство способно распознавать эти дыры и тем самым опре- делять соответствующие значения. Оператор кладет карты в табулятор, а тот распределяет их по десяти выходным корзинам в зависимости от последнего столбца, то есть младшего разряда. Оператор собирает карты из корзин, стара- ясь не перемешать их никоим образом, и затем снова подсовывает их устройству, которое на этот раз распределяет их по выходным корзинам на основе предпо- следнего столбца — разряда, который находится перед младшим. Повторив этот процесс десять раз, оператор собирает упорядоченный набор карт. Вуаля!
Быстрая сортировка
Представьте, что у нас есть группа детей, которые бегают по двору (возможно, школьному), и вы хотите выстроить их в ряд от самого низкого до самого вы- сокого. Сначала мы просим их построиться в любом порядке на их выбор. Вот что получается.
Теперь выбираем ребенка наугад.

86 ГЛАВА 4
Мы просим детей, которые ниже выбранного ребенка, стать слева от него, а всех остальных — справа. На следующей диаграмме показано, где в итоге оказался выбранный ребенок; вы можете видеть, что дети, которые выше его, находятся справа, а те, которые ниже — слева.
Мы не просили детей построиться в правильном порядке. Они всего лишь переместились относительно выбранного нами ребенка. У нас получи- лось две группы: слева и справа. Дети в этих группах не выстроены по росту.
Но мы точно знаем, что один ребенок (тот, которого мы выбрали) уже нахо- дится в правильной позиции в том ряду, который мы хотим сформировать.
Все дети по левую сторону ниже его, а по правую — как минимум такого же роста или выше. Назовем выбранного нами ребенка точкой вращения, так как все остальные дети будут перемещаться относительно него.
Чтобы вам было легче ориентироваться, мы станем закрашивать детей, ко- торые уже находятся в правильной позиции, белым. Точка вращения, которую мы выбираем, выделим черным; после перемещения остальных детей мы на- рисуем небольшую черную «шляпку», чтобы обозначить итоговую позицию точки вращения (ее закрасим белым, поскольку она уже в правильной пози- ции, с черным верхом, который сигнализирует о выполненном перемещении).
Теперь сосредоточимся на одной из двух групп — например, на левой.
Опять выбираем наугад точку вращения в этой группе.
Мы просим детей в этой группе сделать то же, что и раньше: переме- ститься влево от выбранного ребенка, если они ниже его, или вправо, если нет. Как видно ниже, у нас опять получилось две группы поменьше. Одна из них состоит из одного ребенка, который, очевидно, находится в правиль- ной позиции. Остальные дети находятся справа от второй точки вращения.
Вторая точка тоже находится в нужном месте: все дети, которые ниже ростом,

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

88 ГЛАВА 4
И снова не потребовалось никаких перемещений, поэтому мы берем по- следнюю группу неупорядоченных детей и выбираем точку вращения.
Справа у нас получилась группа из одного ребенка, а слева — из двух. Бе- рем левую группу и выбираем одного из двух детей в качестве точки враще- ния.
Вот и все. Все дети выстроены по росту.
Давайте подведем итоги того, что мы только что сделали. Мы упорядочили всех детей, выбирая по одному ребенку и размещая его в правильной пози- ции. Для этого нам было достаточно попросить остальных детей выстроиться относительно него. Это всегда работает, и, конечно же, не только с детьми, но с любыми объектами, которые нужно отсортировать. Если необходимо упорядочить набор чисел, мы можем выполнить аналогичный процесс, выби- рая произвольное число и группируя остальные числа вокруг него так, чтобы меньшие оказались перед ним, а остальные за ним. То же самое повторяется в группах меньшего размера, которые у нас получились; в итоге все числа ока- жутся упорядоченными. Это процесс, лежащий в основе быстрой сортировки.
Быстрая сортировка основана на следующем наблюдении: если нам удастся расположить один элемент в правильной позиции относительно всех остальных (какой бы она ни была) и затем повторить то же самое для каж- дого оставшегося элемента, все элементы в итоге окажутся в правильных

СОРТИРОВКА 89
позициях. Если вспомнить сортировку выбором, там мы тоже брали каждый элемент и перемещали его в нужное место относительно остальных, но этот элемент всегда был наименьшим из тех, что остались. Это ключевое отличие: в быстрой сортировке точка поворота не должна быть минимальным элемен- том среди оставшихся. Давайте посмотрим, что получится, если все же выби- рать минимум.
Если снова начать с той же группы детей, точкой вращения будет самый низ- кий ребенок. Он перейдет в начало шеренги, а все остальные окажутся за ним.
Затем мы выберем самого низкого ребенка из оставшихся и сделаем его вторым. Все остальные опять окажутся справа от него.
Повторим то же самое с третьим ребенком и получим следующее.
Обратите внимание на то, как сильно это напоминает сортировку выбо- ром: шеренга выстраивается слева направо путем отбора самого низкого ре- бенка из оставшихся.
Теперь мы видим, что в качестве точки вращения не следует выбирать ми- нимальный элемент. Во-первых, это требует определенных усилий: каждый раз нам приходится искать наименьшее значение. Во-вторых, этот метод похож на уже известный нам алгоритм, поэтому использовать его нет особого смысла.
На самом деле быстрая сортировка лучше сортировки выбором, потому что «обычно» (вскоре мы увидим, что это означает) выбираемая нами точка