Алгоритмы сортировки данных

ВВЕДЕНИЕ

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

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

ГЛАВА 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.

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

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

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

Сортировка вставками (англ. Insertion sort) — это алгоритм, в котором элемент из входящего массива по одному перемещается в пустой массив на подходящие для него место. Сложность вычислений алгоритма - O(n²).

Если взять последовательность из n чисел a₁, a₂, …, a_n , то на выходе получится последовательность вида a^⸍₁, a^⸍₂, …, a^⸍_n, удовлетворяющая условию a^⸍₁ ≤ a^⸍₂ ≤ … ≤ a^⸍_n. Сначала отсортированная последовательность пуста.

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

2.4 Сортировка слиянием

Сортировка слиянием (англ. merge sort) — это алгоритм, в котором происходит упорядочивание списков, или других структур, доступ к элементам которых можно получать только последовательно. Задача разбивается на подзадачи меньшего размера, после чего решаются при помощи рекурсивного вызова, либо, если размер задачи мал, то сортируется непосредственно. Затем решения объединяются, и получается решение исходной задачи.

Для решения задачи сортировки эти три этапа выглядят так:

1. Входной массив разбивается на подмассивы примерно одного размера. Рекурсивное разбиение массива ведётся до тех пор, пока размер массива не будет равен единице. Массив из одного элемента является упорядоченным.
2. Каждый получившийся подмассив сортируется отдельно. Использоваться может один и тот же алгоритм, а могут и разные.
3. Все отсортированные подмассивы объединяются в один. Для этого меньший из двух первых элементов подмассивов перемещается в результирующий массив. При этом счётчики номеров элементов обоих массивов увеличивается на 1. Если в одном из подмассивов остается остаток, то он целиком записывается в конец результирующего массива.

2.5 Сортировка Шелла

Сортировка Шелла (англ. Shell sort) - этот алгоритм является дополненным вариантом сортировки вставками. Его идея заключается в том, что сравниваются не только элементы, расположенные рядом, но и те, что находятся на расстоянии друг от друга. Ещё его можно назвать алгоритм сортировки вставками с предварительными проходами. Аналогичное дополнение в пузырьковой сортировке называется сортировка расчёской.

При сортировке Шелла первым делом происходит сравнение и обмен элементов, расположенных на некотором расстоянии d. Затем тоже самое происходит для меньших значений d. А в самом конце при d=1 используется уже сортировка вставками. То, что число инверсий при сортировке Шелла может быть больше по сравнению с простыми сортировками, где перестановка двух элементов уменьшает число инверсий только на 1, в некоторых случаях может говорить о его эффективности. И хотя во многих случаях скорость алгоритма ниже, чем у быстрой сортировки, он ряд преимуществ:

• нет необходимости выделять память под стек;
• нет деградации если набор данных оказывается неудачным. Быстрая сортировка легко замедляется до O(n²), что хуже по времени, чем худшее гарантированное время для сортировки Шелла.

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

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

Если метод сортировки строк применить к строке, состоящей из чисел, то результат будет контринтуитивным. Так «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Чтобы этого избежать алгоритм может преобразовывать символы чисел в числа и уже их сортировать.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ:

1. Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск /The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007.
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ / INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006.
3. Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003.
4. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 3-е изд. — М.: Вильямс, 2013.
5. Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006.
6. Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006.
7. Алгоритм сортировки – Википедия. http://ru.wikipedia.org/wiki/

1. Финансовый словарь. dic.academic.ru ↑

2. Экономический словарь. dic.academic.ru ↑

3. Попов В.Б. Turbo Pascal для школьников: Учебное пособие, 3-е доп. изд. – М.: Финансы и статистика, 2003 ↑

4. Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 251. ↑

5. Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — 251 с. ↑