Идеи реализации

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

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

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

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

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

Таким образом, можно представлять себе смысл сортировки в поиске инверсий и их уничтожении до победного конца. Рисунок 18.1. «Глупая сортировка» хорошо показывает, с каким трудом порядок постепенно одерживает победу над хаосом, и даёт читателям возможность немного помедитировать. Нужно только нажать большую круглую кнопку.

Рисунок 18.1. Глупая сортировка

Другой классический алгоритм сортировки — пузырьковый. Алгоритм требует многократных проходов по сортируемому массиву, при которых в конце массива формируется отсортированный участок, причём с каждым проходом его длина увеличивается как минимум на единицу.

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

Рисунок 18.2. Пузырьковая сортировка

Алгоритм сортировки пузырьком можно немного улучшить, если проанализировать, как он работает в случае уже упорядоченного массива. Даже тогда состоятся все проходы в количестве n 1 штук (n — количество элементов), и в ходе каждого из них ни одна пара элементов не будет переставлена. В то же время совершенно ясно, что если очередной проход не принёс ни одной перестановки, сортировку можно на этом завершить. В качестве усовершенствования можно ввести дополнительную флаговую переменную, которой перед очередным проходом присваивается ложное значение, но при обнаружении инверсии она получает истинное значение. По окончании прохода значение флага говорит о его результативности. Это значение проверяется перед новым проходом, что позволит избежать ненужных проходов ценой некоторых дополнительных манипуляций с флагом.

Наблюдение за работой пузырькового алгоритма выявляет некоторый перекос. В то время как после каждого прохода максимальный элемент из необработанной части списка перемещается в её конец и присоединяется к обработанной, все остальные элементы, включая и минимальный, сдвигаются влево в лучшем случае на одну позицию, или же остаются на месте. К примеру, список 4 0 1 2 3 будет упорядочен уже после первого прохода, а список 1 2 3 4 0 для полного упорядочения потребует уже четырёх проходов внешнего цикла.

Шейкерная, она же челночная сортировка призвана устранить эту несправедливость. Список разбивается теперь уже на три части — левую, рабочую и правую. Обработка рабочей части происходит за два прохода — прямой и обратный. Обратный проход, как нетрудно догадаться, осуществляется справа налево, и он перетаскивает минимальный элемент из рабочей части к концу левого подсписка. Всё это хорошо видно на рисунке 18.3. «Шейкерная сортировка».

Оптимизация, применённая в пузырьковой сортировке, годится и для шейкерной. После прямого прохода граница правой части перемещается в точку, где произошёл последний обмен во время прямого прохода. Аналогично, граница левой части смещается в точку последнего обмена при обратном проходе.

Рисунок 18.3. Шейкерная сортировка

Ещё одна стратегия сортировки состоит в том, что сортируемый список мысленно разбивается на две смежные части — уже отсортированную и пока ещё не отсортированную. Изначально отсортированная часть пуста. Для первого элемента из неотсортированной части подыскивается подходящее место в отсортированной части, и этот элемент вставляется на найденное место. Так происходит до тех пор, пока неотсортированная часть не опустеет. Этот метод называется сортировкой вставками.

Рисунок 18.4. Сортировка вставками

При сортировке выбором, как и при сортировке вставками, список состоит из двух частей — отсортированной и неотсортированной. Но, в отличие от сортировки вставками, ищется не место вставки первого элемента из неотсортированной части списка, а тот элемент, который нужно поместить в конец отсортированной части. Это минимальный элемент из неотсортированной части, и он затем меняется местами с первым элементом неотсортированной части. За счёт этого отсортированная часть пополняется ещё одним элементом. Так продолжается до полного опустошения неотсортированной части.

Рисунок 18.5. Сортировка выбором

Метод древесной сортировки использует тот же подход, что и сортировка вставками.

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

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

