Сортировка и поиск МТИ

Курсовая работа, Сортировка и поиск. МТИ. 36 стр. ...

ВВЕДЕНИЕ 3
1 ОСНОВЫ АЛГОРИТМИЗАЦИИ 4
2 АЛГОРИТМЫ ПОИСКА 7
2.1 Линейный поиск 7
2.2 Поиск с барьером 9
2.3 Двоичный поиск 11
2.4 Поиск подстроки в строке 13
3 АЛГОРИТМЫ СОРТИРОВКИ 18
3.1 Сортировка обменом 19
3.2 Сортировка выбором 21
3.3 Сортировка включением 23
3.4 Оценка алгоритмов сортировки 25
4 УСОВЕРШЕНСТВОВАННЫЕ АЛГОРИТМЫ СОРТИРОВКИ 27
4.1 Турнирная сортировка 27
4.2 Сортировка Шелла 29
4.3 Быстрая сортировка Хоара 31
ЗАКЛЮЧЕНИЕ 33
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 35

Алгоритмы сортировки и поиска очень широко распространяются практически во всех задачах обработки информации. При этом они настолько тесно связаны друг с другом, что образуют отдельный класс алгоритмов. Алгоритмы сортировки, как правило, применяются с целью осуществления последующего более быстрого поиска. Например, трудно пользоваться словарями, если бы слова в них не были бы упорядочены по алфавиту.
Цель курсовой работы заключается в следующем:
 исследование алгоритмов поиска и сортировки данных;
 расширение, систематизация и закрепление теоретических знаний;
 формирование навыков ведения самостоятельных теоретических и практических исследований в соответствии с направлением обучения;
 формирование навыков правильного оформления научно-исследовательской работы;
 приобретение опы та обработки, анализа и систематизации результатов практических (экспериментальных) исследований по направлению обучения;
Для достижения поставленной цели нужно решить следующие задачи:
 формирование навыков научно оформлять и излагать свои мысли, выводы и результаты исследования;
 исследовать алгоритмы сортировки и поиска.
Курсовая работа состоит из введения, трех разделов, списка используемой литературы, включающего 20 наименования авторов. Общий объем страниц машинописного текста составляет 31 страниц. Работа содержит 2 рисунка и 3 таблицы.

