Методы сортировки и поиска. Сортировка и поиск.

Курсовая работа состоит из введения, четырех разделов, списка используемой литературы, включающего 22 источника. Общий объем страниц машинописного текста составляет 33 страниц. Работа содержит 3 рисунка и 5 таблиц. ...

ВВЕДЕНИЕ 3
2 АЛГОРИТМЫ ПОИСКА 8
2.1 Линейный поиск 8
2.2 Поиск с барьером 10
2.3 Двоичный поиск 11
2.4 Поиск подстроки в строке 13
3 МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ 17
3.1 Сортировка обменом 18
3.2 Сортировка выбором 20
3.3 Сортировка включением 21
3.4 Сравнение методов внутренней сортировки 22
4 МЕТОДЫ ВНЕШНЕЙ СОРТИРОВКИ 24
4.1 Прямое слияние 24
4.2 Естественное слияние 25
4.3 Сбалансированное многопутевое слияние 27
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 32

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

End.
Если X представляет собой длинную строку и при этом мощность алфавита достаточно велика, на практике используется алгоритм Бойера-Мура.
Данный алгоритм поиска строки считается наиболее быстрым среди алгоритмов общего назначения, которые предназначены для поиска подстроки в строке. Алгоритм был разработан в 1977 году Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore). Преимущество алгоритма Бойера-Мура в том, что не нужно осуществлять сравнение строки, которую хотим найти, с каждой буквой исходного текста, так как некоторые из них можно пропустить. Чем длиннее строка Х, тем быстрее работает алгоритм.
При этом поиск начинается с самого правого символа строки X, то есть осуществляется справа налево. Затем на основе некоторой эвристической процедуры осуществляется вычисление величины сдвига. После чего сравнение продолжается, снова начиная с конца строки.
Исследуя строку, осуществляются более эффективные прыжки в тексте в случае обнаружении несовпадения. 
Сначала осуществляется построение таблицы смещений для искомого шаблона (строки, которую нужно найти).
В данной таблице хранится величина сдвига для каждого символа в строке шаблона. Величина сдвига определяется из тех соображений, что он должен быть максимально возможным, но таким, чтобы не пропустить вхождение искомого шаблона. Таблица содержит список всех символов в шаблоне. В соответствие каждому символу ставится его порядковый номер, считая с конца строки. Если символ встречается несколько раз, то используется самое правое вхождение. Совмещая начало текста (строки S) и шаблона, осуществляется проверка, начиная с последнего символа шаблона. Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений. Причем берется символ из строки (а не шаблона) и просматривается соответствующий сдвиг в таблице. После сдвига снова начинается проверка с последнего символа. Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит подстрока в строке найдена, и поиск окончен. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомой строки (шаблона), либо не будет достигнут конец строки.
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 - Сортировка массива методом пузырька
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
105
21
7
3
3
21
7
3
7
7
7
3
21
21
21
3
57
57
57
57
57
105
105
105
105
Сортировка большого числа элементов данным методом потребует большого времени, поскольку время выполнения сортировки квадратично зависит от числа элементов последовательности.
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 a[j] < a[min] then begin
min = j
y:= a[i];
a[i]:= a[min];
a[min]:= y;
end;
Для иллюстрации работы сортировки пузырьковым методом в таблице 2 представлены результаты каждого этапа сортировки массива.
Таблица 2 - Сортировка выбором
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
105
3
3
3
3
21
21
7
7
7
7
7
21
21
21
3
105
105
105
57
57
57
57
57
105
3.3 Сортировка включением
Данная сортировка является последней из простых алгоритмов. При сортировке включением (вставками) сначала упорядочиваются первые два элемента последовательности. Затем последовательно осуществляется вставка третьего элемента массива в соответствующую для него позицию по отношению к первым двум элементам, а затем четвертый элемент вставляется в список из трех элементов. Этот процесс повторяется до тех пор, пока весь массив не будет отсортирован.
Таким образом, процесс сортировки вставками осуществляется путем сканирования отсортированного подмассива слева направо, пока не достигается первый элемент, больший или равный a[n–1], и после этого происходит вставка элемента непосредственно перед найденным элементом.
Сортировка включением (вставками) основана на рекурсии. Однако более эффективной будет ее итеративная реализация, то есть снизу вверх. Элемент a[i] (начиная с элемента a[1] и заканчивая a[n–1]) вставляется на соответствующую позицию среди первых i элементов массива, которые к этому времени уже отсортированы. Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве [2, с. 230].
Ниже приведен фрагмент программы на языке Паскаль, которая реализует сортировку включением.
for i = 1 to n - 1 do
y= a[i];
j = i – 1;
while j >= 0 and a[j] >y do begin
mass[j + 1] = a[j];
j = j – 1;
end;
a[j + 1] = y;
Иллюстрация работы алгоритма представлена в таблице 3.
Таблица 3 - Сортировка вставками
Исходное состояние
Проходы
Первый
Второй
Третий
Четвертый
105
21
7
3
3
21
105
21
7
7
7
7
105
21
21
3
3
3
105
57
57
57
57
57
105
Сортировка простыми вставками противоположна сортировке простым выбором. При сортировке простыми вставками (включениями) на каждом шаге алгоритма рассматривается только один очередной элемент входного массива и все элементы готового массива для нахождения места вставки.
Сортировка вставками имеет два преимущества:
1) Данный метод обладает естественным поведением. Другими словами, сортировка включением выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это полезно в том случае, когда массив почти отсортирован.
2) Сортировка включением устойчива. Элементы с одинаковыми ключами не переставляются, и если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставками он по-прежнему будет отсортирован по двум ключам.
Хотя число сравнений может быть достаточно небольшим для определенных последовательностей элементов, постоянные сдвиги массива требуют выполнения большого числа операций перестановок.
3.4 Сравнение методов внутренней сортировки
Анализируя любой метод сортировки, можно получить число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях. Для рассмотренных методов внутренней сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). [2] Таблица 4 содержит данные, приводимые в книге Никласа Вирта.
Таблица 4 – Сравнение методов внутренней сортировки
 
Min
Avg
Max
Сортировка выбором
Сортировка обменом

Сортировка включением
4 Методы внешней сортировки