Массив — идеальная структура данных для хранения упорядоченных последовательностей, поскольку само последовательное расположение элементов в памяти уже содержит информацию об их порядке. Но добавление нового элемента в массив с сохранением порядка обходится дорогой ценой: велики и затраты на поиск, и на саму вставку.

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

Как и следует из названия метода, подходящей структурой данных будет дерево, точнее упорядоченное двоичное (бинарное) дерево. Понятие бинарного дерева определим аксиоматически: бинарное дерево или пусто, или состоит из корня и двух ветвей, которые сами являются бинарными деревьями. Корень является ячейкой памяти для хранения элементов списка. Ветви дерева (если они есть), будем называть левым и правым поддеревьями.

Бинарное дерево называется упорядоченным, если:

На рисунке 18.6. «Упорядоченные бинарные деревья» показаны далеко не все возможные способы размещения шести элементов в упорядоченном бинарном дереве. Ветки, уходящие сверху вниз налево, означают «больше», а направо — «меньше или равно».


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

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

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

В языке Perl отсутствует готовая к употреблению структура «упорядоченное бинарное дерево», поэтому придётся строить её самостоятельно на базе имеющихся. Самое простое решение — моделировать дерево как ссылку на трёхэлементный массив, в котором первый элемент предназначен для хранения данных (элементов списка). Второй и третий элементы будут хранить соответственно левое и правое поддеревья. Мы выбрали не массив, а ссылку на массив потому, что деревья могут размещаться как элементы массивов (для которых они являются поддеревьями). Массивы, как мы знаем, не могут быть элементами в других массивах, а ссылки — могут. Пустые деревья будут представляться как ссылки на пустые массивы.

Деревьям на рисунке 18.6, таким образом, в Perl соответствуют следующие структуры:

  • [1, [0, [], []], [3, [2, [], []], [5, [4, [], []], []]]],
  • [2, [0, [], [1, [], []]], [4, [3, [], []], [5, [], []]]] и
  • [0, [], [1, [], [2, [], [3, [], [4, [], [5, [], []]]]]]].

Теперь видно, какой ценой нам достанется быстродействие. Вместе с каждым элементом последовательности (корнем какого-то дерева) хранятся также две ссылки.

Видно также, что разные деревья, построенные для одного и того же набора элементов, не являются равноценными с точки зрения эффективности добавления в них новых элементов. Цепочка рекурсивных вызовов при добавлении нового элемента может иметь такую длину, какова высота дерева (которую было бы уместней назвать глубиной для деревьев, растущих вниз). Среди изображённых на рисунке среднее дерево является наилучшим, а дерево справа — наихудшим. В общем случае предпочтительнее деревья, у которых максимально заполнены все этажи, кроме, быть может, последнего. Максимально возможные количества элементов на этажах дерева равны 1, 2, 4, 8, так что максимальная вместимость k-этажного дерева равняется 1 + 2 + 4 + + 2 k 1 = 2 k 1 элементов (сумма геометрической прогрессии!). Поэтому для «хороших» n-элементных деревьев выполняются неравенства 2 k 2 < n 2 k 1 , или k 2 < log 2 n k 1 (для тех, кто не знает: двоичный логарифм log 2 n числа n — это показатель степени, в которую нужно возвести двойку, чтобы получить n). Для «хороших» деревьев k растёт крайне медленно с ростом n. Для «плохих», как видно на примере дерева справа на рисунке, k = n , и это никуда не годится.

Выходом из положения было бы построение из элементов списка так называемого сбалансированного дерева, у которого высоты левого и правого поддеревьев по возможности близки, и тем же свойством обладают оба поддерева. Ясно, что не во всех случаях удастся добиться равных по высоте поддеревьев, но можно пожелать, чтобы их высоты различались не больше, чем на единицу. Тогда после добавления нового элемента дерево придётся подвергнуть при необходимости ребалансировке, процедуре, которая сделает дерево более коренастым и вернёт утраченное свойство сбалансированности. Это, правда, усложнит структуру данных и алгоритмы работы с ней. Существует несколько вариантов деревьев с автоматической ребалансировкой. Среди них следует упомянуть AVL-деревья и красно-чёрные деревья.

