Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Эволюция методов сортировки данных).pdf

Алгоритмы второго класса предназначены для нечисловых процессов. Для алгоритмов второго класса возможно доказательство результативности (конечности) и в общем виде, но часто более существенным является то, как быстро алгоритм завершается и сколько для завершения требуется шагов.

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

2. Методы внутренней сортировки

2.1 Общее понятие и теоретическая основа методов

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

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

Экономия памяти – это главное требование, предъявляемое к методам сортировки. То есть, при выборе метода сортировки руководствуются критерием экономичного использования памяти. Классификация алгоритмов проводится в соответствии с эффективностью.^[5]

Удобно измерять эффективность, подсчитывая число необходимых сравнений ключей и число пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов.

Исследование алгоритмов сортировки начинают с самых простых, но в то же время самых неэкономичных методов. Это объясняется следующими причинами:

1) Тексты программ, которые основаны на данных методах, легки и коротки для понимания.

2) Данные методы хорошо подходят для объяснения принципов и свойств сортировки.

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

4) При достаточно малой размерности массивов эти методы часто работают даже лучше, чем более сложные методы.

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

1) Сортировка обменом.

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

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

4) Сортировка обменом.

Самым распространенным алгоритмом сортировки является пузырьковый метод (или метод сортировки обменом).

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

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

Далее приведен фрагмент программы, реализующий поиск пузырьком на языке Паскаль:

for i:=n-1 downto 1 do {n – количество элементов в массиве}

for j:=1 to i do

if a[j]>a[j+1] then

begin

y:= a[j];

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

a[j+1]:= y;

end;

Данный алгоритм основан на двух вложенных циклах.

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

Пример процесса сортировки обменом представлен в таблице 1.

Для иллюстрации работы сортировки пузырьковым методом в таблице 1 даны результаты каждого этапа сортировки массива.

Таблица 1

Сортировка массива методом пузырька

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

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

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

В общем случае, при i-ом проходе по массиву (0 i n– 2) алгоритм ищет наименьший элемент среди последних n – i элементов и обменивает его с a[i];

После выполнения n – 1 проходов список оказывается отсортирован. Кол программы на языке Паскаль, которая реализует данный алгоритм:

for i = 0 to n – 2 do

min = I;

for j = i + 1 to n – 1 do

if a[j] < a[min] then begin

min = j

y:= a[i];

a[i]:= a[min];

a[min]:= y;

end;

Для иллюстрации работы сортировки пузырьковым методом в таблице 2 представлены результаты каждого этапа сортировки массива.

Таблица 2

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

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

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

Таким образом, процесс сортировки вставками осуществляется путем сканирования, отсортированного подмассива слева направо, пока не достигается первый элемент, больший или равный a[n–1], и после этого происходит вставка элемента непосредственно перед найденным элементом.

Сортировка включением (вставками) основана на рекурсии. Однако более эффективной будет ее итеративная реализация, то есть снизу вверх. Элемент a[i] (начиная с элемента a[1] и заканчивая a[n–1]) вставляется на соответствующую позицию среди первых i элементов массива, которые к этому времени уже отсортированы. Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве [2, с. 230].

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

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.2 Сравнение методов внутренней сортировки

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

Таблица 4

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

3. Методы внешней сортировки

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

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