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

Шаг 1: Присвоить S значение 0.

Шаг 2: Присвоить S значение S+5.

Шаг 3: Перейти к шагу 2.

Для каждого алгоритма важно, чтобы была доказана его конечность.

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

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

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

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

Рассмотрим вопрос оценки алгоритма сортировки данных.

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

Имея лишь приблизительные характеристики исходных данных, можно подобрать метод сортировки, работающий оптимальным образом.

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

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь есть два основных типа:

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

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

 Понятие и теоретическая основа

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 Сортировка обменом

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

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

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

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

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

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

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

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

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

В общем случае, при 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].