Другой вариант — сразу строить дерево сбалансированным. Но для этого потребуется добавлять элементы в определённом порядке, а именно выбирая каждый раз из списка медиану. Медианой называется такой элемент, что количество элементов списка, меньших или равных медиане либо равно количеству больших или равных элементов, либо эти количества отличаются на единицу. К сожалению, изменить порядок добавления новых элементов бывает нелегко, особенно если список слишком большой, и к элементу, после того как он обработан, больше нет доступа (типичным примером является список строк, прочитанных из файла). Кроме того, поиск медианы — это задача не легче, чем сортировка списка. Ведь медианный элемент — это тот, который окажется в середине отсортированного списка (ну или рядом с серединой, если в списке нечётное число элементов).

Медиану не следует путать со средним арифметическим элементов списка. Средняя температура по больнице не то же самое, что температура «среднего» пациента. Между прочим, вторая величина гораздо больше говорит об общем состоянии пациентов, чем первая. Так что отыскание медианы — очень даже насущная задача.

Мы выбираем третий, хорошо проторенный путь. Будем уповать на то, что подавляющее большинство из деревьев, содержащих элементы одного и того же списка, ближе к идеально сбалансированным, чем к вызывающе разбалансированным (это правда). Если список, подлежащий сортировке, составлен более-менее случайно, построенное дерево с большой вероятностью окажется невысоким. Увы, если сортировать список, уже упорядоченный по неубыванию или невозрастанию, мы как раз получим худший случай.

Другой подход к сортировке заключается в следующем. Извлечём из списка какой-нибудь элемент (проще всего — самый первый). Элемент при этом удаляется из списка. Такой элемент будем называть ключевым. Затем разделим получившийся список на два списка (назовём их левым и правым). В левый список отправятся элементы, строго меньшие ключевого элемента, а в правый — большие или равные ключевому. Затем отсортируем левый и правый списки и соединим их вместе, вставив между ними ключевой элемент. Для сортировки левого и правого списков используем тот же самый подход, что наводит на мысль о рекурсии.

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

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

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

Способ, который совершенно точно выбирает случайные перестановки элементов списка с одинаковыми вероятностями, мог быть таким. Нужно разыграть случайное целое значение от 0 до n ! 1 , где n — длина списка, и воспользоваться этим числом как номером в последовательности всех перестановок n-элементного списка, после чего можно подвергнуть список найденной перестановке. Для получения списка перестановок в принципе подойдёт любой из методов, описанных в главе 17. «Перестановки», но мы отдаём предпочтение итеративному методу, поскольку он требует намного меньшего объёма памяти, и, главное, он не требует получения всех перестановок. Как только будет получена перестановка с нужным случайным номером, цикл можно прервать.

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

Между тем есть очень простой алгоритм Фишера — Йетса — Дурстенфельда, перемешивающий список быстро и идеально.

Поясним алгоритм на примере колоды карт. Загадываем случайную карту в колоде и меняем её местами с самой верхней картой колоды (если загаданная карта и есть самая верхняя, она меняется сама с собой, то есть ничего не происходит). Затем снимаем верхнюю карту и откладываем в сторону. Ту же самую операцию проделываем снова и снова, пока все карты из колоды не будут сняты и отложены, точнее, переложены в другую колоду. Колода, состоящая из отложенных карт, будет идеально перемешана. Доказано, что все порядки карт, получающиеся после работы алгоритма, появятся с равными вероятностями, конечно, при условии, что вероятности любого выбора карты из остатка колоды одинаковы. Тут мы должны положиться на датчик случайных чисел, используемый для случайного выбора карты. Алгоритм Фишера — Йетса — Дурстенфельда требует всего лишь n 1 попарного обмена.

