Файл: Алгоритмы сортировки данных.pdf

Ниже приведен фрагмент программы на языке Паскаль, которая реализует сортировку включением.

for i = 1 to n - 1 do

y= a[i];

j = i – 1;

while j >= 0 and a[j] >y do begin

mass[j + 1] = a[j];

j = j – 1;

end;

a[j + 1] = y;

Иллюстрация работы алгоритма представлена в таблице 3.

Таблица 3

Сортировка вставками

Сортировка простыми вставками противоположна сортировке простым выбором. При сортировке простыми вставками (включениями) на каждом шаге алгоритма рассматривается только один очередной элемент входного массива и все элементы готового массива для нахождения места вставки.

Сортировка вставками имеет два преимущества^[6]:

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

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

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

2.4 Сравнение методов внутренней сортировки

Анализируя любой метод сортировки, можно получить число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях. Для рассмотренных методов внутренней сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). [2] Таблица 4 содержит данные, приводимые в книге Никласа Вирта.

Таблица 4

Сравнение методов внутренней сортировки

3. Рассмотрение внешней сортировки данных

3.1 Прямое слияние

Внешней сортировкой называется сортировка последовательных файлов, которые располагаются во внешней памяти. Данные файлы слишком велики, чтобы полностью поместиться в основную память, поэтому к ним неприменимы рассмотренные ранее методы внутренней сортировки. Чаще всего внешнюю сортировку используют в системах управления базами данных.^[7]

Пусть имеется некоторый последовательный файл А, который включает в себя записи а1, а2,…, аn. Каждая такая запись состоит из одного ключевого элемента. Для сортировки прямым слиянием необходимы два вспомогательных файла В и С, размер каждого из них равен n/2. В таблице 5 показан пример внешней сортировки простым слиянием.

Таблица 5

Внешняя сортировка простым слиянием

Данный метод сортировки состоит из последовательных шагов. На каждом таком шаге выполняется распределение файла А в файлы В и С, а затем осуществляется слияние файлов В и С в исходный файл А. Файл А содержит записи: 8 23 5 95 44 33 2 6. Размер файла А=8, таким образом, размер вспомогательных файлов В и С равен n/2=4. Сначала осуществляется начальное распределение: последовательно считываются записи файла А, записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C. То есть файл В содержит элементы: 8 5 44 2, а файл С: 23 95 33 6. На втором шаге снова осуществляется последовательное считывание файла А, при этом в файл В записываются последовательные пары с нечетными номерами, а в файл С – с четными. В процессе слияния образуются упорядоченные четверки записей. Они записываются в файл А.

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

Стоит отметить, при данном методе сортировки необходимы всего две переменные, расположенные в основной памяти. Данные переменные необходимы для размещения очередных записей из файлов В и С. Все файлы (А, В и С) будут прочитаны и записаны по O(log n) раз.

3.2 Естественное слияние

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

 
Рисунок 1. Первый шаг сортировки

 
Рисунок 2. Второй шаг сортировки

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

3.3 Сбалансированное многопутевое слияние

В основе сбалансированного многопутевого слияния лежит распределение серий исходного файла по нескольким вспомогательным, то есть по по m вспомогательным файлам B1, B2, ..., Bm и их слияние в m вспомогательных файлов C1, C2, ..., Cm. На следующем шаге производится слияние файлов C1, C2, ..., Cm в файлы B1, B2, ..., Bm и т.д., пока в B1 или C1 не образуется одна серия. Сбалансированное многопутевое слияние является развитием идеи двухпутевого слияния, использованного в предыдущих методах сортировки. Простой пример использования данного метода представлен на рисунке 3.

Рисунок 3. Многопутевое слияние

Данный метод сортировки имеет следующие преимущества: число проходов алгоритма оценивается как O(log n) (n - число записей в исходном файле), где логарифм берется по основанию n. Порядок числа копирований записей равен O(log n). Но число сравнений не будет меньше, чем при использовании метода простого слияния.

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

ЗАКЛЮЧЕНИЕ

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

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

Практически каждый алгоритм сортировки можно разбить на три части:

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

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

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

Различают методы внутренней и внешней сортировки. К методу внутренней сортировки относят методы сортировки массив.

Методы сортировки массивов можно разделить на три основных класса в зависимости от лежащего в их основе метода:

• сортировка пузырьком;
• сортировка выбором;
• сортировка включением.

Пузырьковая сортировка просто реализуется, но используется только в учебных целях и не используется на практике. Это объясняется тем, что сортировка обменом эффективна лишь при небольших массивах элементов.

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

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

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