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

ВВЕДЕНИЕ

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

Цель данной курсовой работы - исследование алгоритмов поиска и сортировки данных.

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

Предметом исследования в данной курсовой работе являются способы и методы реализации алгоритмов сортировки на языках программирования высокого уровня, в частности на языке Delphi. Pascal, C++.

В рамках выполнения курсовой работе необходимо решить следующие основные задачи:

- Изучить научно методическую литературу по теме исследования,

- ознакомление с алгоритмами сортировки,

- проанализировать с алгоритмами сортировки и осветить каждый из них.

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

Часто данные приходится упорядочивать, прежде чем обрабатывать их. Если набор данных не упорядочен, то чтобы выяснить, есть ли среди них определённый элемент, нужно перебрать все данные. Если данные упорядочены, то можно воспользоваться методом дихотомического поиска, или метода деления пополам, который работает гораздо быстрее, чем полный перебор. Для того, чтобы данные были упорядочены, можно заполнять специальные структуры данных, которые автоматически упорядочивают по- падающую в них информацию, а можно и воспользоваться алгоритмами сортировки, чтобы перегруппировать уже записанные в массив неупорядоченные данные. Алгоритмы сортировки отличаются друг от друга по многим показателям. Одни алгоритмы пользуются дополнительной памятью, а другие — нет. Когда носителями больших объёмов данных были магнитные ленты, было принципиально важно обойтись без дополнительной памяти. В случае жёсткого диска безразлично, далеко или близко находятся обрабатываемые данные, но в случае магнитной ленты это не так. Чтобы сравнить данные, далеко отстоящие друг от друга на ленте, придётся перематывать ленту, а это занимает намного больше времени, чем операции записи и чтения. Поэтому на то, требует определённый алгоритм, чтобы данные лежали близко, или нет, тоже нужно обращать внимание. Применительно к алгоритмам сортировки введём два понятия: ???? — количество сравнений, ???? — количество перестановок. Эти понятия разделяются, так как иногда операция чтения производится значительно быстрее, чем операция записи. Выбор алгоритма сортировки иногда зависит от специфических требований по объёмам данных или по носителям. В каждом языке программирования есть реализованная стандартная функция сортировки, которая обычно работает быстро. В языке C это функция qsort. С прикладной точки зрения студенту достаточно только знать, как ей пользоваться, а отличать сортировку пузырьком от сортировки Шелла он уметь не обязан. Однако разные алгоритмы стоит пройти, так как некоторым студентам это может быть как полезно, так и интересно. Методы сортировки без привлечения дополнительной памяти — это сортировка включением, или сортировка вставками, сортировка прямым выбором и сортировка пузырьком. Эти алгоритмы имеют самую плохую временную сложность; их обычно проходят в школе, и они обычно запоминаются лучше всего. Сортировка включением происходит следующим образом. В начале массив данных пуст, затем начинается его заполнение. Каждый новый элемент входных данных ставится в массив так, чтобы получившийся массив оказался отсортирован. Когда все входные данные окажутся вставлены в массив, тот будет упорядочен. Можно привести аналогию с колодой карт. Карты по очереди берутся в руку, причём каждая карта ставится на своё место по величине. Когда вся колода окажется в руке, она будет упорядочена, это гарантирует сам метод расположения карт. Наилучший случай по перестановкам, когда мало количество сдвигов правой части массива (считая от вставляемого элемента), — это уже отсортированный массив входных данных. Тогда каждый новый элемент становится в конец массива, существующего на момент его добавления, и никаких сдвигов не происходит. Этот же случай является наилучшим по сравнениям, так как достаточно одного сравнения, чтобы понять, что новый элемент нужно добавить в конец массива. Худший случай и по сравнениям, и по перестановкам — когда входные данные отсортированы в обратном порядке. Тогда каждый новый элемент нужно сравнивать с каждым уже имеющимся элементом, ставить его в начало массива и сдвигать весь массив вправо

В среднем, если частично заполненный массив имеет ???? элементов, на вставку очередного элемента потребуется ???? + 1 2 сравнений. Среднее количество присвоений на каждом шаге равно ???? + 1 2 + 2. Пусть размер конечного массива — ????. Тогда минимальные, максимальные и средние временны́е сложности сортировки включением можно представить в
таблице 1:

min ???? = ????(????) min ???? = ????(1)

max ???? = ????(????2 ) max ???? = ????(????2 )

