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

ВВЕДЕНИЕ

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

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

ГЛАВА 1. АЛГОРИТМ СОРТИРОВКИ

1.1 Что представляет собой алгоритм сортировки

Для раскрытия понятия Алгоритм сортировки рассмотрим следующие определения.

Сортировка – это процесс перегруппировки заданного множества объектов в некотором определенном порядке. Сортировка предпринимается для того, чтобы облегчить последующий поиск элементов в отсортированном множестве^[1].

Алгоритм - (происходит от латинской формы имени математика Аль-Хорезми) последовательность действий, необходимых предпринять исполнителю для достижения результата решения задачи за конечное число действий^[2].

Таким образом Алгоритм сортировки – это порядок действий по упорядочиванию элементов в списке. Обычно это относится к сортировке фрагментов записей, т.е. ключам, которые могут быть упорядочены. При этом записи могут содержать любые данные. Для строковых значений упорядочивание производилось по алфавиту, а для числовых значений использовался математический порядок возрастания и убывания чисел^[3].

Начало развития современных методов сортировки восходит к концу XIX века. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор - электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах. На перфокарте пробивались отверстия, через которые происходило замыкание определённой электрической цепи, которая, в свою очередь, увеличивала счётчик связанного с ней циферблата. После чего перфокарта перемещалась в одно из 26 отделений сортировального ящика. Использование машины увеличило скорость обработки данных в 3 раза, почти 50 перфокарт в минуту. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки.

Дальнейшая история алгоритмов связана с развитием электронно-вычислительных машин (ЭВМ). В 1945 году Джон фон Нейман разработал программы сортировки методом слияния. Они применялись для тестирования ряда команд для EDVAC (Electronic Discrete Variable Automatic Computer - одна из первых электронных вычислительных машин). В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. В 1946 году была опубликована лекция Джона Мокли, в которой были приведены описания методов сортировки простой вставки и бинарных вставок, а также поразрядной сортировки с частичными проходами.

С появлением первых ЭВМ начинается разделение Алгоритмов сортировки на внутренние и внешние.

Внутренняя сортировка (англ. internal sort) — это такой вид алгоритмов сортировки, когда весь массив сортируемых данных помещается в оперативную память. При этом сохраняется с произвольный доступом к любой ячейке. За счёт того, что скорость доступа к оперативной памяти значительно выше, чем к периферийным устройствам, возрастает и скорость сортировки^[4].

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

Внешняя сортировка — вид алгоритмов сортировки, который производился на периферийных устройствах, т.к. массив сортируемых данных не помещался в оперативную память^[5]. Тут были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния.

Как отмечалось ранее, применение внутренней сортировки эффективнее внешней, за счёт скорости обращения к оперативной памяти, по сравнению с временем обращения к магнитным дискам, лентам и т. п.

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

В 1954 году Гарольд Сьюворд развил идеи Гольденберга, и дополнил их анализом методов внешней сортировки.

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

В 1955 году в печати появляется первая большая обзорная статья о сортировке, основанная на работе Дж. Хоскена. В ней он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ.

В 1956 году Э. Френд, проанализировав математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложил некоторые новые методы. Например, вычисление адреса.

В 1959 году были предложены такие методы сортировки, как метод слияния с вставкой, метод обменной поразрядной сортировки, метод каскадного слияния и метод Шелла.

В 1960 году появилась сортировка методом многофазного слияния и методом вставки в дерево.

Осциллирующая сортировка и быстрая сортировка Хоара были разработаны в 1962 году.

А пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году.

Как мы видим, к концу 60-х годов происходило интенсивное развитие теории сортировки. Более поздние алгоритмы в основном представляют собой вариации, разработанных в то время методов. Появились адаптивные методы сортировки. Они основаны на анализе входных данных, и если они удовлетворяют заранее установленным критериям, то их сортировка происходит заметно быстрее.

1.2 Формулировка задачи

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

Пусть требуется упорядочить N элементов: R₁, R₂,…, R_n. Каждый элемент R_j - это запись, в которой содержится информация. Процессом сортировки управляет ключ K_j. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей a,b,c выполнялись следующие условия:

• закон трихотомии, когда справедливо только одно соотношение: либо a < b, либо a > b, либо a = b;
• закон транзитивности, когда из двух соотношений вытекает третье: если a < b и b < c, то a < c.

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

Таким образом, задачей сортировки является нахождение такого расположения записей p(1)p(2)…p(n) с индексами {1,2,…,N}, в котором ключи записей были бы в порядке неубывания:

K_p(1) ≤ K_p(2) ≤ … ≤ K_p(n)

1.3 Свойства алгоритмов сортировки

Из рассмотренной задачи вытекает три свойства алгоритма сортировки:

Первым свойством является устойчивость сортировки:

• Устойчивость (англ. stability) — при устойчивой сортировке не происходит изменения расположения элементов с одинаковыми ключами.

p(i) < p(j) для любых N_p(i) = N_p(j) и i < j.

Второе свойство - это естественность поведения:

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

И третье свойство – это использование операций сравнения.

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

1.4 Оценка алгоритма сортировки

Чтобы оценить алгоритм сортировки применяют показатель Времени, т.е скорости выполнения сортировки, и показатель Памяти, т.е. эффективность использования памяти:

• Время – это основной параметр, также называемый вычислительной сложностью, который характеризует быстродействие алгоритма. Для упорядочения имеет значение поведение алгоритма в худшем, среднем и лучшем вариантах. Если на вход алгоритму подать некоторое множество A, обозначим его n = |A|. Для типичного алгоритма хорошим вариантом поведения будет O(n log n), плохим —O(n²), а идеальным — O(n).
• Память – второй параметр, необходимый алгоритмам, которые требуют использование дополнительной памяти под временное хранение сортируемых данных. Эти алгоритмы требуют O(log n) памяти. При этом размер памяти, которое занимает исходный массив, а так же память, необходимая для хранения кода программы, не учитывается. Алгоритмы, которые не требуют выделения дополнительной памяти, называются алгоритмами сортировки на месте.

ГЛАВА 2. МЕТОДЫ СОРТИРОВКИ

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

В своей работе я рассмотрю некоторые из них.

2.1 Сортировка пузырьком

Сортировка пузырьком (англ. bubble sort) – этот алгоритм относится к простым алгоритмам сортировки. Он эффективен лишь для небольших массивов данных, а его сложность - O(n²).

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

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

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

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

2.2 Поразрядная сортировка

Поразрядная сортировка (англ. radix sort) – алгоритм, выполняющийся за линейное время.

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

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

На практике используется два вида выравнивания упорядоченных данных: в правую сторону, сторону менее значимых разрядов, или единиц - Least significant digit, LSD; и левую сторону, сторону более значимых разрядов - Most significant digit, MSD.

При LSD сортировке сначала сортируются единицы, затем десятки, затем сотни и т.д. При этом уже достигнутые последовательности единиц, десятков и т.д. сохраняются. Например: 1, 2, 9, 10, 21, 100, 200, 201, 202, 210.

При MSD сортировке получается алфавитный порядок. Он очень хорошо подходит для упорядочивания текста. Для примера, последовательность «b, c, d, e, f, g, h, i, j, ba» примет вид «b, ba, c, d, e, f, g, h, i, j». Если последовательность числовая, то получим 1, 10, 100, 2, 200, 201, 202, 21, 210, 9.