Сортировка

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

Зависимость выбора алгоритмов от структуры данных - явление довольно частое, и в случае сортировки она настолько сильна, что методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка (последовательных) файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как располагаются во «внутренней» (оперативной) памяти ЭВМ: для этой памяти характерен быстрый произвольный доступ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающих устройствах с механическим передвижением (дисках и лентах).

Введем некоторую терминологию и систему обозначений, которые будем использовать. Нам даны элементы:

a1, a2,...,an.

Сортировка обозначает перестановку этих элементов в таком порядке: a_k1, a_k2,...,a_kn, так, что при заданной функции упорядочивания f справедливо соотношение:

f (a_k1) £ f (a_k2) £ ... £ f (a_kn).

Обычно функция упорядочения не вычисляется по какому-то специальному правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называют ключом элемента. Следовательно, для представления элемента а_i особенно хорошо подходит структура записи.

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

Сортировка массивов. Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, переупорядочивание элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива a в массив b, не представляют для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии с их эффективностью, т.е. экономией времени или быстродействием. Удобная мера эффективности получается при подсчете числа С - необходимых сравнений ключей и М - пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов. Хотя хорошие алгоритмы сортировки требуют порядка n×log₂n сравнений, мы сначала обсудим несколько несложных и очевидных способов сортировки, называемых простыми методами, которые требуют порядка n² сравнений ключей. Прежде чем перейти к более быстрым алгоритмам рассмотрим простые методы, по следующим трем важным причинам:

1. Простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки.

2. Программы, основанные на этих методах, легки для понимания и коротки. Следует помнить, что программы также занимают память!

3. Хотя сложные методы требуют меньшего числа операций, эти операции более сложны: поэтому при достаточно малых n простые методы работают быстрее, но их не следует использовать при больших n.

Методы, сортирующие элементы, можно разбить на три основных класса в зависимости от лежащего в их основе приема:

Сортировка включениями.

Сортировка выбором.

сортировка обменом.

9.1 Сортировка простыми включениями

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность а₁,...,a_i-1 и входную последовательность a_i ,..., a_n. На каждом шаге, начиная с i=2 и увеличивая i на 1, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Таблица 1.1Пример сортировки простыми включениями

Начальные ключи 44 55 12 42 94 18 06 67

i=1 44 55 12 42 94 18 06 67

i=2 12 44 55 42 94 18 06 67

i=3 12 42 44 55 94 18 06 67

i=4 12 42 44 55 94 18 06 67

i=5 12 18 42 44 55 94 06 67

i=6 06 12 18 42 44 55 94 67

рез-т 06 12 18 42 44 55 67 94

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

fori:=2 to n do

begin x:= a[i]

«вставить на подходящее место в a1,...,ai»

End

При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы «просеивать» х, сравнивая его с очередным элементом ai и либо вставляя х, либо пересылая ai направо и продвигаясь налево. Заметим, что просеивание может закончиться при двух различных условиях:

1. Найден элемент ai с ключом меньшим, чем ключ x.

2. Достигнут левый конец готовой последовательности.

Этот типичный пример цикла с двумя условиями окончания дает нам возможность рассмотреть хорошо известный прием фиктивного элемента («барьера»). Его можно легко применит в этом случае, установив барьер a₀=x. (Заметим, что для этого нужно расширить диапазон индексов в описании а до 0,...,n.) .

Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность а₁,...,a_i-1 , в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.

9.2 Сортировка простым выбором

Этот метод основан на следующем правиле:

Выбирается элемент с наименьшим ключом.

Он меняется местами с первым элементом a1.

Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не станет только один элемент - наибольший. Этот метод продемонстрирован на тех же восьми ключах в табл. 1.2

Таблица 1.2Пример сортировки простым выбором

Начальные ключи 44 55 12 42 94 18 06 67

i=2 44 55 12 42 94 18 06 67

i=3 06 55 12 42 94 18 44 67

i=4 06 12 55 42 94 18 44 67

i=5 06 12 18 42 94 55 44 67

i=6 06 12 18 42 94 55 44 67

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 94 67

рез-т 06 12 18 42 44 55 67 94

Программу можно представить следующим образом:

for i:=1 ton-1 do

begin«присвоить k индекс наименьшего элемента из a[i]... a[n]»;

«поменять местами a_i и a_k»

End

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

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

9.3 Сортировка простым обменом

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

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

Таблица 1.3Пример сортировки методом пузырька

Начальные

ключи i=2 i=3 i=4 i=5 i=6 i=7 i=8

44 06 06 06 06 06 06 06

55 44 12 12 12 12 12 12

12 55 44 18 18 18 18 18

42 12 55 44 42 42 42 42

94 42 18 55 44 44 44 44

18 94 42 42 55 55 55 55

06 18 94 67 67 67 67 67

67 67 67 94 94 94 94 94

Этот алгоритм легко оптимизировать. Пример в табл. 1.3 показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидным способом улучшить данный алгоритм - это запоминать, производился ли на донном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса k, уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться по установленной заранее нижней границе i. Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывает на место за один проход, а неправильно расположенный элемент в легком конце будет опускаться на правильное место только на один шаг на каждом проходе. Например, массив: 12 18 24 44 55 67 94 06 будет рассортирован при помощи метода пузырька за один проход, а сортировка массива: 94 06 12 18 42 44 55 67 потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов. Мы назовем полученный в результате алгоритм шейкерной сортировкой. Его работа показана в табл.1.4 на тех же восьми ключах, которые использовались в табл. 1.3