avr ???? = ????(????2 ) avr ???? = ????(????2 )

Таблица 1: Сортировка вставками

Таким образом, временная сложность алгоритма почти всегда равна ????(????2 ). Может повезти, и входные данные будут уже отсортированы, но в общем случае сортировка включением имеет квадратичную от размера входных данных сложность. Это нехорошо, так как количество операций быстро растёт при увеличении ????. Произведём модификацию этого алгоритма. Сразу заметим, что модификацию нужно производить, когда сложность удовлетворительна, нужно только улучшить скорость алгоритма не более, чем в разы. Но если требуется провести сортировку за час, а данному алгоритму нужны для работы трое суток, то модификация бесполезна — нужно менять сам алгоритм.

Поскольку на каждом шаге частичный массив отсортирован, то вовсе не обязательно сравнивать новый элемент со всеми элементами подряд. Методом деления пополам можно значительно уменьшить количество сравнений. Сложность по сравнениям теперь будет не ????(????2 ), а ????(???? log ????). Количество перестановок при этом не затрагивается, так что результирующая сложность алгоритма по-прежнему равна ????(????2 ).

1.1 Сортировка прямым выбором

Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.

Сортировка прямым выбором, или сортировка выборкой, работает следующим образом (Рисунок 1). В неупорядоченном массиве входных данных размера ???? производится цикл по всем элементам. На итерации ???? выбираем самый маленький элемент из части массива [????, ????] и меняем его местами с элементом с номером ????. По мере функционирования алгоритма в левой части массива будут накапливаться уже отсортированные элементы. Для того чтобы найти наименьший элемент из ????, требуется ????(????) операций сравнения. Количество перестановок всего алгоритма будет равняться ????(????). Так как во внешнем цикле алгоритма ???? итераций, то суммарная сложность алгоритма — ????(????2 ), как и у алгоритма сортировки включением. Однако времена работы алгоритма будут немного лучше за счёт коэффициента у ???? 2 . В настоящее время алгоритм сортировки выбором используется исключительно в учебных целях. Лучший случай — когда массив входных данных полностью отсортирован. Тогда количество перестановок равно нулю. Однако количество сравнений при этом не изменится — ????(????2 ). Худший случай — когда приходится делать перестановку на каждой итерации алгоритма, например, когда весь массив отсортирован, кроме того, что наибольший элемент стоит на первой позиции. Тогда ???? = ????(????), а количество сравнений — то же самое.

Рисунок 1 Сортировка прямым выбором.

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

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

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

При сортировке пузырьком сравниваются пары рядом стоящих элементов. Если они стоят в правильном порядке, то ничего не происходит, а если левый больше, чем правый, то они меняются местами. Затем сравнивается пара элементов, смещённая на единицу относительно предыдущей. Когда один проход по массиву заканчивается, начинается следующий, в котором происходит то же самое. Такие проходы производятся до тех пор, пока весь массив не будет отсортирован. Критерием этого является условие, что на очередном проходе не было произведено ни одной перестановки. Название алгоритма связано с тем, что большой элемент в начале массива в процессе одного прохода как бы «всплывает» вверх (то есть вправо), как пузырь. Маленькое число, наоборот, может сдвинуться влево только на одну позицию за проход. По мере работы алгоритма проходы занимают всё меньше времени, потому что правая часть массива оказывается отсортирована. Этот алгоритм прекрасно подходит для сортировки на магнитных лентах, так как каждый раз сравнивается пара рядом стоящих элементов. Правда, за каждым проходом следует холостая перемотка на начало массива. Так как большие числа «всплывают» быстро, а маленькие «тонут» медленно, то напрашивается модификация алгоритма сортировки пузырьком. Нужно чередовать проходы вправо и влево, тогда эти два процесса происходят одинаково быстро. Такая модификация называется шейкерной сортировкой. Лучший случай — когда массив входных данных изначально отсортирован, тогда производится только один проход, за который программа убеждается, что в массиве ничего менять не нужно. Худший случай — когда массив отсортирован в обратном порядке, тогда за один проход большое число с первой позиции поднимается до своего места в конечном массиве, а количество перестановок максимально. Временна́я сложность алгоритма сортировки пузырьком даже в среднем случае равна ????(????2 ). Её модификация, шейкерная сортировка, имеет такую же сложность.

1.3. Сортировка Шелла

Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами (Рисунок 2).