Сдвигаем образец вправо на две позиции в соответствии с таблицей смещений:
aaaajaaabcbaabc
baabc
Последний символ снова не совпадает с символом строки.
Шаг 4.
В соответствии с таблицей смещений сдвигаем образец на 2 позиции:
aaaajaaabcbaabc
baabc
Шаг 5.
Еще раз сдвигаем образец на 2 позиции:
aaaajaaabcbaabc
baabc
Шаг 6.
В соответствии с таблицей смещений сдвигаем образец на одну позицию, получаем искомое вхождение образца:
aaaajaaabcbaabc
baabc
3 Алгоритмы сортировки
Экономия памяти – это главное требование, предъявляемое к методам сортировки. То есть, при выборе метода сортировки руководствуются критерием экономичного использования памяти. Классификация алгоритмов проводится в соответствии с эффективностью.
Удобно измерять эффективность, подсчитывая число необходимых сравнений ключей и число пересылок элементов. Эти числа определяются некоторыми функциями от числа n сортируемых элементов.
Исследование алгоритмов сортировки начинают с самых простых, но в то же время самых неэкономичных методов. Это объясняется следующими причинами:
1) Тексты программ, которые основаны на данных методах, легки и коротки для понимания.
2) Данные методы хорошо подходят для объяснения принципов и свойств сортировки.
3) Простая реализация позволяет экономить время работы программиста над разработкой программы, которое также необходимо учитывать как составную часть при анализе эффективности работы программы.
4) При достаточно малой размерности массивов эти методы часто работают даже лучше, чем более сложные методы.
Методы сортировки массивов можно разбить на три основных группы.
Они классифицируются в зависимости от лежащего в их основе метода:
1) Сортировка обменом.
2) Сортировка выбором.
3) Сортировка включением.
3.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
Сортировка массива методом пузырька
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
89
18
5
1
1
18
5
1
5
5
5
1
18
18
18
1
57
57
57
57
57
89
89
89
89
Анализируя любой метод сортировки, можно получить число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях.
Для сортировки методом пузырьков число сравнений неизменно, потому что два цикла всегда выполняются заданное число раз, и не зависят от упорядоченности исходного массива. Поэтому при сортировке пузырьковым методом всегда выполняется операций сравнения, где «n» задает число сортируемых элементов последовательности. Эта формула выведена на основании того, что внешний цикл сортировки пузырьковым методом выполняется раз, а внутренний цикл выполняется раз. Произведение данных показателей и дает указанную формулу.
Число операций обмена для наилучшего случая будет нулевым, когда исходный массив уже будет отсортирован. Число операций обмена для среднего случая будет равно , а в наихудшем случае будет равно раз. Стоит отметить, что по мере того, на сколько хуже массив отсортирован, число неупорядоченных элементов приближается к числу сравнений. При этом каждый неупорядоченный элемент требует 3 операции обмена. Пузырьковый метод иногда называют квадратичным алгоритмом, так как время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов данным методом потребует большого времени, поскольку время выполнения сортировки квадратично зависит от числа элементов последовательности.
3.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 mass[j] < mass[min] then begin
min = j
t:= mass[i];
mass[i]:= mass[min];
mass[min]:= t;
end;
Для иллюстрации работы сортировки пузырьковым методом в таблице 2 представлены результаты каждого этапа сортировки массива.
Таблица 2
Сортировка выбором
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
89
1
1
1
1
18
18
5
5
5
5
5
18
18
18
1
89
89
89
57
57
57
57
57
89
Как и в сортировке пузырьковым методом внутренний цикл выполняется раз а, внешний цикл выполняется раз. Это значит, что число сравнений для сортировки выбором равно . Данная сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно , а в худшем случае равно . В случае, когда исходный массив уже упорядочен, потребуется поменять местами только элементов, при этом, каждая операция обмена требует три операции перестановки. Количество операций обмена для метода выбором равно , где (константа Эйлера). То есть, несмотря на одинаковое количество операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.
3.3 Сортировка включением
Данная сортировка является последней из простых алгоритмов. При сортировке включением (вставками) сначала упорядочиваются первые два элемента последовательности. Затем последовательно осуществляется вставка третьего элемента массива в соответствующую для него позицию по отношению к первым двум элементам, а затем четвертый элемент вставляется в список из трех элементов. Этот процесс повторяется до тех пор, пока весь массив не будет отсортирован.
Таким образом, процесс сортировки вставками осуществляется путем сканирования отсортированного подмассива слева направо, пока не достигается первый элемент, больший или равный mass[n–1], и после этого происходит вставка элемента непосредственно перед найденным элементом.
Сортировка включением (вставками) основана на рекурсии. Однако более эффективной будет ее итеративная реализация, то есть снизу вверх. Элемент mass[i] (начиная с элемента mass[1] и заканчивая mass[n–1]) вставляется на соответствующую позицию среди первых i элементов массива, которые к этому времени уже отсортированы. Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве [2, с. 230].
Ниже приведен фрагмент программы на языке Паскаль, которая реализует сортировку включением.
for i = 1 to n - 1 do
y= mass[i];
j = i – 1;
while j >= 0 and mass[j] > t do begin
mass[j + 1] = mass[j];
j = j – 1;
end;
mass[j + 1] = y;
Иллюстрация работы алгоритма представлена в таблице 3.
Таблица 3
Сортировка вставками
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
89
18
5
1
1
18
89
18
5
5
5
5
89
18
18
1
1
1
89
57
57
57
57
57
89
Сортировка простыми вставками противоположна сортировке простым выбором. При сортировке простыми вставками (включениями) на каждом шаге алгоритма рассматривается только один очередной элемент входного массива и все элементы готового массива для нахождения места вставки.
В отличие от сортировки методом обмена и сортировки выбором, количество операций сравнения для сортировки вставками зависит от исходной упорядоченности массива элементов. Если исходный массив уже отсортирован, то число операций сравнения равно . Если массив упорядочен в обратном порядке, то число операций сравнения равно , давая в среднем значение . Число операций обмена будет следующим:
- для худшего случая: ;
- в среднем: ;
- для лучшего случая: .
Число операций обмена для худшего случая будет столь же большим, как и для сортировки методом обмена и сортировки выбором. Но число операций обмена для среднего случая будет немного меньше. Сортировка вставками имеет два преимущества:
1) Данный метод обладает естественным поведением. Другими словами, сортировка включением выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это полезно в том случае, когда массив почти отсортирован.
2) Сортировка включением устойчива. Элементы с одинаковыми ключами не переставляются, и если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставками он по-прежнему будет отсортирован по двум ключам.
Хотя число сравнений может быть достаточно небольшим для определенных последовательностей элементов, постоянные сдвиги массива требуют выполнения большого числа операций перестановок. Сортировка включением имеет естественное поведение и требует наименьшее число операций обмена для почти упорядоченного списка, а так же наибольшее число операций обмена, в тех случаях, когда массив данных упорядочен в противоположном направлении.
3.4 Оценка алгоритмов сортировки
Для каждого метода сортировки может быть организовано большое число алгоритмов. Каждый алгоритм имеет свои достоинства и недостатки. В целом оценка качества алгоритма сортировки зависит от ответов на следующие вопросы:
1) Является ли поведение алгоритма естественным?
Алгоритм сортировки обладает естественным поведением, если для сортировки уже упорядоченной последовательности элементов требуется наименьшее время, а для менее упорядоченного массива время сортировки увеличивается. В случае, когда список элементов упорядочен в противоположном порядке, время сортировки становится наихудшим, то есть принимает наибольшее значение.
2) Устойчива ли сортировка по отношению к перестановке элементов в случае одинаковых значений ключа?
Алгоритм сортировки устойчив, если относительный порядок элементов не меняется при сортировке. Устойчивость сортировки часто бывает желательна, если элементы отсортированы (упорядочены) по каким-то дополнительным ключам, то есть свойствам не отраженным в основном ключе. Это свойство становится достаточно важным при перегруппировки элементов с одинаковыми значениями ключа сортировки и наиболее сильно проявляется при работе с базами данных, упорядоченными сразу по нескольким ключам.
3) С какой средней скоростью алгоритм сортирует данные?
В каждом конкретном случае очень важна скорость работы метода сортировки. Скорость, с которой последовательность элементов упорядочивается, прямо зависит от числа операций сравнения и числа необходимых операций перестановок, причем операции перестановок занимают, как правило, большее время. Данный анализ показывает, что для некоторых алгоритмов, время сортировки зависит логарифмически от числа элементов, а для других алгоритмов это время находится в экспоненциальной зависимости от числа элементов в сортируемом массиве. Стоит отметить, что время может быть разным для различных ЭВМ (так как разным может быть соотношение между временами выполнения операций сравнения и обмена для различных компьютеров).
4) Какова скорость в наихудшем и наилучшем случаях?
Время работы алгоритма в наихудшем и наилучшем случаях, имеет большое значение, если эти случаи часто встречаются. Сортировка может иметь хорошую среднюю скорость, но очень плохую скорость в наихудшем случае, и наоборот.
4 Усовершенствованные алгоритмы сортировки
Все алгоритмы сортировки, рассмотренные выше в данной курсовой работе, обладают очень серьезным недостатком. Этот недостаток заключается в том, что время их выполнения пропорционально квадрату числа элементов. Для больших последовательностей элементов эти сортировки будут выполняться медленно, а начиная с некоторой величины размерности массива, они будут выполняться очень долгое время. Данный факт в большой степени ограничивает их применение на практике.
4.1 Турнирная сортировка
Этот метод сортировки получил свое название из-за сходства с кубковой системой проведения спортивных соревнований (турниров): участники соревнований разбиваются на пары, в которых разыгрывается первый тур. Из победителей первого тура составляются пары для розыгрыша второго тура.
Турнирное дерево используется для сортировки списка из N элементов. Рассмотрим эффективный алгоритм, который использует дерево, представленное в виде массива. Пусть имеется последовательно представленное дерево, содержащее N элементов листовых узлов в нижнем ряду. Эти элементы запоминаются на уровне k. 2k > N. Пусть список сортируется по возрастанию. Сравнивается каждая пара элементов и запоминается наименьший из них (победителя) в родительском узле. Процесс продолжается до тех пор, пока наименьший элемент (победитель турнира) не окажется в корневом узле. Например, приведенное ниже дерево задает следующее начальное состояние массива из N = 8 целых чисел. Элементы запоминаются на уровне 3, так как 23 = 8.
Рассмотрим пример. На рисунке 1 представлено исходное дерево.