Таблица 1.4Пример шейкер-сортировки

i=2 3 3 4 4

r=8 8 7 7 4

44 06 06 06 06

55 44 44 12 12

12 55 12 44 18

42 12 42 18 42

94 42 55 42 44

18 94 18 55 55

06 18 67 67 67

67 67 94 94 94

9.4 Сортировка включениями с убывающим приращением

Некоторое усовершенствование сортировки простыми включениями было предложено Д.Л. Шеллом в 1959 г. Рассмотрим применение этого метода на нашем стандартном примере из восьми элементов (см. табл. 1.5).

Таблица 1.5Сортировка включениями с убывающим приращением

44 55 12 42 94 18 06 67

1-сортировка:

44 18 06 42 94 55 12 67

2-сортировка:

06 18 12 42 44 55 94 67

i-сортировка:

06 12 18 42 44 55 67 94

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

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

Очевидно, что этот метод в результате дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки.

Таким образом, программа разрабатываетсявне связи с конкретной последовательностью приращений. Вне t приращений обозначается через

h1, h2,..., ht

с условиями

ht=1, hi+1<hi (1.1)

Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включениями было простым, используется барьер.

Ясно, что каждая gррh h-сортировка требует собственного барьера и что программа должна определять его место как можно проще. Поэтому массив a нужно дополнить не одной компонентой a[0], а h1 компонентами, так что теперь он описывается как

a:array[-h1..n] of <name_record>

9.5 Сортировка с разделением

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

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

Попробуем рассмотреть следующий алгоритм: выберем случайным образом какой-то элемент (назовем его x), просмотрим массив, двигаясь слева направо, пока не найдем элемент ai > x. Затем просмотрим его справа налево, пока не найдем элемент ai < x . Теперь поменяем местами два элемента и продолжим процесс «просмотра с обменом», пока два элемента не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами меньшими, чем x ,и правую - с ключами большими x .

Если, например, в качестве x выбрать средний ключ, равный 42, из массива ключей 44 55 12 42 94 06 18 67,

то для того, чтобы разделить массив, потребуется два обмена

18 06 12 | 42 | 94 55 44 67,

конечные значения индексов i=5 и j=3. Ключи a1,..., ai-1 меньше или равно ключу x=42 ключи aj+1 ,..., an больше или равны x. Следовательно, мы получим два массива

ak.key £ x.key для k=1, . . . , i - 1,

ak.key ³ x.key для k=j+1,. . . , n (1.2)

и, следовательно,

a.key = x.key k=j+1, . . . , i - 1.

Этот алгоритм очень прост и эффективен, так как основные величины, участвующие в сравнениях: i, j и x , можно во время просмотра хранить на быстрых регистрах. Но он также может быть весьма неуклюжим, как видно из примера с n одинаковыми ключами, в котором выполняется n/2 обменов. Эти ненужные обмены можно легко устранить, заменив операторы просмотра на

while a[i] .key £ x .key do i := i+1;

while x .key £ a[j] .key do j := j -1;

Но тогда выбранный для сравнения элемент x, который находится в массиве, перестанет служить в качестве барьера для двух разнонаправленных просмотров. В случае, когда в массиве все ключи одинаковы, просмотры выйдут за его границы, если не использовать более сложные условия окончания. Простота условий оправдывает излишние обмены, которые в среднем для «случайных» массивов происходят довольно редко. Небольшую экономию можно, однако, получить, если заменить условие, управляющее обменом, на i<j вместо i£j. Но такую замену нельзя распространить на оба оператора (i:=i+1;j:=j-1), которые поэтому требуют использования различных условий. Необходимость условия i£j можно проиллюстрировать следующим примером при x=2: 1 1 1 2 1 1 1

Первый просмотр и обмен дают 1 1 1 1 1 1 2, причем i=5, j=6. Второй просмотр не изменяет массив и заканчивается с i=7 и j=6. Если бы обмен не подчинялся условию i £ j, то произошел бы ошибочный обмен а₆ и а₇.

В правильности алгоритма разделения можно убедиться на основании того, что оба утверждения (1.2) являются вариантами оператора цикла с постусловием. В начале, при i=1 и j=n, они, очевидно, истинны, а при выходе с i>j они предполагают, что получен нужный результат.

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

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

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

Поиск

Эта глава посвящена в основном изучению очень простой поисковой задачи: как находить данные, хранящиеся с определенной идентификацией. Например, в вычислительной задаче нам может понадобится найти f(x), имея x и таблицу значений функции f; в лингвистической может интересовать английский эквивалент данного русского слова.

Вообще будем предполагать, что хранится множество из N записей и необходимо определить положение соответствующей записи. Как и в случае сортировки, предположим, что каждая запись содержит специальное поле, которое называется ключом, возможно, потому, что многие люди ежедневно тратят массу времени на поиск своих ключей. Мы обычно требуем, чтобы N ключей били различными, так что каждый ключ однозначно определяет свою запись. Совокупность всех записей называется таблицей или файлом, причём под таблицей, как правило, подразумевается небольшой файл, а файлом обычно называют большую таблицу. Большой файл, или группа файлов, часто называется базой данных.

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