Рисунок 2 Сортировка Шелла.

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской».

Выбираем из массива подпоследовательность чисел, расположенных друг от друга на расстоянии ????. Эта подпоследовательность сортируется тем или иным методом. Затем сортируется подпоследовательность, получающаяся из предыдущей сдвигом вправо на одну позицию. После того, как все возможные подпоследовательности с шагом ???? отсортированы, выбирается другое значение шага, и процедура повторяется. Каким образом выбирать шаг ???? — сложный вопрос, на эту тему пишутся научные статьи. В отличие от предыдущих алгоритмов, где всё очень наглядно, для обоснования сложности этого алгоритма нужна математика. Количество перестановок ???? у алгоритма Шелла оценивается как ???? (????4 3). На больших наборах данных это намного лучше, чем ????(????2 ).

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

Если имеются две отсортированные подпоследовательности, то чтобы составить из них отсортированную последовательность, нужно попарно сравнивать очередные элементы из них, и перемещать в результирующую последовательность меньший из них (Рисунок 3).

Рисунок 3 Сортировка слиянием.

На этом принципе основана сортировка слиянием mergesort. Из той подпоследовательности, из которой только что был перемещён элемент, на следующей итерации берётся следующий по величине элемент, а из другой подпоследовательности — тот же самый, что и на прошлой итерации. Если в одной из подпоследовательностей закончились элементы, то остаток другой просто пристыковывается справа к результирующей последовательности. Если в обеих подпоследовательностях содержится по ???? элементов, то сложность такого слияния этих подпоследовательностей — ????(????). На глобальном уровне принцип данного алгоритма таков. Разбиваем весь массив на две части. После того, как обе части отсортированы, применим вышеописанную процедуру для их слияния в отсортированный массив. Чтобы отсортировать одну такую часть, разобьём и её пополам. После того, как обе четверти отсортированы, применим вышеописанную процедуру слияния, чтобы получить отсортированную половину. Продолжаем дробить части массива до тех пор, пока одна подпоследовательность не достигнет размера в 1 или 2 элемента — такую группу элементов легко отсортировать. Рекурсивно применяя процедуру разбиения пополам и слияния подпоследовательности, можно отсортировать и весь массив. Сложность алгоритма сортировки слиянием — ????(???? log ????).

1.5. Стабильность алгоритма сортировки

Пусть дана таблица студентов, в которой содержатся такие поля, как «фамилия» и «средний балл». Изначально строки отсортированы по фамилии. Требуется отсортировать их по среднему баллу, при этом строки с одинаковыми средними баллами должны оставаться отсортированными по фамилии. Сортировка, которая не меняет местами элементы с одинаковыми значениями, называется стабильной. Чтобы решить вышеописанную задачу, нужна стабильная сортировка. Сортировка выборкой, например, стабильна, потому что если имеются несколько эле- ментов с одинаковыми значениями, то этот алгоритм сначала выберет первый из них, затем второй, и т. д., так что их порядок в массиве сохранится. Однако если изменить алгоритм так, чтобы он выбирал последний из равных элементов, а не первый, то свойство стабильности пропадает. Это можно сделать, изменив в условии выбора текущего элемента строгое неравенство на нестрогое: i f ( x <= min ) min=x ;

1.6. Быстрая сортировка

В неотсортированном массиве выбирается какой-то элемент. Проводится цикл по массиву, в котором тот разделяется на две части: в одной из них лежат элементы, меньшие, чем выбранный, а в другом — большие. Группы элементов ставятся одна за другой, между ними вставляется выбранный элемент. Для каждой части эта процедура рекурсивно повторяется, пока весь массив не окажется отсортированным. Выбор разделяющего элемента является важным этапом алгоритма. Очевидно, что наименьший или наибольший элемент — это плохой выбор, так как все элементы массива окажутся в одной части. Хорошим выбором был бы выбор среднего по значению, но на каждой итерации для его вычисления нужно потратить ????(????) операций. Часто делают проще: берут три произвольных элемента в группе и выбирают средний из них. Сложность этого алгоритма составляет ????(???? log ????). В общем случае быстрая сортировка является нестабильной: может сложиться ситуация, когда порядок одинаковых по значению элементов нарушится. Например, пусть имеется три одинаковых элемента, а на очередной итерации быстрой сортировки выбран второй из них. Тогда первый и третий элементы окажутся по одну сторону от второго элемента.