А теперь докажем, что с помощью алгоритма Фишера — Йетса — Дурстенфельда может быть получена любая перестановка, причём все перестановки равновероятны. Действительно, после первого шага алгоритма на последнем месте в n-элементном списке может с равными вероятностями 1 n оказаться любой элемент. После второго шага на предпоследнем месте с равными вероятностями 1 n 1 окажется любой из n 1 оставшегося элемента. Так что вероятность того, что после двух шагов в конце списка окажется та или иная пара элементов, равна 1 n n 1 . Рассуждая таким образом, получим, что к окончанию работы алгоритма любое получившееся упорядочение возникнет с вероятностью 1 n n 1 2 1 = 1 n ! . С учётом того, что возможных результатов, то есть перестановок n-элементного списка, всего n ! , доказано, что любая перестановка может быть получена в результате работы алгоритма, и вероятности появления каждой из них равны.

Обсуждая алгоритм Фишера — Йетса — Дурстенфельда, мы уповали на идеальный датчик случайных чисел, позволяющий выбрать случайную карту из колоды. К сожалению, со случайными датчиками не всё так просто. Ничего идеального не бывает, да и случайного, как нам кажется, тоже.

Важнейшей составной частью типичного датчика случайных чисел является целая числовая переменная, которая называется внутренним состоянием датчика. В начале работы эта переменная инициализируется произвольным образом. Обычно инициализирующее значение X 0 как-то вычисляется на основе текущего времени. Очередное случайное число вычисляется как некоторая функция от текущего состояния. После каждого обращения к датчику его состояние меняется по одному и тому же правилу, так что состояния образуют рекуррентную последовательность первого порядка X 0 , X 1 , X 2 , . Рекуррентная последовательность полностью определяется начальным состоянием X 0 , и, следовательно, таких последовательностей будет ровно столько, сколько существует различных начальных состояний. Одинаковым состояниям соответствуют одинаковые случайные числа, так что разнообразие случайных числовых последовательностей, вырабатываемых датчиком, будет ограничено. Вполне может так случиться, что при тасовании колоды некоторые последовательности загаданных карт вовсе не встретятся, а другие, напротив, появятся аномально часто.

Чтобы избежать этого осложнения, нужно увеличить количество возможных внутренних состояний. В типичном случае состояние является целочисленной 32-битной переменной, принимающей 2 32 значений. Для качественного тасования требуется, чтобы это число превышало количество всех перестановок карт в колоде, то есть n ! . Это условие выполняется лишь для колод с не более чем двенадцатью картами, что явно недостаточно для серьёзных игр. Для колоды из 52 карт для внутреннего состояния требуется как минимум 226 бит памяти.

Так что полагаться на встроенный датчик случайных чисел, реализованный в Perl как процедура rand, опасно, если мы не уверены в достаточном объёме памяти для его внутреннего состояния.

Имеется альтернатива процедуре rand. В операционной системе Linux в директории /dev есть два файла, random и urandom. Строго говоря, это не обычные файлы, и они не располагаются на жёстком диске компьютера. Это так называемые файлы устройств, но ведут себя они как файлы, из которых можно читать байт за байтом. Полученные последовательности байтов случайны, и алгоритм, с помощью которого они строятся, не основан на рекуррентных последовательностях. В создании очередного случайного байта участвуют различные трудно предсказуемые события, такие как нажатия клавиш на клавиатуре или движения мыши. Помимо событий используются также показания всевозможных датчиков температуры, скорости вращения вентиляторов, какие только найдутся в компьютере. Последовательности байтов из устройства /dev/urandom менее качественные с точки зрения статистики, чем из /dev/random. С другой стороны, байты считываются из /dev/urandom мгновенно, а устройство /dev/random может заставить программу, читающую из него, подождать, пока не накопится достаточно случайной информации для получения нового байта.

Мы сообщаем читателям эти подробности лишь для расширения кругозора. Проблему несовершенства датчиков случайных чисел мы принимаем к сведению. Готовая программа будет полностью игнорировать эту проблему, считая процедуру rand идеальным воплощением генератора случайных чисел.

Информатика-54© А. Н. Швец